[关闭]
@Catyee 2021-08-01T21:05:45.000000Z 字数 14726 阅读 453

Java集合类

面试

一、ArrayList和LinkedList

1.1 ArrayList

实现： ArrayList底层基于数组实现，如果不在初始化的时候指定容量，默认容量是10，超过容量就会进行扩容，扩容就是创建一个新的数组，将旧数组的元素拷贝到新数组。默认扩充到1.5倍。
特点： 由于底层是数组，数组的每个元素占用内存空间的大小固定，并且每个元素的物理地址连续，所以可以通过第一个元素的地址算出其它每个元素的地址，所以随机访问的时间复杂度是O(1)，但是如果往数组中间插入元素或者删除元素，就会导致这个元素后面的元素整体移动。ArrayList底层是数组，自然具有数组的特性，所以ArrayList随机访问的速度是O(1)，由于要移动元素Add()方法的平均复杂度是O(n)，但是ArrayList的大部分场景都是往末尾顺序add()元素，这时候并不需要移动元素，时间复杂度是O(1)，只要没发生扩容，性能也非常好。另外ArraList的set()方法是覆盖某个位置的元素，不会移动元素。注意数组一旦初始化完成长度就已经固定了，所以size()方法返回的并不是数组的长度，而是元素的个数。
快速失败：ArrayList记录了一个操作数，在add，remove等操作的时候会将操作数加1，如果使用迭代器，在初始化的时候将这个操作数赋给迭代器，在用迭代器遍历的时候，如果发现迭代器记录的操作数和实际的操作数不一致，就会立刻报错，这个就是快速失败。其它集合类的快速失败原理也是一样的。

1.2 LinkedList

实现： LinkedList底层是一个双向链表，同时也是一个双端队列(Deque)。双向代表每个节点都有指向上一个节点和下一个节点的指针；双端代表可以在队列的两端进行出队入队操作。
特点： 和数组不同，链表的每个节点并不要求占用物理连续的内存空间，而是使用额外的指针指向下一个或上一个节点，由于不能通过计算得到节点的物理地址，所以访问节点只能通过遍历。由于是双向链表，可以正向也可以反向遍历，LinkedList在访问节点的时候会去比较节点离队头近还是队尾近，从而决定遍历的方向，但总体来说都对随机访问不友好，需要更多的时间复杂度。双向链表在插入和删除的时候只需要操作指针就可以了，操作本身是O(1)的时间复杂度，但是在操作之前得先找到这个节点的位置，需要经过一次遍历，所以如过通过下标在链表的中间添加或删除节点需要的时间复杂度仍然是O(n)。

3、ArrayList和LinkedList使用注意事项

并不能笼统的说ArrayList访问速度快而LinkedList插入删除速度快。需要看具体的使用方式。使用上要注意以下几点：

二、CopyOnWriteArrayList

ArrayList并不是线程安全的，如果需要保证线程安全性可以使用CopyOnWriteArrayList，CopyOnWriteArrayList适合读操作远大于写操作的场景。
CopyOnWriteArrayList底层也是数组，但是它用了一种"写时复制"的思路来保证线程安全性，同时保证读的高效性。安全性包括写时候的安全性和读时候的安全性，CopyOnWriteArrayList在add方法上加了锁(ReentrantLock)，所以写时的安全性是通过锁来保证的。CopyOnWriteArrayList在读的时候不用加锁，那它如何保证读的安全性呢？这就是写时复制的思路了，在调用add()方法进行写操作的时候，先加锁，然后不直接向原先的数组中添加元素，而是先创建一个新的数组，数组长度为原来数组长度加1，将原来数组的元素拷贝过来，将新元素添加到新数组，然后替换原来的旧数组。只要数组用volatile关键字修饰保证可见性，读操作就不用加锁了，由于没有加锁，所以读的性能也很好。由于每次add操作都需要创建新的数组并复制元素，所以写操作性能不好。只适合读操作远多于写操作的场景。

  1. // 用volatile修饰保证可见性
  2. private transient volatile Object[] array;
  4. /**
  5.  * Gets the array.  Non-private so as to also be accessible
  6.  * from CopyOnWriteArraySet class.
  7.  */
  8. final Object[] getArray() {
  9.     return array;
  10. }
  12. /**
  13.  * Sets the array.
  14.  */
  15.  // 用新数组替换旧的数组
  16. final void setArray(Object[] a) {
  17.     array = a;
  18. }
  20. // 写操作
  21. public boolean add(E e) {
  22.     final ReentrantLock lock = this.lock;
  23.     lock.lock();
  24.     try {
  25.         Object[] elements = getArray();
  26.         int len = elements.length;
  27.         // 创建一个新的数组，并将旧数组的元素拷贝到新数组
  28.         Object[] newElements = Arrays.copyOf(elements, len + 1);
  29.         newElements[len] = e;
  30.         setArray(newElements);
  31.         return true;
  32.     } finally {
  33.         lock.unlock();
  34.     }
  35. }
  37. // 读操作
  38. public E get(int index) {
  39.     return get(getArray(), index);
  40. }

