面试准备之Java集合(二)-阿里云开发者社区

17、数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用 Array 而不是 ArrayList？

数组可以包含基本数据类型和引用类型，ArrayList 只能包含引用类型。注意：Array 数组在存放的时候一定是同种类型的元素。ArrayList 就不一定了，因为 ArrayList 可以存储 Object。

数组空间大小是固定的，但 ArrayList 空间大小是动态变化的，初始化的时候没有定义它的默认容量大小，那么默认是 10，超出限制时会增加50%的容量，每次扩容都底层采用 System.arrayCopy()复制到新的数组

ArrayList 是 List 接口的实现类，相比数组支持更多的方法和特性。

适用场景：

当集合长度固定时，使用数组；当集合的长度不固定时，使用 ArrayList。
由于 ArrayList 不支持基本数据类型，所以保存基本数据类型时需要装箱处理，对比数组性能会下降。这种情况尽量使用数组。
数组支持的操作方法很少，但内存占用少，如果只需对集合进行随机读写，选数组

18、ArrayList 和 LinkedList 有什么区别？

ArrayList 和 LinkedList 都实现了 List 接口，他们有以下的不同点：

ArrayList 是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问，适合元素查找。与此对应，LinkedList 基于链表，为双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是 O(n)。

相对于 ArrayList，LinkedList 增删操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。

LinkedList 比 ArrayList 更占内存，因为 LinkedList 为每一个节点存储了两个引用，一个指向前一个元素，一个指向后一个元素。

19、CopyOnWriteArrayList 相关知识

采用 ReentrantLock 来加锁，保证同一时刻只有一个线程在对数据进行读写操作；
数组引用是 volatile 修饰的，因此将旧的数组引用指向新的数组，根据 volatile 的 happens-before 规则，写线程对数组引用的修改对读线程是可见的的，但是数组中的元素并不可见。
由于在写数据的时候，是在新的数组中插入数据的，从而保证读写是在两个不同的数据容器中进行操作。

CopyOnWriteArrayList 的缺点：

内存占用问题：因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比如说 200M 左右，那么再写入 100M 数据进去，内存就会占用 300M，那么这个时候很有可能造成频繁的 minor GC 和 major GC。
数据一致性问题：CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用 CopyOnWrite 容器。

CopyOnWriteArrayList 的优点：

线程安全，能够保证数据一致性。
与 Vector、ArrayList 相比，CopyOnWriteArrayList 在多线程遍历迭代过程中不会报错。

20、Comparable 和 Comparator 接口是干什么的？列出它们的区别。

Comparable & Comparator 都是用来实现集合中元素的比较、排序的。

Comparable 接口（内部比较器）：

Comparable 位于 java.lang 包下。
comparable 接口是在内部类通过重写 compareTo 方法实现的。在使用 Collections.sort(List list)或者Array.sort(Object[] a)对对象集合进行排序的时候，就会根据对象自定义的排序方法排序。
comparable 接口实现较简单，但对于多元素排序不方便，因为在重写 compareTo 方法时事先定义好了元素比较顺序
使用 Comparable 方式比较时，我们将比较的规则写入了比较的类型中，其特点是高内聚。但如果哪天这个规则需要修改，那么我们必须修改这个类型的源代码。

Comparator 接口（外部比较器）：

Comparator 位于 java.util 包下。
comparator 接口则是在外部类通过重写 compare 与 equals 方法实现的。
comparator 接口实现较复杂，可能定义多个外部类，但对于多元素比较使用起来很方便。
使用 Comparator 方式比较，那么我们不需要修改比较的类，其特点是易维护，但需要自定义一个比较器，后续比较规则的修改，仅仅是改这个比较器中的代码即可。

21、什么是 Java 优先级队列(Priority Queue)？

PriorityQueue 的逻辑结构是一棵完全二叉树，存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组。

