目录

1. HashMap

（1）问：HashMap 有用过吗？您能给我说说他的主要用途吗？

（2）问：您能说说 HashMap 常用操作的底层实现原理吗？如存储 put(K key, V value)，查找 get(Object key)，删除 remove(Object key)，修改 replace(K key, V value)等操作。

（3）.问：您能说说 HashMap 和 HashTable 的区别吗？

（4）问：您说 HashMap 不是线程安全的，那如果多线程下，它是如何处理的？并且什么情况下会发生线程不安全的情况？

（5）问：我们在使用 HashMap 时，选取什么对象作为 key 键比较好，为什么？

总结

2. ArrayList

定义

ArrayList 的构造器

add 方法源码分析

get 方法源码分析

set 方法源码分析

3.LinkedList

定义

4.Hashset

5、List、Set、Map区别

1. HashMap

（1）问：HashMap 有用过吗？您能给我说说他的主要用途吗？ 答：有用过，我在平常工作中经常会用到 HashMap 这种数据结构， HashMap 是基 于 Map 接口实现的一种键 - 值对 的存储结构，允许 null 值，同时非 有序，非同步 ( 即线程不安全 ) 。 HashMap 的底层实现是数组 + 链表 + 红黑树 （ JDK1.8 增加了红黑树部分）。它存储和查找数据时，是根据键 key 的 hashCode 的值计算出具体的存储位置。 HashMap 最多只允许一条记录的键 key 为 null ， HashMap 增删改查等常规操作都有不错的执行效率，是 ArrayList 和 LinkedList 等数据结构的一种折中实现。 示例代码： // 创建一个 HashMap，如果没有指定初始大小，默认底层 hash 表数组的 大小为 16 HashMap < String , String > hashMap = new HashMap(); // 往容器里面添加元素 hashMap .put("小明", "好帅"); hashMap .put("老王", "坑爹货"); hashMap .put("老铁", "没毛病"); hashMap .put("掘金", "好地方"); hashMap .put("王五", "别搞事"); // 获取 key 为小明的元素 好帅 String element = hashMap .get("小明"); // value : 好帅 System .out.println( element ); // 移除 key 为王五的元素 String removeElement = hashMap .remove("王五"); // value : 别搞事 System .out.println( removeElement ); // 修改 key 为小明的元素的值 value 为 其实有点丑 hashMap .replace("小明", "其实有点丑"); // {老铁=没毛病, 小明=其实有点丑, 老王=坑爹货, 掘金=好地方} System .out.println( hashMap ); // 通过 put 方法也可以达到修改对应元素的值的效果 hashMap .put("小明", "其实还可以啦,开玩笑的"); // {老铁=没毛病, 小明=其实还可以啦,开玩笑的, 老王=坑爹货, 掘金= 好地方} System .out.println( hashMap ); // 判断 key 为老王的元素是否存在(捉奸老王) boolean isExist = hashMap .containsKey("老王"); // true , 老王竟然来搞事 System .out.println( isExist ); // 判断是否有 value = "坑爹货" 的人 boolean isHasSomeOne = hashMap .containsValue("坑爹货"); // true 老王是坑爹货 System .out.println( isHasSomeOne ); // 查看这个容器里面还有几个家伙 value : 4 System .out.println( hashMap .size());

（2）问：您能说说 HashMap 常用操作的底层实现原理吗？如存储 put(K key, V value)，查找 get(Object key)，删除 remove(Object key)，修改 replace(K key, V value)等操作。 2.1）：调用 put(K key, V value) 操作添加 key-value 键值对时，进行了如下操作： 判断哈希表 Node[] table 是否为空或者 null ，是则执行 resize() 方法进行扩容。

根据插入的键值 key 的 hash 值，通过(n - 1) & hash 当前元素的 hash