三、HashMap

1、HashMap基本实现原理

思路：概念、底层结构、如何解决hash冲突、1.7put、get过程，1.8put、get过程
HashMap即散列表，存储的是键值对，散列表的目的是为了尽可能在O(1)的时间复杂度之内通过key获取到value，O(1)时间内的随机访问我们首先想到的就是数组，HashMap底层也是通过数组来实现的，不过数组是通过下标来进行随机访问的，散列表是通过key来进行访问，那怎么办呢？这就需要把key映射到数组下标，hash函数就是做这个的，映射的过程可能出现多个key映射到同一个数组下标，这就是hash冲突，解决hash冲突有多种方式，java HashMap使用的是拉链法，所谓拉链法就是用一个链表来存储hash冲突的这些键值对。
我们来看一下Hash算法：

  1. // 1.8 处理hash值（1.7处理hash值更加复杂）
  2. static final int hash(Object key) {
  3.     int h;
  4.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  5. }
  7. // 通过hash值计算数组下标
  8. (tab.length - 1) & hash

首先看一下更具hash值计算数组下标的算法，数组的长度总是，这个数值减一之后的数值的二进制表示中高位都是0，低位都是1，HashMap默认容量是16，我们以16为例，16减1就是15，15的二进制表示如下：

  1. 15: 0000 1111

用这个数与hash值做与运算，不管hash有多大，运算结果高位都会变成0，而低位会保持原有的数值，但是这个数值不管有多大都不会比低位都是1的数值大，所以保证了这个数一定在数组范围内，实际上是消除了高位，保留了低位。
这样虽然保证了不会发生数组越界，但是高位实际上是没有参与计算的，为了更进一步的散列，减少hash冲突，就得想方法让高位也参与计算，这就是处理hashcode的算法，具体做法就是用原始的hashcode值与hashcode的高16位做异或运算，之所以选择异或是因为与运算和或运算都会使结果更偏想0或1，只有异或运算是更加均匀的，会使得结果更加散列。

jdk1.7的时候底层用一个Entry数组来作为HashMap的底层结构，数组的每一个元素都是一个单链表。正常情况下，我们总是希望没有hash冲突，没有hash冲突的时候访问只需要访问数组元素的头节点就可以了，不用遍历链表，数组支持随机访问，效率最高。但是hash冲突总是不可避免，总有两个元素散列到同一个数组下标的情况，这个时候就只好构造一个链表，将元素存入链表中。

HashMap在put的时候，如果key不是null，先用hash算法计算出存储数组的元素下标，然后检查数组在这个位置有没有元素，如果没有，直接构造一个节点放进去进去。如果有元素，那说明已经存在链表（只有头节点也是链表），这个时候就要遍历链表，比较待存储元素的key和链表中每个节点的key有没有相等的，如果有相等的就覆盖，如果都不相等，就采用头插法插入链表。如果key是null，就会存储到数组的第0个位置，存储的过程和普通元素的存储过程是一样的。

Get的时候也一样，如果key不是null，先用hash算法确定存储的数组下标，检查这个数组在这个位置有没有元素，没有就返回null，有的话就遍历链表，比较key和节点的key是不是相等的，相等就把value取出，如果遍历结束仍然没有相等的，就返回null；如果key是null，就去数组第0个位置取值，取值过程和普通元素一样。