PriorityQueue 是一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。在创建的时候，我们可以给它提供一个负责给元素排序的比较器。PriorityQueue 不允许 null 值，因为他们没有自然顺序，或者说他们没有任何相关联的比较器。最后，PriorityQueue 不是线程安全的，入队和出队的时间复杂度是 O(log(n))。

22、Java集合类框架的最佳实践有哪些？

23、HashSet 和 TreeSet 有什么区别？

Hashset 的底层是由哈希表实现的，Hashset 中的元素是无序的。add()，remove()，contains()方法的时间复杂度是 O(1)。

Treeset 底层是由红黑树实现的。如果需要在 Treeset 中插入对象，需要实现 Comparable 接口，重写 compareTo 方法。

24、HashSet 的实现原理？

HashSet 底层由 HashMap 实现
HashSet 的值存放于 HashMap 的 key 上
HashMap 的 value 统一为 PRESENT

25、如何实现数组和 List 之间的转换？

List 转换成为数组：调用 ArrayList 的 toArray 方法。

数组转换成为 List：调用 Arrays 的 asList 方法。

26、Arrays.asList()使用指南

String[] myArray = { "Apple", "Banana", "Orange" }； 
List<String> myList = Arrays.asList(myArray);
//上面两个语句等价于下面一条语句
List<String> myList = Arrays.asList("Apple","Banana", "Orange");
复制代码

注意：使用工具类 Arrays.asList()把数组转换为集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。说明：asList 的返回对象是一个 Arrays 内部类，并没有实现集合的修改方法。Arrays.asList 体现的是适配器模式，只是转换接口，后台的数据仍是数组。

String[] str = new String[]{"and","you"};
List list = Arrays.asList(str);
System.out.println(list.get(1));//输出you
list.add("yes");//抛出异常
str[0] = s"yes";
System.out.println(list);//list也会发生改变，输出[yes, you]
复制代码

Arrays.asList()是泛型方法，传入的参数对象必须是对象数组。

int[] myArray = { 1, 2, 3 };
List myList = Arrays.asList(myArray);
System.out.println(myList.size());//1
System.out.println(myList.get(0));//数组地址值
System.out.println(myList.get(1));//报错：ArrayIndexOutOfBoundsException
int [] array=(int[]) myList.get(0);
System.out.println(array[1]);//1
复制代码

当传入一个原生数据类型数组时，Arrays.asList() 的真正得到的参数就不是数组中的元素，而是数组对象本身！此时List 的唯一元素就是这个数组，这也就解释了上面的代码。

转换为包装数据类型即可。

Integer[] myArray = { 1, 2, 3 };
List myList = Arrays.asList(myArray);
System.out.println(myList.size());//数组长度3
System.out.println(myList.get(0));//1
System.out.println(myList.get(1));//2
复制代码

使用集合的修改方法:add()、remove()、clear()会抛出异常。

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类,这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

List myList = Arrays.asList(1, 2, 3);
System.out.println(myList.getClass());//class java.util.Arrays$ArrayList
复制代码

如何正确的将数组转换为ArrayList?

1、自定义代码

static <T> List<T> arraysToList(T[] array){
    List<T> list = new ArrayList<T>(array.length);
    for(T obj:array){
        list.add(obj);
    }
    return list;
}
String[] str = new String[]{"and","you"};
List ll = arraysToList(str);
System.out.println(ll.getClass());//class java.util.ArrayList
int[] myArray = { 1, 2, 3 };
List ll2 = arraysToList(myArray);//编译报错
复制代码

该方法暂不支持基本数据类型。

2、最简便的方法(推荐)

List list = new ArrayList<>(Arrays.asList("a", "b", "c"))
复制代码

3、使用 Java8 的 Stream(推荐)

Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).collect(Collectors.toList());
//基本类型也可以实现转换（依赖boxed的装箱操作）
int [] myArray2 = { 1, 2, 3 };
List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());
复制代码

4、使用 Guava(推荐)

对于可变集合，你可以使用 Lists 类及其 newArrayList()工厂方法：