值 & hash 表长度 - 1 （实际就是 hash 值 % hash 表长度） 计算出存储位 置 table[i] 。如果存储位置没有元素存放，则将新增结点存储在此位置 table[i] 。 如果存储位置已经有键值对元素存在，则判断该位置元素的 hash 值和 key 值是否和当前操作元素一致，一致则证明是修改 value 操作，覆盖 value 即可。 当前存储位置即有元素，又不和当前操作元素一致，则证明此位置 table[i] 已经发生了 hash 冲突，则通过判断头结点是否是 treeNode ，如 果是 treeNode 则证明此位置的结构是红黑树，已红黑树的方式新增结点。 如果不是红黑树，则证明是单链表，将新增结点插入至链表的最后位置， 随后判断当前链表长度是否 大于等于 8 ，是则将当前存储位置的链表转 化为红黑树。遍历过程中如果发现 key 已经存在，则直接覆盖 value 。 插入成功后，判断当前存储键值对的数量 大于 阈值 threshold 是则扩 容。 2.2）：调用 get(Object key) 操作根据键 key 查找对应的 key-value 键值对时，进行 了如下操作： 先调用 hash(key) 方法计算出 key 的 hash 值 根据查找的键值 key 的 hash 值，通过 (n - 1) & hash 当前元素的 hash 值 & hash 表长度 - 1 （实际就是 hash 值 % hash 表长度） 计算出存储位 置 table[i] ，判断存储位置是否有元素存在 。 如果存储位置有元素存放，则首先比较头结点元素，如果头结点的 key 的 hash 值 和 要获取的 key 的 hash 值相等，并且 头结点的 key 本身 和要 获取的 key 相等，则返回该位置的头结点。 如果存储位置没有元素存放，则返回 null 。 如果存储位置有元素存放，但是头结点元素不是要查找的元素，则需要遍 历该位置进行查找。 先判断头结点是否是 treeNode ，如果是 treeNode 则证明此位置的结构是 红黑树，以红色树的方式遍历查找该结点，没有则返回 null 。 如果不是红黑树，则证明是单链表。遍历单链表，逐一比较链表结点，链 表结点的 key 的 hash 值 和 要获取的 key 的 hash 值相等，并且 链表结 点的 key 本身 和要获取的 key 相等，则返回该结点，遍历结束仍未找到 对应 key 的结点，则返回 null 。 2.3）：调用 remove(Object key)操作根据键 key 删除对应的 key-value 键值对时，进 行了如下操作： 先调用 hash(key) 方法计算出 key 的 hash 值 根据查找的键值 key 的 hash 值，通过 (n - 1) & hash 当前元素的 hash 值 & hash 表长度 - 1 （实际就是 hash 值 % hash 表长度） 计算出存储位 置 table[i] ，判断存储位置是否有元素存在 。 如果存储位置有元素存放，则首先比较头结点元素，如果头结点的 key 的 hash 值 和 要获取的 key 的 hash 值相等，并且 头结点的 key 本身 和要 获取的 key 相等，则该位置的头结点即为要删除的结点，记录此结点至 变量 node 中。 如果存储位置没有元素存放，则没有找到对应要删除的结点，则返回 null 。 如果存储位置有元素存放，但是头结点元素不是要删除的元素，则需要遍 历该位置进行查找。 先判断头结点是否是 treeNode ，如果是 treeNode 则证明此位置的结构是 红黑树，以红色树的方式遍历查找并删除该结点，没有则返回 null 。 如果不是红黑树，则证明是单链表。遍历单链表，逐一比较链表结点，链 表结点的 key 的 hash 值 和 要获取的 key 的 hash 值相等，并且 链表结 点的 key 本身 和要获取的 key 相等，则此为要删除的结点，记录此结点 至变量 node 中，遍历结束仍未找到对应 key 的结点，则返回 null 。 如果找到要删除的结点 node ，则判断是否需要比较 value 也是否一致， 如果 value 值一致或者不需要比较 value 值，则执行删除结点操作，删除 操作根据不同的情况与结构进行不同的处理。 如果当前结点是树结点，则证明当前位置的链表已变成红黑树结构，通过 红黑树结点的方式删除对应结点。 如果不是红黑树，则证明是单链表。如果要删除的是头结点，则当前存储 位置 table[i] 的头结点指向删除结点的下一个结点。 如果要删除的结点不是头结点，则将要删除的结点的后继结点 node.next 赋值给要删除结点的前驱结点的 next 域，即 p.next = node.next; 。 2.4）：调用 replace(K key, V value)操作根据键 key 查找对应的 key-value 键值对， 随后替换对应的值 value ，进行了如下操作： 先调用 hash(key) 方法计算出 key 的 hash 值 随后调用 getNode 方法获取对应 key 所映射的 value 值 。 记录元素旧值，将新值赋值给元素，返回元素旧值，如果没有找到元素， 则返回 null 。

