Java容器

ArrayList与LinkedList的区别:

底层实现:数组,双链表
消耗内存:ArrayList的内存浪费在为数据预分配的数组,LinkedList每个节点除了保存的值之外还有指向前后节点的指针
在访问上:ArrayList提供随机访问,时间复杂度是O(1),LinkedList不提供,时间复杂度是O(n)
在插入时:ArrayList的时间主要消耗在移动数据,也有可能由于空间不足而重新分配一个新的数组,再将数组拷贝到新数组;而LinkedList主要消耗的时间是查找对应位置,然后直接插入即可,所以综合来看,LinkedList的插入效率要高一些。
线程安全性:都是非线程安全的

ArrayList扩容机制

当插入数据时,首先判断当前的数组是否还有容量,如果还有,则直接插入,如果没有空间了,则进行扩容,初始化一个是原来数组1.5倍大小的新数组,然后将当前数组的数据拷贝到新数组,然后在新数组中添加数据。

ArrayList removeAll方法

ArrayList removeAll(Collection c) 实际调用batchRemove(Collection c, false). 该方法使用时间复杂度为O(n*m)的算法,在原始数组上进行一趟遍历,并调用参数中的collection的contains方法来判断当前元素是否在参数中,具体可以看代码。所以如果最大限度的发挥removeAll的性能的方法是将参数中的collection转化为Set,这样最优的情况contains方法是O(1)的时间复杂度。因为遍历是在try块中,最后还有finally块,所以如果遍历的过程中出现异常,在finally块中判断是否遍历完成,如果没有完成,将后面没有遍历到的地方往前移动,然后将剩余的空间指向null,让GC尽快回收空间,避免出现内存泄漏的情况。

HashMap的实现

底层数据结构

jdk7的时候用的是数组+链表,jdk8用的是数组+链表+红黑树
初始化:使用默认初始化方法,数组的大小初始化为16,但是此时并不会真正的new一个数组,只有在插入数据的时候才会new一个数组。负载因子默认为0.75,意思是当插入的数据的个数达到数组容量的0.75时,进行扩容,扩容的为原数组的两倍。threshold就是扩容开始的触发条件,threshold=capacity*loadFactor

HashMap为什么数组长度保证是2的整数次幂

一是在计算模的时候方便,可以直接通过位运算(capacity-1) | hash来计算出模,二是在扩容的时候,同一个槽位上的节点在新数组上的位置很容易确定,要么还是在当前的index里,要么是当前的index+oldCapacity,迁移的成本更低。

为什么HashMap链表转化成红黑树的threshold是8

通过推理得知,随机数映射到同一个槽位的概率达到百万分之6的最小的阈值是8。

为什么不直接用数组加红黑树,而是先用链表,达到阈值再转成红黑树

  1. 红黑树的节点占用的空间比链表更大,因为除了保存hash,key, value之外,还有保存父节点、左子树,右子树,前驱节点,而链表只需要再保存next节点就行了。
  2. 维护红黑树要比链表麻烦得多,每次插入都要判断是否还满足红黑树的条件,如果不满足还需要进行必要的转换。
  3. 在节点数量少的时候,使用链表进行查找的效率与红黑树没有区别,几乎都是可以忽略不计的,而如果一个hash函数设计的较好,出现碰撞的概率很小,所以用链表更合适。

HashMap直接使用object的hashCode作为hash值寻找槽位的吗

不是的,还经过了一次运算,这个运算是将高16位与低16位做了一个异或运算,使得高位也能参与到槽位的计算中来。

HashMap多线程情况下的死循环问题

jdk7的hashmap在多线程环境下会导致死循环,jdk8修复了这个问题,为什么会导致死循环?
jdk7 hashmap在扩容的时候,将节点从一个槽位移动到另一个槽位用的是头插法,将原来的顺讯颠倒了,而jdk8在扩容时保留了旧的顺序。
用两个线程模拟jdk7的resize操作就能知道死循环出在哪里。

HashMap扩容时每个entry需要再计算一次hash吗

不会,因为Entry中保存了hash值

ConcurrentHashMap怎样保证线程安全的情况下提高效率

