作为Java求职者&＃xff0c;无数次被问到过集合的知识&＃xff0c;同时作为一位"周角公司小菜面试官”&＃xff0c;我也肯定会问面试者集合的知识&＃xff0c;所以就有了这篇&＃xff0c;源码较多&＃xff0c;建议静下心来哈&＃xff0c;一起学习&＃xff0c;一起进步

面向对象语言对事物的体现都是以对象的形式&＃xff0c;所以为了方便对多个对象的操作&＃xff0c;需要将对象进行存储&＃xff0c;集合就是存储对象最常用的一种方式&＃xff0c;也叫容器。

从上面的集合框架图可以看到&＃xff0c;Java 集合框架主要包括两种类型的容器

• 一种是集合(Collection)&＃xff0c;存储一个元素集合
• 另一种是图(Map)&＃xff0c;存储键/值对映射。

Collection 接口又有 3 种子类型&＃xff0c;List、Set 和 Queue&＃xff0c;再下面是一些抽象类&＃xff0c;最后是具体实现类&＃xff0c;常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容&＃xff1a;

• 接口&＃xff1a;是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口&＃xff0c;是为了以不同的方式操作集合对象
• 实现(类)&＃xff1a;是集合接口的具体实现。从本质上讲&＃xff0c;它们是可重复使用的数据结构&＃xff0c;例如&＃xff1a;ArrayList、LinkedList、HashSet、HashMap。
• 算法&＃xff1a;是实现集合接口的对象里的方法执行的一些有用的计算&＃xff0c;例如&＃xff1a;搜索和排序。这些算法被称为多态&＃xff0c;那是因为相同的方法可以在相似的接口上有着不同的实现。

说说常用的集合有哪些吧&＃xff1f;

Map 接口和 Collection 接口是所有集合框架的父接口&＃xff1a;

1. Collection接口的子接口包括&＃xff1a;Set、List、Queue
2. List是有序的不允许有重复元素的Collection&＃xff0c;实现类主要有&＃xff1a;ArrayList、LinkedList、Stack以及Vector等
3. Set是一种不包含重复元素且无序的Collection&＃xff0c;实现类主要有&＃xff1a;HashSet、TreeSet、LinkedHashSet等
4. Map没有继承Collection接口&＃xff0c;Map提供key到value的映射。实现类主要有&＃xff1a;HashMap、TreeMap、Hashtable、ConcurrentHashMap 以及 Properties 等

ArrayList 和 Vector 的区别

相同点&＃xff1a;

• ArrayList 和 Vector 都是继承了相同的父类和实现了相同的接口(都实现了List&＃xff0c;有序、允许重复和null)
• 底层都是数组(Object[])实现的
• 初始默认长度都为10

不同点&＃xff1a;

• 同步性&＃xff1a;Vector 中的 public 方法多数添加了 synchronized 关键字、以确保方法同步、也即是 Vector 线程安全、ArrayList 线程不安全
• 性能&＃xff1a;Vector 存在 synchronized 的锁等待情况、需要等待释放锁这个过程、所以性能相对较差
• 扩容大小&＃xff1a;ArrayList在底层数组不够用时在原来的基础上扩展 0.5 倍&＃xff0c;Vector 默认是扩展 1 倍 扩容机制&＃xff0c;扩容方法其实就是新创建一个数组&＃xff0c;然后将旧数组的元素都复制到新数组里面。其底层的扩容方法都在 grow() 中(基于JDK8)
  • ArrayList 的 grow()&＃xff0c;在满足扩容条件时、ArrayList以1.5 倍的方式在扩容(oldCapacity >> 1 &＃xff0c;右移运算&＃xff0c;相当于除以 2&＃xff0c;结果为二分之一的 oldCapacity)
  • Vector 的 grow()&＃xff0c;Vector 比 ArrayList多一个属性 capacityIncrement&＃xff0c;可以指定扩容大小。当扩容容量增量大于 0 时、新数组长度为 原数组长度**&＃43;**扩容容量增量、否则新数组长度为原数组长度的 2 倍

ArrayList 与 LinkedList 区别