（3）.问：您能说说 HashMap 和 HashTable 的区别吗？ 答： HashMap 和 HashTable 有如下区别： 1 ）容器整体结构： HashMap 的 key 和 value 都允许为 null ， HashMap 遇到 key 为 null 的时候， 调用 putForNullKey 方法进行处理，而对 value 没有处理。 Hashtable 的 key 和 value 都不允许为 null 。 Hashtable 遇到 null ，直接 返回 NullPointerException 。 2 ） 容量设定与扩容机制： HashMap 默认初始化容量为 16 ，并且容器容量一定是 2 的 n 次方，扩容 时，是以原容量 2 倍 的方式 进行扩容。 Hashtable 默认初始化容量为 11 ，扩容时，是以原容量 2 倍 再加 1 的 方式进行扩容。即 int newCapacity = (oldCapacity << 1) + 1; 。 3 ） 散列分布方式（计算存储位置）： HashMap 是先将 key 键的 hashCode 经过扰动函数扰动后得到 hash 值，然 后再利用 hash & (length - 1) 的方式代替取模，得到元素的存储位置。 Hashtable 则是除留余数法进行计算存储位置的（因为其默认容量也不是 2 的 n 次方。所以也无法用位运算替代模运算）， int index = (hash & 0x7FFFFFFF) % tab.length; 。 由于 HashMap 的容器容量一定是 2 的 n 次方，所以能使用 hash & (length - 1) 的方式代替取模的方式计算元素的位置提高运算效率，但 Hashtable 的容器容量不一定是 2 的 n 次方，所以不能使用此运算方式代替。 4 ）线程安全（最重要）： HashMap 不是线程安全，如果想线程安全，可以通过调用 synchronizedMap(Map m) 使其线程安全。但是使用时的运行效率会 下降，所以建议使用 ConcurrentHashMap 容器以此达到线程安全。 Hashtable 则是线程安全的，每个操作方法前都有 synchronized 修饰使 其同步，但运行效率也不高，所以还是建议使用 ConcurrentHashMap 容器 以此达到线程安全。 因此， Hashtable 是一个遗留容器，如果我们不需要线程同步，则建议使用 HashMap ，如果需要线程同步，则建议使用 ConcurrentHashMap 。

（4）问：您说 HashMap 不是线程安全的，那如果多线程下，它是如何处理的？并且什么情况下会发生线程不安全的情况？ 答： HashMap 不是线程安全的，如果多个线程同时对同一个 HashMap 更改数据的 话，会导致数据不一致或者数据污染。如果出现线程不安全的操作时， HashMap 会尽可能的抛出 ConcurrentModificationException 防止数据异常，当我们在对 一个 HashMap 进行遍历时，在遍历期间，我们是不能对 HashMap 进行添加，删除 等更改数据的操作的，否则也会抛出 ConcurrentModificationException 异常， 此为 fail-fast （快速失败）机制。从源码上分析，我们在 put,remove 等更改 HashMap 数据时，都会导致 modCount 的改变，当 expectedModCount != modCount 时， 则抛出 ConcurrentModificationException 。如果想要线程安全，可以考虑使用 ConcurrentHashMap 。 而且，在多线程下操作 HashMap ，由于存在扩容机制，当 HashMap 调用 resize() 进行自动扩容时，可能会导致死循环的发生。 由于时间关系，我暂不带着大家一起去分析 resize() 方法导致死循环发生的现 象造成原因了，迟点有空我会再补充上去，请见谅，大家可以参考如下文章： Java 8 系列之重新认识 HashMap 谈谈 HashMap 线程不安全的体现

（5）问：我们在使用 HashMap 时，选取什么对象作为 key 键比较好，为什么？ 答：可变对象：指创建后自身状态能改变的对象。换句话说，可变对象是该对象 在创建后它的哈希值可能被改变。 我们在使用 HashMap 时，最好选择不可变对象作为 key 。例如 String ， Integer 等不可变类型作为 key 是非常明智的。 如果 key 对象是可变的，那么 key 的哈希值就可能改变。在 HashMap 中可 变对象作为 Key 会造成数据丢失。因为我们再进行 hash & (length - 1) 取模运算计算位置查找对应元素时，位置可能已经发生改变，导致数据丢 失。 详细例子说明请参考： 危险！在 HashMap 中将可变对象用作 Key