注意上面讲的是1.7中HashMap的put和get过程，到了1.8，HashMap采用了数组加链表加红黑树的结构。当链表的长度超过8，就会自动构造为红黑树。原因也很简单，如果出现链表，遍历链表的时间复杂度是O(n)，但是访问红黑树节点的时间复杂度是O(logn), 这样进一步提高了效率。因为加入了红黑树的结构，1.8中put和get方法也会发生一些变化，put的时候一开始计算数组下标还是一样的方法，计算出数组下标之后如果发现这个位置已经有元素了，就要判断这个元素是一个链表节点还是一个红黑树节点，如果是红黑树节点，要按红黑树的方式插入；如果是链表节点，就按链表的方式插入，在链表中插入之后还要判断是否插入之后链表长度超过了8，并且总容量是否超过了64，如果超过了，还要将链表转化为红黑树，如果只是单纯链表长度超过了8，总容量没有超过64，则进行扩容。
remove的时候如果红黑树节点少于6个，会退化为链表。

hashmap允许key为null，固定放在数组的第0个位置。当然也可能其它元素会存在数组第0个位置。

2、HashMap扩容过程

思路：初始容量、扩容因子、扩容过程
如果不在初始化的时候指定hashmap的容量，那HashMap的默认初始容量是16，扩容因子是0.75，当存储的元素个数超过容量*扩容因子之后，HashMap就会扩容，扩容的过程就是先创建一个新的数组，数组容量为原数组的两倍，然后从原来数组中遍历取出元素，1.7的时候会用hash算法重新计算元素在新数组中的位置，然后将元素放入新数组。1.8之后进行了优化，不需要再重新计算hash值了。这里有个地方需要注意，由于1.7采用的是头插法，原来数组中的链表到了新数组就会整个颠倒过来，采用头插法也是1.7hashmap不线程安全的原因之一，多线程环境下扩容可能造成环，导致get方法陷入死循环，1.8改为了尾插法。

3、HashMap的扩容因子为什么是0.75

个人认为就是一个性能平衡后的结果。我们总是期望没有hash冲突，不会构成单链表，这个时候访问效率最高，但是数组的容量是有限的，当数组快存满的时候出现hash冲突的概率会急剧增高，可以想象以下，假如不设置扩容因子，也就是说只有数组存满的情况下再扩容，在数组存满的最后阶段hash冲突加剧，可能会形成非常长的单链表，访问效率就会急剧下降。反过来考虑，数组位置充足的时候，hash冲突的概率很小，但是始终维持数组位置充足意味着更频繁的扩容操作，比如数组长度是16，如果只存3个元素就扩充一倍，这样出现hash冲突的概率确实最小，但是会造成了大量空间的浪费，并且需要更频繁的扩容，意味着写的效率就会下降。所以我认为0.75是平衡了这两方面考虑之后的一个结果。

4、HashMap的容量为什么总是2的n次方倍，如果初始化时候指定容量不是2的n次方倍会怎么样

hashmap的容量之所以总是2的n次方倍，主要是与它的hash算法有关。HashMap的hash算法是key的hashcode值与上当前容量-1，即hashcode & (length - 1)。这个hash算法很巧妙，如果容量是2的n次方倍，减1之后它的二进制都是1，比如16减1之后是15，15的二进制是4个1，用这个二进制去与hashcode进行与运算，会完整保留hashcode的低四位，而高位都会变成0，这样与运算之后的结果一定是小于等于15的，可以保证不会数组越界。同时我们倾向于认为hashcode是随机均匀的，与出来的结果也会是随机均匀的，这样就可以保证放到数组中的位置也是随机均匀的，减少了hash冲突的概率。当然我们只是倾向认为hashcode就是足够散列的，实际上hashcode并不一定会足够散列，这种情况下hashmap可以做一些额外的处理，如果看过源码就知道，1.7和1.8中hashmap都没有直接用key的hashcode值，而是经过了处理，1.7里面会用一个hash种子来做处理，这个过程就是为了让获取到的的hash值尽量均匀，不给过默认情况下这个hash种子为0，并没有起到作用，需要做额外的设置才能激活（指定一个环境变量，如果hashmap容量大于这个环境变量就会生成一个hash种子）。1.8中取消了hash种子的使用，直接与hashcode的高16位做异或运算。