• 是否保证线程安全&＃xff1a;ArrayList 和 LinkedList 都是不同步的&＃xff0c;也就是不保证线程安全&＃xff1b;
• 底层数据结构&＃xff1a;Arraylist 底层使用的是 Object 数组&＃xff1b;LinkedList 底层使用的是双向循环链表数据结构&＃xff1b;
• 插入和删除是否受元素位置的影响&＃xff1a;
  • ArrayList 采用数组存储&＃xff0c;所以插入和删除元素的时间复杂度受元素位置的影响。 比如&＃xff1a;执行 add(E e)方法的时候&＃xff0c; ArrayList 会默认在将指定的元素追加到此列表的末尾&＃xff0c;这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话( add(intindex,E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
  • LinkedList 采用链表存储&＃xff0c;所以插入&＃xff0c;删除元素时间复杂度不受元素位置的影响&＃xff0c;都是近似 &＃xff0c;而数组为近似 。
  • ArrayList 一般应用于查询较多但插入以及删除较少情况&＃xff0c;如果插入以及从删除较多则建议使用 LinkedList
• 是否支持快速随机访问&＃xff1a;LinkedList 不支持高效的随机元素访问&＃xff0c;而 ArrayList 实现了 RandomAccess 接口&＃xff0c;所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(intindex)方法)。
• 内存空间占用&＃xff1a;ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间&＃xff0c;而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

高级工程师的我&＃xff0c;可不得看看源码&＃xff0c;具体分析下&＃xff1a;

• ArrayList工作原理其实很简单&＃xff0c;底层是动态数组&＃xff0c;每次创建一个 ArrayList 实例时会分配一个初始容量(没有指定初始容量的话&＃xff0c;默认是 10)&＃xff0c;以add方法为例&＃xff0c;如果没有指定初始容量&＃xff0c;当执行add方法&＃xff0c;先判断当前数组是否为空&＃xff0c;如果为空则给保存对象的数组分配一个最小容量&＃xff0c;默认为10。当添加大容量元素时&＃xff0c;会先增加数组的大小&＃xff0c;以提高添加的效率&＃xff1b;
• LinkedList 是有序并且支持元素重复的集合&＃xff0c;底层是基于双向链表的&＃xff0c;即每个节点既包含指向其后继的引用也包括指向其前驱的引用。链表无容量限制&＃xff0c;但双向链表本身使用了更多空间&＃xff0c;也需要额外的链表指针操作。按下标访问元素 get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半&＃xff0c;会从末尾移起)。插入、删除元素时修改前后节点的指针即可&＃xff0c;但还是要遍历部分链表的指针才能移动到下标所指的位置&＃xff0c;只有在链表两头的操作add()&＃xff0c; addFirst()&＃xff0c;removeLast()或用 iterator() 上的 remove() 能省掉指针的移动。此外 LinkedList 还实现了 Deque(继承自Queue接口)接口&＃xff0c;可以当做队列使用。

ps&＃xff1a;不会囊括所有方法&＃xff0c;只是为了学习&＃xff0c;记录思想。

ArrayList 和 LinkedList 两者都实现了 List 接口

构造器

ArrayList 提供了 3 个构造器&＃xff0c;①无参构造器 ②带初始容量构造器 ③参数为集合构造器

LinkedList 提供了 2 个构造器&＃xff0c;因为基于链表&＃xff0c;所以也就没有初始化大小&＃xff0c;也没有扩容的机制&＃xff0c;就是一直在前面或者后面插插插~~

插入

ArrayList 的 add() 方法

当然也可以插入指定位置&＃xff0c;还有一个重载的方法 add(int index, E element)

可以看到每次插入指定位置都要移动元素&＃xff0c;效率较低。

再来看 LinkedList 的插入&＃xff0c;也有插入末尾&＃xff0c;插入指定位置两种&＃xff0c;由于基于链表&＃xff0c;肯定得先有个 Node

获取

ArrayList 的 get() 方法很简单&＃xff0c;就是在数组中返回指定位置的元素即可&＃xff0c;所以效率很高

LinkedList 的 get() 方法&＃xff0c;就是在内部调用了上边看到的 node() 方法&＃xff0c;判断在前半段还是在后半段&＃xff0c;然后遍历得到即可。

---

HashMap的底层实现

什么时候会使用HashMap&＃xff1f;他有什么特点&＃xff1f;

你知道HashMap的工作原理吗&＃xff1f;