总结 HashMap 是基于 Map 接口实现的一种键 - 值对 的存储结构，允 许 null 值，同时非有序，非同步 ( 即线程不安全 ) 。 HashMap 的底层实现是 数组 + 链表 + 红黑树（ JDK1.8 增加了红黑树部分）。 HashMap 定位元素位置是通过键 key 经过扰动函数扰动后得到 hash 值， 然后再通过 hash & (length - 1) 代替取模的方式进行元素定位的。 HashMap 是使用链地址法解决 hash 冲突的，当有冲突元素放进来时，会 将此元素插入至此位置链表的最后一位，形成单链表。当存在位置的链表 长度 大于等于 8 时， HashMap 会将链表 转变为 红黑树，以此提高查找 效率。 HashMap 的容量是 2 的 n 次方，有利于提高计算元素存放位置时的效率， 也降低了 hash 冲突的几率。因此，我们使用 HashMap 存储大量数据的时 候，最好先预先指定容器的大小为 2 的 n 次方，即使我们不指定为 2 的 n 次方， HashMap 也会把容器的大小设置成最接近设置数的 2 的 n 次方，如， 设置 HashMap 的大小为 7 ，则 HashMap 会将容器大小设置成最接近 7 的 一个 2 的 n 次方数，此值为 8 。 HashMap 的负载因子表示哈希表空间的使用程度（或者说是哈希表空间的 利用率）。当负载因子越大，则 HashMap 的装载程度就越高。也就是能容 纳更多的元素，元素多了，发生 hash 碰撞的几率就会加大，从而链表就 会拉长，此时的查询效率就会降低。当负载因子越小，则链表中的数据量 就越稀疏，此时会对空间造成浪费，但是此时查询效率高。 HashMap 不是线程安全的， Hashtable 则是线程安全的。但 Hashtable 是 一个遗留容器，如果我们不需要线程同步，则建议使用 HashMap ，如果需 要线程同步，则建议使用 ConcurrentHashMap 。 在多线程下操作 HashMap ，由于存在扩容机制，当 HashMap 调用 resize() 进行自动扩容时，可能会导致死循环的发生。 我们在使用 HashMap 时，最好选择不可变对象作为 key 。例如 String ， Integer 等不可变类型作为 key 是非常明智的。

2. ArrayList

定义 快速了解 ArrayList 究竟是什么的一个好方法就是看 JDK 源码中对 ArrayList 类的 注释，大致翻译如下： private static final int DEFAULT_CAPACITY = 10; private static final Object [] EMPTY_ELEMENTDATA = {}; private static final Object [] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object [] elementData ; // non-private to simplify nested class access private int size ; 通过以上字段，我们验证了 ArrayList 内部确实使用一个 Object 数组来存储集合 元素。

ArrayList 的构造器 首先我们来看一下我们平时经常使用的 ArrayList 的无参构造器的源码： public ArrayList() { this. elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;} 我们可以看到，无参构造器仅仅是把 ArrayList 实例的 elementData 字段赋值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 。 接下来，我们再来看一下 ArrayList 的其他构造器：

public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}}

public ArrayList(Collection c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}}

通过源码我们可以看到，第一个构造器指定了 ArrayList 的初始 capacity ，然后根 据这个初始 capacity 创建一个相应大小的 Object 数组。若 initialCapacity 为 0 ，则 将 elementData 赋值为 EMPTY_ELEMENTDATA ；若 initialCapacity 为负数，则抛出 一个 IllegalArgumentException 异常。 第二个构造器则指定一个 Collection 对象作为参数，从而构造一个含有指定集合 对象元素的 ArrayList 对象。这个构造器首先把 elementData 实例域赋值为集合对 象转为的数组，而后再判断传入的集合对象是否不含有任何元素，若是的话，则 将 elementData 赋值为 EMPTY_ELEMENTDATA ；若传入的集合对象至少包含一个 元素，则进一步判断 c.toArray 方法是否正确返回了 Object 数组，若不是的话， 则需要用 Arrays.copyOf 方法把 elementData 的元素类型改变为 Object 。 现在，我们又了解了 ArrayList 实例的构建过程，那么接下来我们来通过 ArrayList 的 get 、 set 等方法的源码来进一步了解它的实现原理