String[] str = {"acd","yes"};
List list = Lists.newArrayList(str);//class java.util.ArrayList
int[] myArray = { 1, 2, 3 };
list = Lists.newArrayList(myArray);//class java.util.ArrayList
复制代码

5、使用 Apache Commons Collections

List<String> list = new ArrayList<String>();
CollectionUtils.addAll(list, str);
复制代码

27、Collection.toArray()方法使用的坑&如何反转数组

该方法是一个泛型方法： T[] toArray(T[] a); 如果 toArray 方法中没有传递任何参数的话返回的是 Object 类型数组。

String [] s= new String[]{
    "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.asList(s);//class java.util.Arrays$ArrayList
Collections.reverse(list);
s=list.toArray(new String[0]);//没有指定类型的话会报错，s2类型为String
Object[] s2 = list.toArray();//效果同上
list = Lists.newArrayList(s);//class java.util.ArrayList
Collections.reverse(list);
s = list.toArray(new String[0]);
Object[] s2 = list.toArray(new String[0]);//s2类型为String，不指定类型，s2则为Object类型
复制代码

综上可知，当数组为引用类型数组时，使用 Arrays.asList 转换为 List，反转操作后，再转换为数组，无论 toArray()方法中是否有参数，声明为 Object 类型的数组实际类型都为原引用类型。使用其他数组转 List 方法，比如 Lists.newArrayList，需要在 toArray()参数中传入对应类型，最后得到的数组类型也是原类型。

当数组为基本数据数组时，最后转换之后得到的数组为 Object 类型。

28、ArrayList 和 Vector 的区别是什么？

Vector 是线程安全的，ArrayList 不是线程安全的。
ArrayList 在底层数组不够用时在原来的基础上扩展 0.5 倍，Vector 是扩展 1 倍。
ArrayList 更加通用，因为线程安全需要更大的系统开销。

29、在 Queue 中 poll()和 remove()有什么区别？

poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。

30、JDK1.8之后ConcurrentHashMap为什么使用synchronized而不用lock?

减少内存开销假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。

获得 JVM 的支持可重入锁毕竟是API这个级别的，后续的性能优化空间很小。 synchronized 则是 JVM 直接支持的，JVM 能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得 synchronized 能够随着 JDK 版本的升级而不改动代码的前提下获得性能上的提升。具体而言： JVM 使用了锁升级的优化方式，就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为 CAS 轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。

31、JDK1.7中 ConcurrentHashMap实现原理

数据结构

jdk1.7中采用Segment + HashEntry的方式进行实现，结构如下：

ConcurrentHashMap 的主干是个 Segment 数组，Segment 继承了 ReentrantLock，所以它就是一种可重入锁（ReentrantLock)。在 ConcurrentHashMap，一个 Segment 就是一个子哈希表，Segment 里维护了一个HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。并发环境下，对于不同 Segment 的数据进行操作是不用考虑锁竞争的。

put 方法

并发情况下 put 方法实现，主要逻辑也就两步：1.定位 segment 并确保定位的 Segment 已初始化 2.调用 Segment 的 put 方法。

场景：线程A和线程B同时执行相同Segment对象的put方法

1、线程A执行tryLock()方法成功获取锁，则把HashEntry对象插入到相应的位置； 2、线程B获取锁失败，则执行scanAndLockForPut()方法，在scanAndLockForPut方法中，会通过重复执行tryLock()方法尝试获取锁，在多处理器环境下，重复次数为64，单处理器重复次数为1，当执行tryLock()方法的次数超过上限时，则执行lock()方法挂起线程B； 3、当线程A执行完插入操作时，会通过unlock()方法释放锁，接着唤醒线程B继续执行；

关于 scanAndLockForPut() 方法深入理解：

它首先会调用entryForHash()，根据hash值获取”当前Segment中对应的HashEntry节点(first)，即找到对应的HashEntry链表“。

紧接着进入while循环。在while循环中，它会遍历”HashEntry链表(e)“，查找”要插入的key-value键值对“在”该HashEntry链表上对应的节点“。