你知道 get 和 put 的原理吗&＃xff1f;equals() 和 hashCode() 的都有什么作用&＃xff1f;

你知道hash的实现吗&＃xff1f;为什么要这样实现&＃xff1f;

如果HashMap的大小超过了负载因子(load factor)定义的容量&＃xff0c;怎么办&＃xff1f;

HashMap 在 JDK 7 和 JDK8 中的实现方式略有不同。分开记录。

JDK1.7 实现

深入 HahsMap 之前&＃xff0c;先要了解的概念

1. initialCapacity&＃xff1a;初始容量。指的是 HashMap 集合初始化的时候自身的容量。可以在构造方法中指定&＃xff1b;如果不指定的话&＃xff0c;总容量默认值是 16 。需要注意的是初始容量必须是 2 的幂次方。(1.7中&＃xff0c;已知HashMap中将要存放的 KV 个数的时候&＃xff0c;设置一个合理的初始化容量可以有效的提高性能)static final int DEFAULT_INITIAL_CAPACITY &＃61; 1 <<4; // aka 16
2. size&＃xff1a;当前 HashMap 中已经存储着的键值对数量&＃xff0c;即 HashMap.size()
3. loadFactor&＃xff1a;加载因子。所谓的加载因子就是 HashMap (当前的容量/总容量) 到达一定值的时候&＃xff0c;HashMap 会实施扩容。加载因子也可以通过构造方法中指定&＃xff0c;默认的值是 0.75 。举个例子&＃xff0c;假设有一个 HashMap 的初始容量为 16 &＃xff0c;那么扩容的阀值就是 0.75 * 16 &＃61; 12 。也就是说&＃xff0c;在你打算存入第 13 个值的时候&＃xff0c;HashMap 会先执行扩容。
4. threshold&＃xff1a;扩容阀值。即 扩容阀值 &＃61; HashMap 总容量 * 加载因子。当前 HashMap 的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为当前 HashMap 总容量的两倍。比如&＃xff0c;当前 HashMap 的总容量为 16 &＃xff0c;那么扩容之后为 32 。
5. table&＃xff1a;Entry 数组。我们都知道 HashMap 内部存储 key/value 是通过 Entry 这个介质来实现的。而 table 就是 Entry 数组。

JDK1.7 中 HashMap 由 数组&＃43;链表 组成(“链表散列” 即数组和链表的结合体)&＃xff0c;数组是 HashMap 的主体&＃xff0c;链表则是主要为了解决哈希冲突而存在的(HashMap 采用 “拉链法也就是链地址法” 解决冲突)&＃xff0c;如果定位到的数组位置不含链表(当前 entry 的 next 指向 null ),那么对于查找&＃xff0c;添加等操作很快&＃xff0c;仅需一次寻址即可&＃xff1b;如果定位到的数组包含链表&＃xff0c;对于添加操作&＃xff0c;其时间复杂度依然为 O(1)&＃xff0c;因为最新的 Entry 会插入链表头部&＃xff0c;即需要简单改变引用链即可&＃xff0c;而对于查找操作来讲&＃xff0c;此时就需要遍历链表&＃xff0c;然后通过 key 对象的 equals 方法逐一比对查找。

所谓 “拉链法” 就是将链表和数组相结合。也就是说创建一个链表数组&＃xff0c;数组中每一格就是一个链表。若遇到哈希冲突&＃xff0c;则将冲突的值加到链表中即可。

源码解析

构造方法

《阿里巴巴 Java 开发手册》推荐集合初始化时&＃xff0c;指定集合初始值大小。(说明&＃xff1a;HashMap 使用HashMap(int initialCapacity) 初始化)&＃xff0c;原因&＃xff1a;https://www.zhihu.com/question/314006228/answer/611170521

HashMap 的前 3 个构造方法最后都会去调用 HashMap(int initialCapacity, float loadFactor) 。在其内部去设置初始容量和加载因子。而最后的 init() 是空方法&＃xff0c;主要给子类实现&＃xff0c;比如 LinkedHashMap。

put() 方法

最后的 createEntry() 方法就说明了当 hash 冲突时&＃xff0c;采用的拉链法来解决 hash 冲突的&＃xff0c;并且是把新元素是插入到单边表的表头。

get() 方法

JDK1.8 实现