假如我们指定的容量并不是2的n次方，hashmap会自动计算出比我们指定值大的第一个2的n次方的值，比如我们指定容量是5，那hashmap会选8作为初始容量，如果指定容量是17，hashmap会选32作为初始容量。

5、1.8之后对扩容做了什么优化

主要是不需要进行再hash的计算了，这也是与hash算法有关的，HashMap的hash算法是key的hashcode与上容量-1（hashcode & (length - 1)），由于每次是扩容一倍，比如原来16，16减1等于15，15的二进制是4个1，扩容之后是32，32减1是31，31的二进制是5个1，也就是说每次扩容，相当于二进制高位增加了一个1，这样hashcode值会往高位多保留一位，如果这个多保留的一位刚好是0，那计算的结果和扩容前是一样的，也就是扩容之后位置不变；如果这个多保留的一位刚好是1，这个位置的十进制是2的n-1方（n代表最高位的位置），刚好就是原来的总容量，也就是说扩容之后新的位置就是原位置加上原容量。可以看到，扩容之后只需要根据高一位的hashcode是0还是1就可以确定扩容之后新的位置在什么地方了，所以就不用进行再hash的计算了。

另外一个点就是原来的头插法改为了尾插法，避免了多线程情况下造成环。

6、HashMap为什么不是线程安全的

HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环和数据丢失是在JDK1.7中出现的问题，在JDK1.8中已经得到解决，然而1.8中仍然会有数据覆盖这样的问题。
1.7之前链表采用了头插法，多线程put的时候，可能多个线程都在扩容，扩容的时候有可能会造成环。这个时候去get就会陷入死循环。1.8之后采用了尾插法，不会再出现环的问题了，但是依然有可能造成数据覆盖。
详细：https://blog.csdn.net/swpu_ocean/article/details/88917958

7、hashset底层为什么使用hashmap

在Java有些集合类（HashSet）中要想保证元素不重复可以在每增加一个元素就通过对象的equals方法比较一次，那么当元素很多时后添加到集合中的元素比较的次数就非常多了，也就是说如果集合中现在已经有3000个元素则第3001个元素加入集合时就要调用3000次equals方法，这显然会大大降低效率，于是Java采用了哈希表的原理，这样当集合要添加新的元素时会先调用这个元素的hashCode方法就一下子能定位到它应该放置的物理位置上（实际可能并不是），如果这个位置上没有元素则它就可以直接存储在这个位置上而不用再进行任何比较了，如果这个位置上已经有元素了则就调用它的equals方法与新元素进行比较，相同的话就不存，不相同就散列其它的地址，这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

8、为什么要同时重写equals()和hashcode()方法

Java中规定如果两个对象equals()方法相等则它们的hashCode返回值一定要相同，如果两个对象的hashCode返回值相同，但它们的equals()方法不一定相等。这意味着两个对象的hashCode()方法返回值相等并不能判断这两个对象相等，但如果两个对象的hashcode()方法返回值不相等则可以判定两个对象一定不相等。
当然这并不是一项强制性规定，但是最好就这么做。举个例子，比如我有两个对象，比如A和B，他们并不是同一个对象，hashcode()方法返回值是不一样的，但是我重写了他们两个的equals()方法，A.equals(B)返回true，也就是认为他们两个是相等的，这是如果把A作为HashMap的key放入到HashMap，之后我用B去作为get()方法的参数去获取存取的值，按照直觉应该能获取到才对，因为A和B相等，但实际上是获取不到的，因为A和B的hashcode不相等，而HashMap是使用HashCode来计算散列位置的。

四、ConcurrentHashMap

1、ConcurrentHashMap的基本实现原理

HashMap不是线程安全的，但是散列表有另外一个实现HashTable，它是线程安全的，它在所有涉及到多线程操作的方法上都加上了synchronized关键字来锁住整个HashTable，也就是说所有的线程都在竞争一把锁，可能某两个线程操作的是HashTable中不同的键值对，本来不存在竞争关系，但是因为只有一把锁，所以一个线程获取到了锁，另外一个线程一定会阻塞，这样效率就比较低了。