jdk7:使用分段锁,类似于将hashmap又抽象了一层,每个segment就是一个hashmap,先将数据hash到segment的槽位,然后再hashsegment中hashmap的槽位,当插入或删除时先对segment的槽位加锁。
jdk8:使用synchronized和cas,底层和HashMap一样,但是在插入的时候会锁住单个槽位,与jdk7相比,锁的粒度小了很多。

有序的map

LinkedHashMap

LinkedHashMap是HashMap的子类,在HashMap的基础上用双向链表来保存元素插入(或访问)的顺序,通过初始化时传入的boolean类型参数accessOrder来决定是插入顺序还是访问顺序。

LinkedHashMap实现LRU算法(Least Recently Used)

LRU是常用的缓存失效算法之一。LRU算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

LinkedHashMap正好可以保存元素的访问顺序,将最近一次访问的元素排序到链表的尾部,表头则是最近最久没有访问过的元素,这样我们就可以在每次插入之后判断是否有必要移除这个元素。而且HashMap在每次插入之后都会调用一个回调方法afterNodeInsertion,LinkedHashMap实现了这个方法,并且如果当前不是LinkedHashMap第一次创建的时候,就会通过removeEldestEntry方法判断是否移除最老的元素(就是表头元素)。所以我们可以重新removeEldestEntry方法来实现LRU。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRUCache(int cacheSize) {
super((int) (cacheSize / 0.75) + 1, 0.75f, true);
this.cacheSize = (int) (cacheSize / 0.75) + 1;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > this.cacheSize;
}
}
复制代码

TreeMap

TreeMap使用红黑树来存储元素,在构造TreeMap的时候可以传入一个Comparator对象,如果不传入的话,需要TreeMap的元素是实现Comparable接口的。

红黑树的性质

  1. 节点只能是黑色或红色
  2. 根节点是黑色
  3. 叶子节点是黑色(null节点)
  4. 红节点的子节点是黑色
  5. 从根节点到任意叶子节点的路径中,黑色节点的个数相同

TreeMap如何实现一致性Hash

以hash值为key,节点为value,保存TreeMap中,在搜索的时候,同样用请求得到一个hash值h1,然后将其作为参数传入TreeMap的tailMap方法,得到一个SortedMap,map的头结点就是离h1最近的节点,如果map为空,那就返回TreeMap的头节点。

线程安全的集合Collections.synchronizedList,synchronizedMap

对线程的操作加锁,实现线程安全。内部维持了一个Object类型的实例,作为锁对象,所以原集合本身的任何操作都不受限制。

CopyOnWriteArrayList

在有写操作的时候,将原数组复制一份出来,然后再写,写操作是需要加锁的。Copy-On-Write用于读多写少的场景。重要字段如下:

/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
复制代码

用ReentrantLock实现加锁,用volatile修饰数组array,可以保证可见性,但是由于get方法并不需要加锁,所以可见性并不是实时的。

为什么没有ConcurrentArrayList?

因为ArrayList这样的数据结构没有规避并发瓶颈的地方。以插入方法add为例,往List尾部插入,在不需要扩容的情况下,可以用自旋锁+CAS+volatile的方式,但是这个方式也会导致插入的数据的index不确定,也就是插入元素的顺序不确定。如果碰到了扩容,就需要加锁,这个加锁是不可避免的。如果是调用add(int index, E element),那么可能需要对index之后的元素都加锁,这一点不容易做到,那只能锁整个数组了。所以ArrayList如果想做到并发安全,无法做到像ConcurrentHashMap那样规避并发瓶颈。

而ConcurrentHashMap,如果一个Key的hashCode方法实现得好,hash碰撞的几率并不大,这时候锁住一个元素代替锁住整个数组,并发安全和并发性能都能兼顾。

ConcurrentHashMap

原理

底层数据结构与HashMap一致,都是数组+链表/红黑树的形式。在put的时候,如果hash槽中无数据,则用CAS将当前节点保存为槽的头结点,如果有数据,则用synchronized锁住头结点,然后再插入。

扩容优化

与HashTable对比

稀土掘金
我还没有学会写个人说明!
上一篇

在 TKE 中使用 Velero 迁移复制集群资源

你也可能喜欢

评论已经被关闭。

插入图片