JDK 1.7 中&＃xff0c;如果哈希碰撞过多&＃xff0c;拉链过长&＃xff0c;极端情况下&＃xff0c;所有值都落入了同一个桶内&＃xff0c;这就退化成了一个链表。通过 key 值查找要遍历链表&＃xff0c;效率较低。JDK1.8在解决哈希冲突时有了较大的变化&＃xff0c;当链表长度大于阈值(默认为8)时&＃xff0c;将链表转化为红黑树&＃xff0c;以减少搜索时间。

TreeMap、TreeSet以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷&＃xff0c;因为二叉查找树在某些情况下会退化成一个线性结构。

源码解析

构造方法

JDK8 构造方法改动不是很大

确定哈希桶数组索引位置(hash 函数的实现)

HashMap定位数组索引位置&＃xff0c;直接决定了hash方法的离散性能。Hash算法本质上就是三步&＃xff1a;取key的hashCode值、高位运算、取模运算。

hash

为什么要这样呢&＃xff1f;

HashMap 的长度为什么是2的幂次方?

目的当然是为了减少哈希碰撞&＃xff0c;使 table 里的数据分布的更均匀。

1. HashMap 中桶数组的大小 length 总是2的幂&＃xff0c;此时&＃xff0c;h & (table.length -1) 等价于对 length 取模 h%length。但取模的计算效率没有位运算高&＃xff0c;所以这是是一个优化。假设 h &＃61; 185&＃xff0c;table.length-1 &＃61; 15(0x1111)&＃xff0c;其实散列真正生效的只是低 4bit 的有效位&＃xff0c;所以很容易碰撞。img
2. 图中的 hash 是由键的 hashCode 产生。计算余数时&＃xff0c;由于 n 比较小&＃xff0c;hash 只有低4位参与了计算&＃xff0c;高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关&＃xff0c;高位数据没发挥作用。为了处理这个缺陷&＃xff0c;我们可以上图中的 hash 高4位数据与低4位数据进行异或运算&＃xff0c;即 hash ^ (hash >>> 4)。通过这种方式&＃xff0c;让高位数据与低位数据进行异或&＃xff0c;以此加大低位信息的随机性&＃xff0c;变相的让高位数据参与到计算中。此时的计算过程如下&＃xff1a;img在 Java 中&＃xff0c;hashCode 方法产生的 hash 是 int 类型&＃xff0c;32 位宽。前16位为高位&＃xff0c;后16位为低位&＃xff0c;所以要右移16位&＃xff0c;即 hash ^ (hash >>> 16) 。这样还增加了hash 的复杂度&＃xff0c;进而影响 hash 的分布性。

put() 方法

resize() 扩容

get() 方法

---

Hashtable

Hashtable 和 HashMap 都是散列表&＃xff0c;也是用”拉链法“实现的哈希表。保存数据和 JDK7 中的 HashMap 一样&＃xff0c;是 Entity 对象&＃xff0c;只是 Hashtable 中的几乎所有的 public 方法都是 synchronized 的&＃xff0c;而有些方法也是在内部通过 synchronized 代码块来实现&＃xff0c;效率肯定会降低。且 put() 方法不允许空值。

使用次数太少&＃xff0c;不深究。

HashMap 和 Hashtable 的区别

1. 线程是否安全&＃xff1a; HashMap 是非线程安全的&＃xff0c;HashTable 是线程安全的&＃xff1b;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧&＃xff01;)&＃xff1b;
2. 效率&＃xff1a; 因为线程安全的问题&＃xff0c;HashMap 要比 HashTable 效率高一点。另外&＃xff0c;HashTable 基本被淘汰&＃xff0c;不要在代码中使用它&＃xff1b;
3. 对Null key 和Null value的支持&＃xff1a; HashMap 中&＃xff0c;null 可以作为键&＃xff0c;这样的键只有一个&＃xff0c;可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null&＃xff0c;直接抛出 NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 &＃xff1a;

• 创建时如果不指定容量初始值&＃xff0c;Hashtable 默认的初始大小为11&＃xff0c;之后每次扩充&＃xff0c;容量变为原来的2n&＃43;1。HashMap 默认的初始化大小为16。之后每次扩充&＃xff0c;容量变为原来的2倍。

• 创建时如果给定了容量初始值&＃xff0c;那么 Hashtable 会直接使用你给定的大小&＃xff0c;而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂次方作为哈希表的大小,后面会介绍到为什么是2的幂次方。