若找到的话，则不断的自旋，即不断的执行while循环。在自旋期间，若通过tryLock()获取锁成功则返回；否则，在自旋MAX_SCAN_RETRIES次数之后，强制获取锁并退出。

若没有找到的话，则新建一个HashEntry链表，然后不断的自旋。在自旋期间，若通过tryLock()获取锁成功则返回；否则，在自旋MAX_SCAN_RETRIES次数之后，强制获取锁并退出。

此外，若在自旋期间，HashEntry链表的表头发生变化；则重新进行查找和自旋工作！

get方法

get 方法无需加锁，由于其中涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以不会读取到过期数据。

size实现

先采用不加锁的方式，连续计算元素的个数，最多计算3次： 1、如果前后两次计算结果相同，则说明计算出来的元素个数是准确的； 2、如果前后两次计算结果都不同，则给每个Segment进行加锁，再计算一次元素的个数；

32、JDK1.8中 ConcurrentHashMap实现原理

数据结构

1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，结构如下：

ConcurrentHashMap 取消了Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

ConcurrentHashMap 在构造函数中只会初始化 sizeCtl 值，并不会直接初始化 table，而是延缓到第一次 put 操作。

ConcurrentHashMap的红黑树实现分析

initTable实现

table 初始化操作会延缓到第一次 put 行为。但是 put 是可以并发执行的，那么如何实现 table 只初始化一次的？

通过源码可知，sizeCtl 默认为0，如果 ConcurrentHashMap 实例化时有传参数，sizeCtl 会是一个2的幂次方的值。所以执行第一次 put 操作的线程会执行 Unsafe.compareAndSwapInt 方法修改 sizeCtl 为-1，有且只有一个线程能够修改成功，其它线程通过 Thread.yield()让出CPU时间片等待 table 初始化完成。

put实现

当执行put方法插入数据时，首先计算 key 的 hash 值，通过 spread() 获取，然后判定 Node 数组是否为空，若不为空，根据得到的 hash 值，在Node数组中找到相应的位置，实现如下：

1、如果相应位置的Node还未初始化，则通过CAS插入相应的数据；

如果 CAS 成功，说明 Node 节点已经插入，随后 addCount(1L, binCount)方法会检查当前容量是否需要进行扩容。
如果 CAS 失败，说明有其它线程提前插入了节点，自旋重新尝试在这个位置插入节点。

2、如果相应位置的Node不为空，且 hash 值为 -1，说明当前 Node 是 ForwardingNode 节点，意味有其它线程正在扩容，则一起进行扩容操作。

3、如果相应位置的Node不为空，且当前该节点不处于移动状态，则对该节点加synchronized锁，synchronized 只锁定当前链表或红黑二叉树的首节点，如果该节点的hash不小于0，则遍历链表更新节点或插入新节点；

4、如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点；

5、如果当前链表的个数达到 8 个，则通过treeifyBin方法转化为红黑树。同时会判断 put 操作为新增还是更新操作，若为更新操作，则更新

value 值并返回旧值，否则执行 addCount()方法，返回 null 值。

扩容

何时扩容？

当前容量达到阈值 s >= (long)(sc = sizeCtl)；
当链表中元素个数超过默认设定（8个），当数组的大小还未超过64的时候，此时进行数组的扩容，如果超过则将链表转化成红黑树；
在 putVal 方法发现其他线程扩容时，帮其扩容。

当 table 容量不足的时候，即 table 的元素数量达到容量阈值 sizeCtl，需要对 table 进行扩容。

多线程之间，以 volatile 的方式读取 sizeCtl 属性，来判断 ConcurrentHashMap 当前所处的状态。通过 CAS 设置 sizeCtl 属性，告知其他线程 ConcurrentHashMap 的状态变更。

不同状态，sizeCtl 所代表的含义也有所不同。

未初始化：

sizeCtl=0：表示没有指定初始容量。
sizeCtl>0：表示初始容量。