怎么解决效率问题呢？减小锁的粒度是最合适的方法，1.7的ConcurrentHashMap就是采用分段锁的方式减小锁粒度，降低锁竞争，从而提高效率。1.7的ConcurrentHashMap底层实际上是一个Segment数组，Segement数组的每个元素又是HashMap中的Entry数组结构，Entry数组的元素是单链表结构。加锁的时候只需要对Segment的一个元素加锁就可以了，其他段不需要加锁，这就是分段锁的思路。

如果不指定ConcurrentHashMap的容量和分段数量的话，ConcurrentHashMap默认的分段数量是16，也就是说Segement数组长度为16，我们知道HashMap中Entry数组的长度总是2的n次方，也就是说最小是2，所以ConcurrentHashMap的初始容量是32。ConcurrentHashMap初始化的时候，会在第0个分段中把Entry数组给初始化出来，其它分段则不会初始化，之所以要在第0个分段初始化出来，实际上是作为原型，之后其它分段初始化的时候就不用重新计算Entry数组容量之类的了，直接用第一个分段的属性。

由于有两层数组，1.7的ConcurrentHashMap的put方法和get方法都需要两次Hash寻址，第一次是找到key所在的分段，第二次是找到具体的存储位置。两次hash寻址的算法都是一样的，即hash值与上数组长度减1(hash & (length - 1)) 不同的地方在于第一次hash寻址用的是hash值的高位，而第二次寻址用的是hash值的低位, 但是算法是一样的，所以Segement数组的长度也必须是2的n次方倍。另外分段数量一旦确定之后就不会再改变了，也就是说Segement数组的长度定了之后就不会变了，扩容的话只针对分段里面的Entry数组，是局部扩容，也就是说哪个分段中的Entry数组需要扩容它就自己扩容，不会影响其它分段中Entry数组，另外Segement数组不会扩容。也正是因为这个原因，put方法的第一次寻址是不需要加锁的(初始化分段用unsafe的cas算法)，第一次寻址是找分段，分段不会变所以不需要加锁，只有找到分段了，在分段里面存取元素的时候才需要加锁。这里的锁用的是ReentranLock，实际上是Segement继承了ReentranLock，这里没有使用synchornized同步锁，原因是使用ReentranLock在put元素的时候可以先尝试获取锁，如果没有获取到锁，可以去做一些其它的事情（遍历链表，判断是不是已经存在，不存在会创建一个节点），而如果使用synchornized同步锁就只能阻塞在这里了。

1.7 ConcurrentHashMap不允许value为null；
1.8 ConcurrentHashMap的key和value都不允许为null；

1.8中ConcurrentHashMap也是node+链表+红黑树的实现方式，与1.7已经有很大不同。1.8为了进一步减小锁粒度，已经放弃了分段锁的思路，1.8的ConcurrentHashMap和HashMap的结构已经非常像了，但是它如何保证线程安全呢？1.8如果散列数组位置还是空的，直接用cas操作put值，如果发现不为空，也就是说已经形成了链表或者红黑树，会用synchornized锁住链表头节点或者红黑树的根节点，然后进行操作。

1.8扩容的时候采用了多线程并发扩容的机制，当一个线程put操作的时候发现当前正在扩容，如果符合条件则会加入到扩容的行列中去。ConcurrentHashMap用了一个int类型的sizeCtl变量来表示当前状态，如果是0表示未初始化，或者未初始化完成；是-1表示正在初始化，只允许一个线程进行初始化；初始化完成则是一个正整数，实际上是当前容量*加载因子的值，也就是下一次扩容的阈值；如果正处于扩容过程，sizeCtl是一个负值，低16位代表当前有几个参与扩容的线程。每个扩容的线程负责一段区域进行扩容，如果一个线程发现正在扩容并且并发扩容线程数没有达到最大值就会加入扩容的线程，同样的如果一个线程自己的扩容任务结束了也还会判断是否还有区段可以扩容，如果有还会继续进行新区段的扩容。多个线程并发搬运时，如果是首个搬运线程，负责nextTable（扩容后的数组）的初始化工作；然后从当前table的n-1槽位开始依次向低位扫描搬运，通过CAS操作一次获取一个区段（默认是16），如果不再能够获取到新的区段，线程开始退出，退出时会在sizeCtl上将总的线程数减一，最后一个退出的线程将扫描坐标i回退到最高位，强迫做一次抄底的全局扫描。