5. 底层数据结构&＃xff1a; JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化&＃xff0c;当链表长度大于阈值(默认为8)时&＃xff0c;将链表转化为红黑树&＃xff0c;以减少搜索时间。Hashtable 没有这样的机制。
6. HashMap的迭代器(Iterator)是fail-fast迭代器&＃xff0c;但是 Hashtable的迭代器(enumerator)不是 fail-fast的。如果有其它线程对HashMap进行的添加/删除元素&＃xff0c;将会抛出ConcurrentModificationException&＃xff0c;但迭代器本身的remove方法移除元素则不会抛出异常。这条同样也是 Enumeration 和 Iterator 的区别。

ConcurrentHashMap

HashMap在多线程情况下&＃xff0c;在put的时候&＃xff0c;插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作&＃xff0c;就是rehash&＃xff0c;这个会重新将原数组的内容重新hash到新的扩容数组中&＃xff0c;在多线程的环境下&＃xff0c;存在同时其他的元素也在进行put操作&＃xff0c;如果hash值相同&＃xff0c;可能出现同时在同一数组下用链表表示&＃xff0c;造成闭环&＃xff0c;导致在get时会出现死循环&＃xff0c;所以HashMap是线程不安全的。

Hashtable&＃xff0c;是线程安全的&＃xff0c;它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table&＃xff0c;这就意味着所有的线程都在竞争一把锁&＃xff0c;在多线程的环境下&＃xff0c;它是安全的&＃xff0c;但是无疑是效率低下的。

JDK1.7 实现

Hashtable 容器在竞争激烈的并发环境下表现出效率低下的原因&＃xff0c;是因为所有访问 Hashtable 的线程都必须竞争同一把锁&＃xff0c;那假如容器里有多把锁&＃xff0c;每一把锁用于锁容器其中一部分数据&＃xff0c;那么当多线程访问容器里不同数据段的数据时&＃xff0c;线程间就不会存在锁竞争&＃xff0c;&＃xff0c;这就是ConcurrentHashMap所使用的锁分段技术。

在 JDK1.7版本中&＃xff0c;ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。Segment 数组的意义就是将一个大的 table 分割成多个小的 table 来进行加锁。每一个 Segment 元素存储的是 HashEntry数组&＃43;链表&＃xff0c;这个和 HashMap 的数据存储结构一样。

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键值对&＃xff0c;Segment 用来充当锁的角色&＃xff0c;每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。每个 Segment 守护着一个 HashEntry 数组里的元素&＃xff0c;当对 HashEntry 数组的数据进行修改时&＃xff0c;必须首先获得它对应的 Segment 锁。

Segment 类

Segment 类继承于 ReentrantLock 类&＃xff0c;从而使得 Segment 对象能充当可重入锁的角色。一个 Segment 就是一个子哈希表&＃xff0c;Segment 里维护了一个 HashEntry 数组&＃xff0c;并发环境下&＃xff0c;对于不同 Segment 的数据进行操作是不用考虑锁竞争的。

从源码可以看到&＃xff0c;Segment 内部类和我们上边看到的 HashMap 很相似。也有负载因子&＃xff0c;阈值等各种属性。

HashEntry 类

HashEntry 是目前我们最小的逻辑处理单元。一个ConcurrentHashMap 维护一个 Segment 数组&＃xff0c;一个Segment维护一个 HashEntry 数组。

ConcurrentHashMap 类

默认的情况下&＃xff0c;每个ConcurrentHashMap 类会创建16个并发的 segment&＃xff0c;每个 segment 里面包含多个 Hash表&＃xff0c;每个 Hash 链都是由 HashEntry 节点组成的。

put() 方法

1. 定位segment并确保定位的Segment已初始化
2. 调用 Segment的 put 方法。

get() 方法

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

JDK1.8 实现

ConcurrentHashMap 在 JDK8 中进行了巨大改动&＃xff0c;光是代码量就从1000多行增加到6000行&＃xff01;1.8摒弃了Segment(锁段)的概念&＃xff0c;采用了 CAS &＃43; synchronized 来保证并发的安全性。

可以看到&＃xff0c;和HashMap 1.8的数据结构很像。底层数据结构改变为采用数组&＃43;链表&＃43;红黑树的数据形式。