初始化中：

sizeCtl=-1,标记作用，告知其他线程，正在初始化

正常状态：

sizeCtl=0.75n ,扩容阈值

扩容中:

sizeCtl < 0 : 表示有其他线程正在执行扩容
sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2 :表示此时只有一个线程在执行扩容

ConcurrentHashMap 的状态图如下：

上述内容来源于：ConcurrentHashMap源码分析（JDK8）扩容实现机制

关于扩容过程的分析，网上的文章都不是很全面，不过多篇文章结合着看，还是有所帮助的。首先推荐并发编程——ConcurrentHashMap#transfer() 扩容逐行分析，本文对于 transfer 方法的讲解很详细，后续的图像讲解也不错。另外还可以参考狼哥的深入分析ConcurrentHashMap1.8的扩容实现，不过我对于其中部分内容不是很认同，所以我接下来自己好好研究了源码，然后进行如下代码测试。

测试案例：

public static void main(String[] args) {
    Map<Integer,Object> map = null;
    map = new ConcurrentHashMap<>();
    map.put(7, "");
    map.put(11, "");
    map.put(43, "");
    map.put(59, "");
    map.put(19, "");
    map.put(3, "");
    map.put(1, "");
    map.put(35, "");
    map.put(51, "");
    map.put(67, "");
    map.put(83, "");
    System.out.println("遍历结果：");
    for (Integer key : map.keySet()) {
        System.out.print(key + " -> ");
    }
}
复制代码

上述代码的执行结果为：

1 -> 19 -> 3 -> 35 -> 51 -> 67 -> 83 -> 7 -> 11 -> 43 -> 59 ->
复制代码

对应下图所示：

下表为上述节点数据转换为二进制后的信息：

十进制数	二进制	二进制中第5位（从右往左）
1	0000001	0
19	0010011	1
3	0000011	0
35	0100011	0
51	0110011	1
67	1000011	0
83	1010011	1
99	1100011	0
7	0000111	0
11	0001011	0
43	0101011	0
59	0110111	1

目前集合中有11个节点，如果此时再增加一个节点，将会触发扩容。在上述代码上增加下述代码：

map.put(99, "");
复制代码

重新执行效果如下：

1 -> 67 -> 35 -> 3 -> 99 -> 7 -> 43 -> 11 -> 83 -> 51 -> 19 -> 59
复制代码

图形效果展示：

size实现

1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount 。

1、初始化时counterCells为空，在并发量很高时，如果存在两个线程同时执行CAS修改baseCount值，则失败的线程会继续执行方法体中的逻辑，使用CounterCell记录元素个数的变化；

2、如果CounterCell数组counterCells为空，调用fullAddCount()方法进行初始化，并插入对应的记录数，通过CAS设置cellsBusy字段，只有设置成功的线程才能初始化CounterCell数组；

3、如果通过CAS设置cellsBusy字段失败的话，则继续尝试通过CAS修改baseCount字段，如果修改baseCount字段成功的话，就退出循环，否则继续循环插入CounterCell对象；

所以在1.8中的size实现比1.7简单多，因为元素个数保存baseCount中，部分元素的变化个数保存在CounterCell数组中，通过累加baseCount和CounterCell数组中的数量，即可得到元素的总个数。

33、红黑树学习

红黑树是一种自平衡的二叉查找树，主要用它存储有序的数据，提供高效的数据检索，时间复杂度为O(lgn)，每个节点都有一个标识位表示颜色，红色或黑色。

红黑树特性：

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树应用：

在 JDK1.8 中，HashMap 和 ConcurrentHashMap 用到了红黑树，TreeMap 和 TreeSet 底层也是红黑树实现的。

推荐阅读：漫画：什么是红黑树？

注意事项：

1、在新插入节点的时候，为什么待插入的节点是红色？

答：如果插入节点是黑色，就一定会违背每条查找线上黑色节点个数一致的规则，插入红色，就可能不需要变色或者旋转，所以待插入节点都是红色。