总结：
1.8引入并发transfer的机制支持多线程搬运，写操作和transfer操作在不同bin上可并行（transfer操作与写操作都要竞争bin的头节点的syncronized锁，两者是互斥串行的，所以不会有线程安全问题）。引入ForwardingNode支持读操作和transfer并行，并进一步支持transfer过程有可能存在的哈希表链的遍历。引入ReserveNode在compute原子计算可能耗时较长的情况下抢先占位，避免重复计算。
1.8引入红黑树来优化哈希冲突时的检索性能，其内部实现了轻量级的读写锁保证读写安全，在线性检索和tree检索之间做了智能切换，达到了性能与安全的极佳的平衡。引入CounterCell机制优化多核场景的计数，解决内存伪共享问题。

参考：https://mp.weixin.qq.com/s/4sz6sTPvBigR_1g8piFxug

2、ConcurrentHashMap的get方法为什么不需要加锁

1.7和1.8的ConcurrentHashMap都没有加锁，原因是Get方法只是读操作，多线程环境下只需要考虑会不会读到脏数据的问题，所以不用加锁，只需要使用volitile关键字就可以了，它可以保证修饰变量的可见性，在HashEntry(1.7)或者Node(1.8)节点的value和next都使用了volitile关键字，1.7中读取的时候使用的是unsafe类，原子性读取。
1.8中，由于用了volitile修饰，如果此时读到数组元素为null，直接返回null，如果读到是一个节点，不管是链表节点还是红黑树节点，都代表当前没有进行扩容，或者扩容还没有到这个位置，就算之后扩容到了这个位置，扩容结束之前也不会改变其结构，所以照常遍历旧的链表和红黑树结构结构就可以了；如果读到的是一个forwadingNode，代表这个位置已经扩容结束，会调用到forwadingNode的find方法到新表中去递归查询。不管哪一种情况都不会有并发安全问题。

  1. // 1.7 HashEntry结构
  2. static final class HashEntry<K,V> {
  3.     final int hash;
  4.     final K key;
  5.     volatile V value;
  6.     volatile HashEntry<K,V> next;
  7. }
  9. // 1.8 Node结构
  10. static class Node<K,V> implements Map.Entry<K,V> {
  11.     final int hash;
  12.     final K key;
  13.     volatile V val;
  14.     volatile Node<K,V> next;
  15. }

3、JDK1.7的ConcurrentHashMap的size()方法和JDK1.8有什么区别

1.7和1.8都是每put一个元素就进行计数。
1.7中先不加锁累加每个分段的数量，这样计算至少两次，如果两次数量一样就直接返回，如果不一样还会再计算一次，也就是总共三次，如果三次都不一样就会遍历每个分段，给每个分段加锁，然后累加每个分段的数量，解锁再返回。

1.8中采用了分段计数的方式，就是用一个额外的分段数组来保存分段中的容量，每一个分段被称为CounterCell。然后还有一个baseCount来记录容量，如果put或remove不存在竞争就直接原子性操作一个long类型的baseCount来计数。而如果存在竞争（cas操作baseCount失败），则会到对应CounterCell中计数，CounterCell是一个数组，竞争激烈的时候也会进行扩容，最后计算总的size()的时候就是baseCount+所有CounterCell中的value。

4、ConcurrentHashMap一定线程安全吗？

ConcurrentHashMap的单操作都是线程安全的，但是复合操作需要程序员自己控制线程安全性。

五、LinkedHashMap与LRU算法