和 HashMap1.8 相同的一些地方

• 底层数据结构一致
• HashMap初始化是在第一次put元素的时候进行的&＃xff0c;而不是init
• HashMap的底层数组长度总是为2的整次幂
• 默认树化的阈值为 8&＃xff0c;而链表化的阈值为 6
• hash算法也很类似&＃xff0c;但多了一步& HASH_BITS&＃xff0c;该步是为了消除最高位上的负符号&＃xff0c;hash的负在ConcurrentHashMap中有特殊意义表示在扩容或者是树节点

一些关键属性

put() 方法

1. 首先会判断 key、value是否为空&＃xff0c;如果为空就抛异常&＃xff01;
2. spread()方法获取hash&＃xff0c;减小hash冲突
3. 判断是否初始化table数组&＃xff0c;没有的话调用initTable()方法进行初始化
4. 判断是否能直接将新值插入到table数组中
5. 判断当前是否在扩容&＃xff0c;MOVED为-1说明当前ConcurrentHashMap正在进行扩容操作&＃xff0c;正在扩容的话就进行协助扩容
6. 当table[i]为链表的头结点&＃xff0c;在链表中插入新值&＃xff0c;通过synchronized (f)的方式进行加锁以实现线程安全性。
   1. 在链表中如果找到了与待插入的键值对的key相同的节点&＃xff0c;就直接覆盖
   2. 如果没有找到的话&＃xff0c;就直接将待插入的键值对追加到链表的末尾
7. 当table[i]为红黑树的根节点&＃xff0c;在红黑树中插入新值/覆盖旧值
8. 根据当前节点个数进行调整&＃xff0c;否需要转换成红黑树(个数大于等于8&＃xff0c;就会调用treeifyBin方法将tabel[i]第i个散列桶拉链转换成红黑树)
9. 对当前容量大小进行检查&＃xff0c;如果超过了临界值(实际大小*加载因子)就进行扩容

我们可以发现 JDK8 中的实现也是锁分离的思想&＃xff0c;只是锁住的是一个 Node&＃xff0c;而不是 JDK7 中的 Segment&＃xff0c;而锁住Node 之前的操作是无锁的并且也是线程安全的&＃xff0c;建立在原子操作上。

get() 方法

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

Hashtable 和 ConcurrentHashMap 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构&＃xff1a; JDK1.7的 ConcurrentHashMap 底层采用 分段的数组&＃43;链表 实现&＃xff0c;JDK1.8 采用的数据结构和HashMap1.8的结构类似&＃xff0c;数组&＃43;链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组&＃43;链表 的形式&＃xff0c;数组是 HashMap 的主体&＃xff0c;链表则是主要为了解决哈希冲突而存在的&＃xff1b;
• 实现线程安全的方式(重要)&＃xff1a;
  • 在JDK1.7的时候&＃xff0c;ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment)&＃xff0c;每一把锁只锁容器其中一部分数据&＃xff0c;多线程访问容器里不同数据段的数据&＃xff0c;就不会存在锁竞争&＃xff0c;提高并发访问率。(默认分配16个Segment&＃xff0c;比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念&＃xff0c;而是直接用 Node 数组&＃43;链表/红黑树的数据结构来实现&＃xff0c;并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap&＃xff0c;虽然在 JDK1.8 中还能看到 Segment 的数据结构&＃xff0c;但是已经简化了属性&＃xff0c;只是为了兼容旧版本&＃xff1b;
  • Hashtable(同一把锁) :使用 synchronized 来保证线程安全&＃xff0c;效率非常低下。当一个线程访问同步方法时&＃xff0c;其他线程也访问同步方法&＃xff0c;可能会进入阻塞或轮询状态&＃xff0c;如使用 put 添加元素&＃xff0c;另一个线程不能使用 put 添加元素&＃xff0c;也不能使用 get&＃xff0c;竞争越激烈效率越低。

list 可以删除吗&＃xff0c;遍历的时候可以删除吗&＃xff0c;为什么

Java快速失败(fail-fast)和安全失败(fail-safe)区别

快速失败(fail—fast)

在用迭代器遍历一个集合对象时&＃xff0c;如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改)&＃xff0c;则会抛出ConcurrentModificationException。