add 方法源码分析 public boolean add(E e ) { ensureCapacityInternal( size + 1); // Increments modCount!! elementData [ size ++] = e ; return true;} 我们可以看到，在 add 方法内部，首先调用了 ensureCapacityInternal(size+1) ，这 句的作用有两个： • 保证当前 ArrayList 实例的 capacity 足够大； • 增加 modCount ， modCount 的作用是判断在迭代时是否对 ArrayList 进行了结构性修 改。 然后通过将内部数组下一个索引处的元素设置为给定参数来完成了向 ArrayList 中添加元素，返回 true 表示添加成功。

get 方法源码分析 public E get(int index ) { rangeCheck( index ); return elementData( index );} 首先调用了 rangeCheck 方法来检查我们传入的 index 是否在合法范围内，然后调 用了 elementData 方法，这个方法的源码如下： E elementData(int index ) { return ( E ) elementData [ index ];}

set 方法源码分析 public E set( int index , E element ) { rangeCheck( index ); E oldValue = elementData( index ); elementData [ index ] = element ; return oldValue ;} 我们可以看到， set 方法的实现也很简单，首先检查给定的索引是否在合法范围 内，若在，则先把该索引处原来的元素存储在 oldValue 中，然后把新元素放到该 索引处并返回 oldValue 即可。

3.LinkedList 定义 LinkedList 类源码中的注释如下： LinkedList 是对链表这种数据结构的实现（对链表还不太熟悉的小伙伴可以参考 深入理解数据结构之链表 ），当我们需要一种支持高效删除 / 添加元素的数据结 构时，可以考虑使用链表。 总的来说，链表具有以下两个优点： • 插入及删除操作的时间复杂度为 O(1) • 可以动态改变大小 链表主要的缺点是：由于其链式存储的特性，链表不具备良好的空间局部性，也 就是说，链表是一种缓存不友好的数据结构。

4.Hashset HashSet 是 Set 的一种实现方式，底层主要使用 HashMap 来确保元素不重复。 总结 （ 1 ） HashSet 内部使用 HashMap 的 key 存储元素，以此来保证元素不重复； （ 2 ） HashSet 是无序的，因为 HashMap 的 key 是无序的； （ 3 ） HashSet 中允许有一个 null 元素，因为 HashMap 允许 key 为 null ； （ 4 ） HashSet 是非线程安全的； （ 5 ） HashSet 是没有 get() 方法的；

5、List、Set、Map区别

在说三者区别的时候先普及一下三个概念：数组，链表和哈希表

数组：存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

链表：存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。

哈希表：那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。

1.List列表:元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。List集合允许加入重复元素，因为它可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引

2.Set集合：没有顺序，不能重复。Set集合类似于一个罐子，"丢进"Set集合里的多个对象之间没有明显的顺序。Set继承自Collection接口，不能包含有重复元素(记住，这是整个Set类层次的共有属性)。

3.Map:用于保存具有"映射关系"的数据，因此Map集合里保存着两组值，一组值用于保存Map里的key，另外一组值用于保存Map里的value。key和value都可以是任何引用类型的数据。Map的key不允许重复

ArrayList -是线程不安全 底层是由数组实现 他的构造主要从AbstractList实现，主要是判断下初始元素的容量，ArrayList最大的特点就是提供了Add、Get操作，当然可以通过迭代器来遍历，对于元素的存在可以通过contains方法判断。

LinkedList - 线程不安全的 作为一种双向链表结构，对于元素的插入、删除效率比较高，只需要调整节点指向即可，但是对于随机查找而言性能主要看这个链表长度和运气了。 LinkedList也提供了ArrayList的get方法，但是要复杂的多，主要通过next或previous方法遍历得到，LinkedList要移动指针。

Vector -线程安全的，这两个类底层都是由数组实现的，效率低  比较简单和ArrayList差不多，主要是内部实现了synchronized关键字，实现了线程安全访问但性能有些降低，同时对于元素的扩充在算法上和ArrayList稍有不同，通过构造的容量增量系数来决定。