LinkedHashMap的Entry继承了HashMap的Entry，在此基础上增加了before和after引用，也就是说LinkedHashMap它保持了HashMap的结构，依然是一个数组，用拉链法解决Hash冲突，链太长也会转换为红黑树。但是它在维持HashMap结构的同时还把每个节点构造成了一个双链表，每put一个key/value键值对，会生成一个Entry节点，除了维护HashMap的结构，还会把这个Entry节点插入到双链表的结尾。遍历的时候直接用双链表来遍历，默认情况下，遍历的顺序就是节点插入的顺序，但是如果在初始化LinkedHashMap的时候指定accessOrder为true，当我们调用get方法的时候，会把这个节点从双链表中删除，然后插入到双链表的尾部；如果put一个新节点，会将新节点插到队尾，如果put的时候是覆盖一个原有的节点，也会把这个节点从双链表中删除，然后插入到双链表的尾部。

根据LinkedHashMap的特性，我们可以实现LRU算法，LRU即最近最少使用算法(Least Recently Used)，是一种缓存淘汰算法，指的是最近访问的元素下次访问的概率也会更高，而很久没访问的元素，以后访问到的概率也会更低，如果超过一定时间或一定容量，就把最久未访问的节点淘汰掉。如果设置LinkedHashMap的accessOrder为true，双链表的队尾就是最近访问的节点，队首为最久未访问的节点，只要淘汰掉队首的节点就可以了。LinkedHashMap贴心的为我们准备了removeEdlestEntry()方法，该方法默认返回false，也就是不淘汰节点，我们可以重写这个方法，当达到某个条件（比如超过了一个指定的容量）就返回true，这个时候就会淘汰掉队首的节点。另外本身LinkedHashMap是一个HashMap，随机访问会更方便，但如果要遍历，它是从队首向队尾遍历，其实不太符合LRU算法的思路，所以我们还要实现一个遍历器，从队尾往队首遍历（比如实现一个ListIterator）。

六、TreeMap和ConcurrentSkipListMap

我们知道HashMap底层是数组，通过hash算法将key的hashcode映射到数组下标，所以数组存储的数据是乱序的。如果我们需要一个key有序的键值对存储结构该怎么办呢？
其实实现思路有多种，甚至用朴素的链表和数组结构也能实现，只是put、get、remove的效率可能会慢，比如用数组和链表维持key有序，那么put的时候一定是先找到要put的位置，对于数组来说可以使用二分搜索，时间复杂度为O(logn)，但put的时候要移动元素，所以总时间复杂度还是O(n)；如果是链表则只能遍历找到put的位置，时间复杂度也是O(n)；那有没有更好的数据结构呢，我们想到了二叉搜索树，但是二叉搜索树在特殊情况下可能会退化为一个链表的情况，这基础上就有了平衡二叉树，平衡二叉树不会出现退化成链表的情况，但是要频繁维护平衡结构；在这之上就有了红黑树，红黑树牺牲了严格的高度平衡，它只要求部分达到平衡就可以，降低了维护平衡结构的消耗，从而提高了性能。所以红黑树就成了key有序键值对存储结构的最优选择，而TreeMap就是如此。

回顾一下HashMap的特性，HashMap设计的时候尽量保证能在O(1)的时间内进行put、get、remove操作，性能非常好，但是没办法保证key有序排列。为了保证key有序排列，选择了红黑树的存储结构，红黑树的put、get、remove操作都是O(logn)的时间复杂度，世上没有两全法，要达到key有序只能牺牲一些性能。

我们再来回顾一下二叉查找数、平衡树(AVL树)和红黑树：

  1. 二叉查找树：
  2. 特点：左孩子的节点值都比父节点小，右孩子的节点值都比父节点大，同时左右子树也都是二叉查找树（中序遍历结果是排序结果）
  3. 缺点：特殊情况下可能会退化为链表
  5. 平衡树：
  6. 特点：平衡树是一种特殊的二叉查找树，它具有二叉查找树的所有性质，但是平衡树的左右子树高度差最多为1，这个性质保证平衡树不会退化为链表，同时左右子树高度平衡，查询效率是最好。
  7. 缺点：平衡树要求左右子树高度差最多为1，这个条件过于苛刻了，以至于几乎每次put或者remove都会破坏这个条件，需要频繁旋转来调整到平衡状态，这使得插入和删除的性能大打折扣
  9. 红黑树：
  10. 特点：红黑树也是一种特殊的二叉查找树，也具有二叉查找树的所有性质，但是它不要求左右子树高度差必须为1，而是通过一些其它的定义来保证左右子树有一个相对宽松的平衡度，在put和remove的时候同样也可能会破坏平衡结构，但是都可以在三次旋转之内解决。所以实际上就是牺牲了一些平衡性(牺牲平衡性就是牺牲了平均查询效率)，但是提升了put和remove的性能，实际上是二叉查找树和平衡树的中和。