原理&＃xff1a;迭代器在遍历时直接访问集合中的内容&＃xff0c;并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化&＃xff0c;就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前&＃xff0c;都会检测 modCount 变量是否为 expectedmodCount 值&＃xff0c;是的话就返回遍历&＃xff1b;否则抛出异常&＃xff0c;终止遍历。

注意&＃xff1a;这里异常的抛出条件是检测到 modCount&＃xff01;&＃61;expectedmodCount 这个条件。如果集合发生变化时修改modCount 值刚好又设置为了 expectedmodCount 值&＃xff0c;则异常不会抛出。因此&＃xff0c;不能依赖于这个异常是否抛出而进行并发操作的编程&＃xff0c;这个异常只建议用于检测并发修改的bug。

场景&＃xff1a;java.util包下的集合类都是快速失败的&＃xff0c;不能在多线程下发生并发修改(迭代过程中被修改)。

安全失败(fail—safe)

采用安全失败机制的集合容器&＃xff0c;在遍历时不是直接在集合内容上访问的&＃xff0c;而是先复制原有集合内容&＃xff0c;在拷贝的集合上进行遍历。

原理&＃xff1a;由于迭代时是对原集合的拷贝进行遍历&＃xff0c;所以在遍历过程中对原集合所作的修改并不能被迭代器检测到&＃xff0c;所以不会触发 Concurrent Modification Exception。

缺点&＃xff1a;基于拷贝内容的优点是避免了Concurrent Modification Exception&＃xff0c;但同样地&＃xff0c;迭代器并不能访问到修改后的内容&＃xff0c;即&＃xff1a;迭代器遍历的是开始遍历那一刻拿到的集合拷贝&＃xff0c;在遍历期间原集合发生的修改迭代器是不知道的。

场景&＃xff1a;java.util.concurrent包下的容器都是安全失败&＃xff0c;可以在多线程下并发使用&＃xff0c;并发修改。

快速失败和安全失败是对迭代器而言的。快速失败&＃xff1a;当在迭代一个集合的时候&＃xff0c;如果有另外一个线程在修改这个集合&＃xff0c;就会抛出ConcurrentModification异常&＃xff0c;java.util下都是快速失败。安全失败&＃xff1a;在迭代时候会在集合二层做一个拷贝&＃xff0c;所以在修改集合上层元素不会影响下层。在java.util.concurrent下都是安全失败

如何避免fail-fast &＃xff1f;

• 在单线程的遍历过程中&＃xff0c;如果要进行remove操作&＃xff0c;可以调用迭代器 ListIterator 的 remove 方法而不是集合类的 remove方法。看看 ArrayList中迭代器的 remove方法的源码&＃xff0c;该方法不能指定元素删除&＃xff0c;只能remove当前遍历元素。
• 使用并发包(java.util.concurrent)中的类来代替 ArrayList 和 hashMap
  • CopyOnWriterArrayList 代替 ArrayList
  • ConcurrentHashMap 代替 HashMap

Iterator 和 Enumeration 区别

在Java集合中&＃xff0c;我们通常都通过 “Iterator(迭代器)” 或 “Enumeration(枚举类)” 去遍历集合。

• 函数接口不同&＃xff0c;Enumeration只有2个函数接口。通过Enumeration&＃xff0c;我们只能读取集合的数据&＃xff0c;而不能对数据进行修改。Iterator只有3个函数接口。Iterator除了能读取集合的数据之外&＃xff0c;也能数据进行删除操作。
• Iterator支持 fail-fast机制&＃xff0c;而Enumeration不支持。Enumeration 是JDK 1.0添加的接口。使用到它的函数包括Vector、Hashtable等类&＃xff0c;这些类都是JDK 1.0中加入的&＃xff0c;Enumeration存在的目的就是为它们提供遍历接口。Enumeration本身并没有支持同步&＃xff0c;而在Vector、Hashtable实现Enumeration时&＃xff0c;添加了同步。而Iterator 是JDK 1.2才添加的接口&＃xff0c;它也是为了HashMap、ArrayList等集合提供遍历接口。Iterator是支持fail-fast机制的&＃xff1a;当多个线程对同一个集合的内容进行操作时&＃xff0c;就可能会产生fail-fast事件

Comparable 和 Comparator接口有何区别&＃xff1f;