34、深入源码学习

对集合类的深入学习必须研读源码，才能有更加深刻的认识，鉴于网上对相关源码的解读文章很多，所以没必要重复造轮子，结合文章阅读源码，同时可以结合案例进行调试，查看代码的具体执行流程。以下文章是对应每个集合类的深入学习参考文章，希望能对大家有所帮助。

ArrayList深入学习

Java Collections Framework - ArrayList

面试必备：ArrayList源码解析（JDK8）

搞懂 Java ArrayList 源码

总结：

ArrayList 底层是一个动态扩容的数组结构，默认第一次插入元素时创建数组的大小为10 ，每次扩容需要增加0.5倍的容量；

ArrayList 扩容底层是通过 Arrays.CopyOf 和 System.arraycopy 来实现的。每次都会产生新的数组，和数组中内容的拷贝，所以会耗费性能，所以在多增删的操作的情况可优先考虑 LinkList 而不是 ArrayList；

ArrayList 的 toArray 方法重载方法的使用；

允许存放（不止一个） null 元素；

允许存放重复数据，存储顺序按照元素的添加顺序；

ArrayList 并不是一个线程安全的集合。如果集合的增删操作需要保证线程的安全性，可以考虑使用 CopyOnWriteArrayList 或者使collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类；

不正确访问集合元素的时候 ConcurrentModificationException和

java.lang.IndexOutOfBoundsException 异常产生的时机和原理；

增删改查中，增导致扩容，则会修改modCount，删一定会修改。 改和查一定不会修改modCount。

LinkedList深入学习

java基础：LinkedList — 源码分析

LinkedList 是双向列表，能存储多个 null 值；

链表批量增加，是靠 for 循环遍历原数组，依次执行插入节点操作。对比 ArrayList 是通过 System.arraycopy完成批量增加的。新增操作一定会修改 modCount；

通过下标获取某个 node 的时候，会根据 index 处于前半段还是后半段进行一个折半，以提升查询效率；

删除操作也一定会修改 modCount。按下标删，也是先根据 index 找到 Node，然后去链表上 unlink 掉这个Node。按元素删，会先去遍历链表寻找是否有该Node，如果有，去链表上unlink掉这个Node；

修改操作也是先根据 index 找到 Node，然后替换值。修改操作不修改 modCount；

查询操作本身就是根据 index 找到 Node；

LinkedList 不光能够向前迭代，还能像后迭代，不光能当链表，还能当队列、栈使用。

HashMap深入学习

史上最详细的 JDK 1.8 HashMap 源码解析

Java 8系列之重新认识HashMap

HashMap 源码详细分析(JDK1.8)

总结：

HashMap 的底层是个 Node 数组（Node[] table），在数组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。

增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到 key 的 hashCode 值；2）将 hashCode 的高位参与运算，重新计算 hash 值；3）将计算出来的 hash 值与 “table.length - 1” 进行 & 运算。

HashMap 的默认初始容量（capacity）是 16，capacity 必须为 2 的幂次方；默认负载因子（load factor）是 0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity * loadfactor。

HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。

导致 HashMap 扩容后，同一个索引位置的节点重 hash 最多分布在两个位置的根本原因是：1）table的长度始终为 2 的 n 次方；2）索引位置的计算方法为 “(table.length - 1) & hash”。HashMap 扩容是一个比较耗时的操作，定义 HashMap 时尽量给个接近的初始容量值。

HashMap 有 threshold 属性和 loadFactor 属性，但是没有 capacity 属性。初始化时，如果传了初始化容量值，该值是存在 threshold 变量，并且 Node 数组是在第一次 put 时才会进行初始化，初始化时会将此时的 threshold 值作为新表的 capacity 值，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。

当同一个索引位置的节点在增加后达到 8 个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next 属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin 方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。

当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify 方法。

HashMap 在 JDK 1.8 之后不再有死循环的问题，JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。