除了TreeMap，java还有一种key有序的键值对存储结构，就是ConcurrentSkipListMap，我们知道TreeMap是非线程安全的，那线程安全的key有序键值对存储结构就是ConcurrentSkipListMap，它的底层用的不是红黑树，而是跳表。跳表是一种典型的空间换时间的结构，我们知道用链表维持有序结构，在get的时候需要遍历，时间复杂度是o(n)，那如何在链表上实现类似二分查找的操作呢？答案就是维护一些额外的结构，这些额外的结构可以增加查询的效率，相对而言也会增加空间的占用。对于跳表而言这个额外的结构仍然是链表，只是额外的链表只存储原始链表中一部分的值，访问的时候先访问额外链表，访问额外链表的一个节点相对原始链表来说就是一次跨越多个节点的访问，如图所示：
1、跳表结构

跳表的put、get、remove操作平均时间复杂度也是o(logn)，几乎可以和红黑树持平，但是在并发情况下更有优势，插入、删除或者更新等操作相对而言牵扯到的节点数更少，所以锁竞争也更少，但是红黑树维护平衡性的时候会操作大量节点，锁竞争会更大，这也是线程安全情况下使用的是跳表而不是红黑树的原因。

七、TreeMap与一致性Hash

6.1 普通hash算法在分布式系统中的不足

在分布式的存储系统中，要将数据存储到具体的节点上，如果我们采用普通的hash算法进行路由，将数据映射到具体的节点上，如key%N，key是数据的key，N是机器节点数，如果有一个机器加入或退出这个集群，由于N的变化，之后计算的Hash值都将产生变化，所有的数据映射都无效了。这种情况下如果是持久化存储就需要做数据迁移，如果是分布式缓存，则原有的缓存就失效了。

6.2 一致性Hash算法

一致性Hash算法通过一个叫做一致性Hash环的数据结构实现Key到缓存服务器的Hash映射。具体算法过程为：先构造一个长度为2^32的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 2^32-1]）将缓存服务器节点放置在这个Hash环上，然后根据需要缓存的数据的Key值计算得到其Hash值（其分布也为[0, 2^32-1]），然后在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。采用一致性Hash算法，如果有新的机器加入或者退出也的确还会影响集群，但是影响的只是加入的节点逆时针的那一段，相比余数Hash算法影响了远超一半的影响率，这种影响要小得多。更重要的是，集群中缓存服务器节点越多，增加节点带来的影响越小，也就是说随着集群规模的增大，继续命中原有缓存数据的概率会越来越大，虽然仍然有小部分数据缓存在服务器中不能被读到，但是这个比例足够小，即使访问数据库，也不会对数据库造成致命的负载压力。

6.3 为什么使用红黑树

一致性Hash算法最先要考虑的一个问题是：构造出一个长度为2^32的整数环，根据节点名称的Hash值将服务器节点放置在这个Hash环上。
可以先考虑有序链表的方式，将服务器节点的hash值计算出来，然后从小到大排序，然后计算要存储数据key的hash值，然后去链表中找到具体的服务器节点存储进去。但是这样需要遍历链表，时间复杂度是O(n)。
所以可以看出关键在于有序的结构中找到一个节点，除了有序链表很自然就想到了红黑树。红黑树本身就是存储有序数据的数据结构，找到一个节点的时间复杂度是O(logn).

6.4 一致性算法的倾斜问题

一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题。解决这个问题的办法是引入虚拟节点，将一个物理节点拆分为多个虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上（每个物理节点的虚拟节点数量可能不一样），如果某个数据映射到虚拟节点，之后只要根据虚拟节点和物理节点的映射找到物理节点，最终还是将数据存储在物理节点。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注