Java中对集合对象或者数组对象排序&＃xff0c;有两种实现方式&＃xff1a;

• 对象实现Comparable 接口
  • Comparable 在 java.lang 包下&＃xff0c;是一个接口&＃xff0c;内部只有一个方法 compareTo()
  • Comparable 可以让实现它的类的对象进行比较&＃xff0c;具体的比较规则是按照 compareTo 方法中的规则进行。这种顺序称为 自然顺序。
  • 实现了 Comparable 接口的 List 或则数组可以使用 Collections.sort() 或者 Arrays.sort() 方法进行排序
• 定义比较器&＃xff0c;实现 Comparator接口
  • Comparator 在 java.util 包下&＃xff0c;也是一个接口&＃xff0c;JDK 1.8 以前只有两个方法&＃xff1a;comparable相当于内部比较器。comparator相当于外部比较器

区别&＃xff1a;

• Comparator 位于 java.util 包下&＃xff0c;而 Comparable 位于 java.lang 包下
• Comparable 接口的实现是在类的内部(如 String、Integer已经实现了 Comparable 接口&＃xff0c;自己就可以完成比较大小操作)&＃xff0c;Comparator 接口的实现是在类的外部(可以理解为一个是自已完成比较&＃xff0c;一个是外部程序实现比较)
• 实现 Comparable 接口要重写 compareTo 方法, 在 compareTo 方法里面实现比较。一个已经实现Comparable 的类的对象或数据&＃xff0c;可以通过 Collections.sort(list) 或者 Arrays.sort(arr)实现排序。通过 Collections.sort(list,Collections.reverseOrder()) 对list进行倒序排列。
• 实现Comparator需要重写 compare 方法

HashSet

HashSet是用来存储没有重复元素的集合类&＃xff0c;并且它是无序的。HashSet 内部实现是基于 HashMap &＃xff0c;实现了 Set 接口。

从 HahSet 提供的构造器可以看出&＃xff0c;除了最后一个 HashSet 的构造方法外&＃xff0c;其他所有内部就是去创建一个 Hashap 。没有其他的操作。而最后一个构造方法不是 public 的&＃xff0c;所以不对外公开。

HashSet如何检查重复

HashSet的底层其实就是HashMap&＃xff0c;只不过我们HashSet是实现了Set接口并且把数据作为K值&＃xff0c;而V值一直使用一个相同的虚值来保存&＃xff0c;HashMap的K值本身就不允许重复&＃xff0c;并且在HashMap中如果K/V相同时&＃xff0c;会用新的V覆盖掉旧的V&＃xff0c;然后返回旧的V。

Iterater 和 ListIterator 之间有什么区别&＃xff1f;

• 我们可以使用Iterator来遍历Set和List集合&＃xff0c;而ListIterator只能遍历List
• ListIterator有add方法&＃xff0c;可以向List中添加对象&＃xff0c;而Iterator不能
• ListIterator和Iterator都有hasNext()和next()方法&＃xff0c;可以实现顺序向后遍历&＃xff0c;但是ListIterator有hasPrevious()和previous()方法&＃xff0c;可以实现逆向(顺序向前)遍历。Iterator不可以
• ListIterator可以定位当前索引的位置&＃xff0c;nextIndex()和previousIndex()可以实现。Iterator没有此功能
• 都可实现删除操作&＃xff0c;但是 ListIterator可以实现对象的修改&＃xff0c;set()方法可以实现。Iterator仅能遍历&＃xff0c;不能修改

参考与感谢

所有内容都是基于源码阅读和各种大佬之前总结的知识整理而来&＃xff0c;输入并输出&＃xff0c;奥利给。

• https://www.javatpoint.com/java-arraylist
• https://www.runoob.com/java/java-collections.html
• https://www.javazhiyin.com/21717.html
• https://yuqirong.me/2018/01/31/LinkedList内部原理解析/
• https://youzhixueyuan.com/the-underlying-structure-and-principle-of-hashmap.html
• 《HashMap源码详细分析》http://www.tianxiaobo.com/2018/01/18/HashMap-源码详细分析-JDK1-8
• 《ConcurrentHashMap1.7源码分析》https://www.cnblogs.com/chengxiao/p/6842045.html
• http://www.justdojava.com/2019/12/18/java-collection-15.1/