HashMap 是非线程安全的，在并发场景下使用 ConcurrentHashMap 来代替。

LinkedHashMap深入学习

LinkedHashMap 源码详细分析（JDK1.8）

总结：

在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构，并实现了不同的功能。HashMap 底层基于拉链式的散列结构，并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构，HashMap 可提供高效的增删改查操作。LinkedHashMap 在其之上，通过维护一条双向链表，实现了散列数据结构的有序遍历。TreeMap 底层基于红黑树实现，利用红黑树的性质，实现了键值对排序功能。

总结：

元素没有顺序

元素不能重复，集合元素可以是null,但只能放入一个null

非线程安全。

HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以 equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false。所以如果存储自定义对象，需要重写自定义对象的 hashcode 方法和 equals 方法。

TreeSet 可以确保集合元素处于排序状态。TreeSet 支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。

LinkedHashSet 集合同样是根据元素的 hashCode 值来决定元素的存储位置，但是它同时使用链表维护元素的次序,当遍历该集合时候，LinkedHashSet 将会以元素的添加顺序访问集合的元素。LinkedHashSet 创建的时候只会创建以插入顺序排序的 LinkedHashMap。

面试准备之Java集合(二)

17、数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用 Array 而不是 ArrayList？

18、ArrayList 和 LinkedList 有什么区别？

19、CopyOnWriteArrayList 相关知识

20、Comparable 和 Comparator 接口是干什么的？列出它们的区别。

21、什么是 Java 优先级队列(Priority Queue)？

22、Java集合类框架的最佳实践有哪些？

23、HashSet 和 TreeSet 有什么区别？

24、HashSet 的实现原理？

25、如何实现数组和 List 之间的转换？

26、Arrays.asList()使用指南

27、Collection.toArray()方法使用的坑&如何反转数组

28、ArrayList 和 Vector 的区别是什么？

29、在 Queue 中 poll()和 remove()有什么区别？

30、JDK1.8之后ConcurrentHashMap为什么使用synchronized而不用lock?

31、JDK1.7中 ConcurrentHashMap实现原理

数据结构

put 方法

get方法

size实现

32、JDK1.8中 ConcurrentHashMap实现原理

数据结构

initTable实现

put实现

扩容

size实现

33、红黑树学习

34、深入源码学习

ArrayList深入学习

LinkedList深入学习

HashMap深入学习

LinkedHashMap深入学习

ConcurrentHashMap JDK1.7深入学习

ConcurrentHashMap JDK1.8深入学习

HashSet深入学习

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

面试准备之Java集合(二)

17、数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用 Array 而不是 ArrayList？

18、ArrayList 和 LinkedList 有什么区别？

19、CopyOnWriteArrayList 相关知识

20、Comparable 和 Comparator 接口是干什么的？列出它们的区别。

21、什么是 Java 优先级队列(Priority Queue)？

22、Java集合类框架的最佳实践有哪些？

23、HashSet 和 TreeSet 有什么区别？

24、HashSet 的实现原理？

25、如何实现数组和 List 之间的转换？

26、Arrays.asList()使用指南

27、Collection.toArray()方法使用的坑&如何反转数组

28、ArrayList 和 Vector 的区别是什么？

29、在 Queue 中 poll()和 remove()有什么区别？

30、JDK1.8之后ConcurrentHashMap为什么使用synchronized而不用lock?

31、JDK1.7中 ConcurrentHashMap实现原理

数据结构

put 方法

get方法

size实现

32、JDK1.8中 ConcurrentHashMap实现原理

数据结构

initTable实现

put实现

扩容

size实现

33、红黑树学习

34、深入源码学习

ArrayList深入学习

LinkedList深入学习

HashMap深入学习

LinkedHashMap深入学习

ConcurrentHashMap JDK1.7深入学习

ConcurrentHashMap JDK1.8深入学习

HashSet深入学习

热门文章

最新文章

相关课程

相关电子书

相关实验场景