集合的介绍

Java 集合是一个存储相同类型数据的容器,类似数组,集合可以不指定长度,但是数组必须指定长度。集合类主要从** Collection 和 Map **两个根接口派生出来,比如常用的 ArrayList、LinkedList、HashMap、HashSet、ConcurrentHashMap 等等。
Collection 根接口框架结构图
图片说明

Map 根接口框架结构图
图片说明

List

ArrayList

ArrayList 是基于动态数组实现,容量能自动增长的集合。随机访问效率高,随机插入、随机删除效率低。线程不安全,多线程环境下可以使用 Collections.synchronizedList(list) 函数返回一个线程安全的 ArrayList 类,也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

动态数组,是指当数组容量不足以存放新的元素时,会创建新的数组,然后把原数组中的内容复制到新数组。
主要属性:

//存储实际数据,使用transient修饰,序列化的时不会被保存
transient Object[] elementData;
//元素的数量,即容量。
private int size;


特征:

  1. 允许元素为 null;
  2. 查询效率高、插入、删除效率低,因为大量 copy 原来元素;
  3. 线程不安全。

使用场景:

  1. 需要快速随机访问元素
  2. 单线程环境

add(element) 流程:

  1. 判断当前数组是否为空,如果是则创建长度为 10(默认)的数组,因为 new ArrayList 的时是没有初始化;
  2. 判断是否需要扩容,如果当前数组的长度加 1(即 size+1)后是否大于当前数组长度,则进行扩容 grow();
  3. 最后在数组末尾添加元素,并 size+1。【最后才进行size+1】

grow() 流程:

  1. 创建新数组,长度扩大为原数组的 1.5 倍;
  2. 如果扩大 1.5 倍还是不够,则根据实际长度来扩容,比如 addAll() 场景;
  3. 将原数组的数据使用 System.arraycopy(native 方法)复制到新数组中。


add(index,element) 流程:

  1. 检查 index 是否在数组范围内,假如数组长度是 2,则 index 必须 >=0 并且 <=2,否则报 IndexOutOfBoundsException 异常;
  2. 扩容检查;
  3. 通过拷贝方式,把数组位置为 index 至 size-1 的元素都往后移动一位,腾出位置之后放入元素,并 size+1。

set(index,element) 流程:

  1. 检查 index 是否在数组范围内,假如数组长度是 2,则 index 必须 >=0 并且 <2;
  2. 保留被覆盖的值,因为最后需要返回旧的值;
  3. 新元素覆盖位置为 index 的旧元素,返回旧值。

get(index) 流程:

  1. 判断下标有没有越界;
  2. 通过数组下标来获取元素,get 的时间复杂度是 O(1)。

remove(index) 流程:

  1. 检查指定位置是否在数组范围内,假如数组长度是 2,则 index 必须 >=0 并且 < 2;
  2. 保留要删除的值,因为最后需要返回旧的值;
  3. 计算出需要移动元素个数,再通过拷贝使数组内位置为 index+1 到 size-1 的元素往前移动一位,把数组最后一个元素设置为 null(精辟小技巧),返回旧值。

注意事项:

  1. new ArrayList 创建对象时,如果没有指定集合容量则初始化为 10, size是0;如果有指定,则按照指定的大小初始化;
  2. 扩容时,先将集合扩大 1.5 倍,如果还是不够,则根据实际长度来扩容,保证都能存储所有数据,比如 addAll() 场景。
  3. 如果新扩容后数组长度大于(Integer.MAX_VALUE-8),则抛出 OutOfMemoryError。

LinkedList

LinkedList 是可以在任何位置进行插入移除操作的有序集合,它是基于双向链表实现的,线程不安全。LinkedList 功能比较强大,可以实现队列双向队列

主要属性:

//链表长度 transient int size = 0; //头部节点 transient Node<E> first; //尾部节点 transient Node<E> last; /**
* 静态内部类,存储数据的节点
*/ private static class Node<E> { //自身结点 E item; //下一个节点 Node<E> next; //上一个节点 Node<E> prev;
}

数据结构:双向链表

特征:

  1. 允许元素为 null;
  2. 插入和删除效率高,查询效率低;
  3. 顺序访问会非常高效,而随机访问效率(比如 get 方法)比较低;
  4. 既能实现栈 Stack(后进先出),也能实现队列(先进先出), 也能实现双向队列,因为提供了 xxxFirst()、xxxLast() 等方法;
  5. 线程不安全。

使用场景:

  1. 需要快速插入,删除元素
  2. 按照顺序访问其中的元素
  3. 单线程环境

add() 流程:

  1. 创建一个新结点,结点元素 item 为传入参数,前继节点 prev 为“当前链表 last 结点”,后继节点 next 为 null;
  2. 判断当前链表 last 结点是否为空,如果是则把新建结点作为头结点,如果不是则把新结点作为 last 结点。
  3. 最后返回 true。

get(index,element) 流程:

  1. 检查 index 是否在数组范围内,假如数组长度是 2,则 index 必须 >=0 并且 < 2;
  2. index 小于“双向链表长度的 1/2”则从头开始往后遍历查找,否则从链表末尾开始向前遍历查找。

remove() 流程:

  1. 判断 first 结点是否为空,如果是则报 NoSuchElementException 异常;
  2. 如果不为空,则把待删除结点的 next 结点的 prev 属性赋值为 null,达到删除头结点的效果。
  3. 返回删除值。

Vector

Vector 是矢量队列,也是基于动态数组实现,容量可以自动扩容。跟 ArrayList 实现原理一样,但是 Vector 是线程安全,使用 Synchronized 实现线程安全,性能非常差,已被淘汰,使用 CopyOnWriteArrayList 替代 Vector

pyOnWriteArrayList 替代 Vector

主要属性:

//存储实际数据 protected Object[] elementData; //动态数组的实际大小 protected int elementCount; //动态数组的扩容系数 protected int capacityIncrement;

特征:

  1. 允许元素为 null;
  2. 查询效率高、插入、删除效率低,因为需要移动元素;
  3. 默认的初始化大小为 10,没有指定增长系数则每次都是扩容一倍,如果扩容后还不够,则直接根据参数长度来扩容;
  4. 线程安全,性能差(Synchronized),使用 CopyOnWriteArrayList 替代 Vector。
使用场景:多线程环境

 ArrayList 和 Vector 区别

  1. Vector 线程安全,ArrayList 线程不安全;
  2. ArrayList 在扩容时默认是扩展 1.5 倍,Vector 是默认扩展 1 倍;
  3. ArrayList 支持序列化,Vector 不支持;
  4. Vector 提供 indexOf(obj, start) 接口,ArrayList 没有;
  5. Vector 构造函数可以指定扩容增加系数,ArrayList 不可以。

 ArrayList 与 LinkedList 的区别

  1. ArrayList 的数据结构是动态数组,LinkedList 的数据结构是链表;
  2. ArrayList 不支持高效的插入和删除元素,LinkedList 不支持高效的随机访问元素;
  3. ArrayList 的空间浪费在数组末尾预留一定的容量空间,LinkedList 的空间浪费在每一个结点都要消耗空间来存储 prev、next 等信息。

Stack

Stack 是栈,先进后出原则,Stack 继承 Vector,也是通过数组实现,线程安全。因为效率比较低,不推荐使用,可以使用 LinkedList(线程不安全)或者 ConcurrentLinkedDeque(线程安全)来实现先进先出的效果。

数据结构:动态数组

构造函数:只有一个默认 Stack()

特征:先进后出

实现原理:

  1. Stack 执行 push() 时,将数据推进栈,即把数据追加到数组的末尾。
  2. Stack 执行 peek 时,取出栈顶数据,不删除此数据,即获取数组首个元素。
  3. Stack 执行 pop 时,取出栈顶数据,在栈顶删除数据,即删除数组首个元素。
  4. Stack 继承于 Vector,所以 Vector 拥有的属性和功能,Stack 都拥有,比如 add()、set() 等等。

CopyOnWriteArrayList


CopyOnWriteArrayList 是线程安全的 ArrayList,写操作(add、set、remove 等等)时,把原数组拷贝一份出来,然后在新数组进行写操作,操作完后,再将原数组引用指向到新数组。CopyOnWriteArrayList 可以替代 Collections.synchronizedList(List list)。

数据结构:动态数组

特征:

  1. 线程安全;
  2. 读多写少,比如缓存;
  3. 不能保证实时一致性,只能保证最终一致性。

缺点:

  1. 写操作,需要拷贝数组,比较消耗内存,如果原数组容量大的情况下,可能触发频繁的 Young GC 或者 Full GC;
  2. 不能用于实时读的场景,因为读取到数据可能是旧的,可以保证最终一致性。

实现原理:

CopyOnWriteArrayList 写操作加了锁,不然多线程进行写操作时会复制多个副本;读操作没有加锁,所以可以实现并发读,但是可能读到旧的数据,比如正在执行读操作时,同时有多个写操作在进行,遇到这种场景时,就会都到旧数据。

CopyOnWriteArraySet

CopyOnWriteArraySet 是线程安全的无序并且不能重复的集合,可以认为是线程安全的 HashSet,底层是通过 CopyOnWriteArrayList 机制实现。

数据结构:**动态数组(CopyOnWriteArrayList),并不是散列表。**

特征:

  1. 线程安全
  2. 读多写少,比如缓存
  3. 不能存储重复元素

Set


HashSet

HashSet 是用来存储没有重复元素的集合类并且是无序的。实现了 Set 接口。底层使用 HashMap 机制实现,所以也是线程不安全

主要属性:

//定义了一个HashMap类型的成员变量,即拥有HashMap的所有属性 private transient HashMap<E,Object> map;

特征:

  1. 不可重复
  2. 无序
  3. 线程不安全
  4. 集合元素可以是 null,但只能放入一个 null

使用场景:去重、不要求顺序

原理:底层使用 HashMap 的 key 不能重复机制来实现没有重复的 HashSet。

TreeSet

TreeSet 实现了 SortedSet 接口,意味着可以排序,它是一个有序并且没有重复的集合类,底层是通过 TreeMap 实现。TreeSet 并不是根据插入的顺序来排序,而是字典自然排序。线程不安全

TreeSet 支持两种排序方式:自然升序排序自定义排序

特征:

  1. 不可重复
  2. 有序,默认自然升序排序
  3. 线程不安全
  4. 集合元素不可以为 null

原理:

TreeSet 底层是基于 treeMap(红黑树结构)实现的,可以自定义比较器对元素进行排序,或是使用元素的自然顺序。

使用场景:去重、要求排序

 LinkedHashSet

LinkedHashSet 是使用 HashSet 机制实现,它是一个可以保证插入顺序或是访问顺序,并且没有重复的集合类。线程不安全

数据结构:数组 + 双向链表,Entry 结构:before|hash|key|value|next|after,before 和 after 用于维护整个双向链表。

特征:

  1. 集合元素不可以为 null;
  2. 线程不安全。

原理:

LinkedHashSet 底层使用了 LinkedHashMap 机制(比如 before 和 after),加上又继承了 HashSet,所以可以实现既可以保证迭代顺序,又可以达到不出现重复元素。

使用场景:去重、需要保证插入或者访问顺序

HashSet、TreeSet、LinkedHashSet 的区别

HashSet,TreeSet,LinkedHashSet 之间的区别:HashSet 只去重,TreeSet 去重并排序,LinkedHashSet 去重并保证迭代顺序。

Queue

Queue 是一个先入先出(FIFO)的集合,它有 3 种实现方式:阻塞队列、非阻塞队列、双向队列。Queue 跟 List、Set 一样,也是继承了 Collection 接口。

阻塞队列

阻塞队列是一个可以阻塞的先进先出集合,比如某个线程在空队列获取元素时、或者在已存满队列存储元素时,都会被阻塞。BlockingQueue 接口常用的实现类如下:

  • ArrayBlockingQueue :基于数组的有界阻塞队列,必须指定大小。
  • LinkedBlockingQueue :基于单链表的无界阻塞队列,不需指定大小。
  • PriorityBlockingQueue :基于最小二叉堆的无界、优先级阻塞队列。
  • DelayQueue:基于延迟、优先级、无界阻塞队列。
  • SynchronousQueue :基于 CAS 的阻塞队列。

常用方法:

  • add():新增一个元索,假如队列已满,则抛异常。
  • offer():新增一个元素,假如队列没满则返回 true,假如队列已满,则返回 false。
  • put():新增一个元素,假如队列满,则阻塞。
  • element():获取队列头部一个元素,假如队列为空,则抛异常。
  • peek():获取队列头部一个元素,假如队列为空,则返回 null。
  • remove():执行删除操作,返回队列头部的元素,假如队列为空,则抛异常。
  • poll():执行删除操作,返回队列头部的元素,假如队列为空,则返回 null。
  • take():执行删除操作,返回队列头部的元素,假如队列为空,则阻塞。

非阻塞队列

非阻塞队列是使用CAS(compare and set)机制实现,类似 volatile,并发性能好。常用的非阻塞队列有 PriorityQueue 和 ConcurrentLinkedQueue。

  • PriorityQueue :基于优先级的无界优先级队列
  • ConcurrentLinkedDeque:基于双向链表结构的无界并发队列。

双端队列(Deque)

Deque 是一个既可以在头部操作元素,又可以为尾部操作元素,俗称为双向(双端)队列。Deque 继承自 Queue,Deque 实现类有 LinkedList、 ArrayDeque、ConcurrentLinkedDeque 等等。

  • LinkedList:基于单链表的无界双端队列,允许元素为 null。
  • ArrayDeque:基于数组的有界双端队列,不允许 null。


Map

HashMap

HashMap 是以key-value 键值对形式存储数据,允许 key 为 null(多个则覆盖),也允许 value 为 null。底层结构是数组 + 链表 + 红黑树。

主要属性:

  • initialCapacity:初始容量,默认 16,2 的 N 次方。
  • loadFactor:负载因子,默认 0.75,用于扩容。
  • threshold:阈值,等于 initialCapacity * loadFactor,比如:16 * 0.75 = 12。
  • size:存放元素的个数,非 Node 数组长度。
  • Node
//存储元素的数组
transient Node<K,V>[] table;
//存放元素的个数,非Node数组长度
transient int size;
//记录结构性修改次数,用于快速失败
transient int modCount;
//阈值
int threshold;
//负载因子,默认0.75,用于扩容
final float loadFactor;

 /**
 * 静态内部类,存储数据的节点 
 */
static class Node<K,V> implements Map.Entry<K,V> {
    //节点的hash值
    final int hash;
    //节点的key值
    final K key;
    //节点的value值
    V value;
    //下一个节点的引用
    Node<K,V> next;
}

特征:

  1. 只允许一个 key 为 Null(多个则覆盖),但允许多个 value 为 Null
  2. 查询、插入、删除效率都高(集成了数组和单链表的特性)
  3. 默认的初始化大小为 16,之后每次扩充为原来的 2 倍
  4. 线程不安全

使用场景:

  1. 快速增删改查
  2. 随机存取
  3. 缓存

哈希冲突的解决方案:

  1. 开放定址法
  2. 再散列函数法
  3. 链地址法(拉链法,常用)

put() 存储的流程(Java 8):

  1. 计算待新增数据 key 的 hash 值;

  2. 判断 Node[] 数组是否为空或者数据长度为 0 的情况,则需要进行初始化;

  3. 根据 hash 值通过位运算定计算出 Node 数组的下标,判断该数组第一个 Node 节点是否有数据,如果没有数据,则插入新值;

  4. 如果有数据,则根据具体情况进行操作,如下:

    • 如果该 Node 结点的 key(即链表头结点)与待新增的 key 相等(== 或者 equals),则直接覆盖值,最后返回旧值;
    • 如果该结构是树形,则按照树的方式插入新值;
    • 如果是链表结构,则判断链表长度是否大于阈值 8,如果 >=8 并且数组长度 >=64 才转为红黑树,如果 >=8 并且数组长度 < 64 则进行扩容;
    • 如果不需要转为红黑树,则遍历链表,如果找到 key 和 hash 值同时相等,则进行覆盖返回旧值,如果没有找到,则将新值插入到链表的最后面(尾插法);
  5. 判断数组长度是否大于阈值,如果是则进入扩容阶段。【最后在进行扩容】

resize() 扩容的流程(Java 8): 【欠缺完善】

扩容过程比较复杂, 迁移算法与 Java 7 不一样,Java 8 不需要每个元素都重新计算 hash,迁移过程中元素的位置要么是在原位置,要么是在原位置再移动 2 次幂的位置。

我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash【头插】,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap(扩容前的容量)


get() 查询的流程(Java 8):

  1. 根据 put() 方法的方式计算出数组的下标;
  2. 遍历数组下标对应的链表,如果找到 key 和 hash 值同时相等就返回对应的值,否则返回 null。

get() 注意事项Java 8 没有把 key 为 null 放到数组 table[0] 中。 ???

remove() 删除的流程(Java 8):

  1. 根据 get() 方法的方式计算出数组的下标,即定位到存储删除元素的 Node 结点;
  2. 如果待删结点是头节点,则用它的 next 结点顶替它作为头节点;
  3. 如果待删结点是红黑树结点,则直接调用红黑树的删除方法进行删除;
  4. 如果待删结点是链表中的一个节点,则用待删除结点的前一个节点的 next 属性指向它的 next 结点;
  5. 如果删除成功则返回被删结点的 value,否则返回 null。

remove() 注意事项:删除单个 key,注意返回是的键值对中的 value。

为什么使用位运算(&)来代替取模运算(%):

  1. 效率高,位运算直接对内存数据进行操作,不需转成十进制,因此处理速度非常快;
  2. 可以解决负数问题,比如:-17 % 10 = -7。

HashMap 在 Java 7 和 Java 8 中的区别:

  1. 存放数据的结点名称不同,作用都一样,存的都是 hashcode、key、value、next 等数据:

    • Java 7:使用 Entry 存放数据
    • Java 8:改名为 Node
  2. 定位数组下标位置方法不同:

    • Java 7:计算 key 的 hash,将 hash 值进行了四次扰动,再进行取模得出;
    • Java 8:计算 key 的 hash,将 hash 值进行高 16 位异或低 16 位,再进行与运算得出。
  3. 扩容算法不同:

    • Java 7:扩容要重新计算 hash
    • Java 8:不用重新计算
  4. put 方法插入链表位置不同:

    • Java 7:头插法
    • Java 8:尾插法
  5. Java 8 引入了红黑树,当链表长度 >=8 时,并且同时数组的长度 >=64 时链表就转换为红黑树,利用红黑树快速增删改查的特点提高 HashMap 的性能。

 HashTable

和 HashMap 一样,Hashtable 也是一个哈希散列表,Hashtable 继承于 Dictionary,使用重入锁 Synchronized 实现线程安全,key 和 value 都不允许为 Null。HashTable 已被高性能的 ConcurrentHashMap 代替

主要属性:

  • initialCapacity:初始容量,默认 11。
  • loadFactor:负载因子,默认 0.75。
  • threshold:阈值。
  • modCount:记录结构性修改次数,用于快速失败。
/真正存储数据的数组
private transient Entry<?,?>[] table;
//存放元素的个数,非Entry数组长度
private transient int count;
//阈值
private int threshold;
//负载因子,默认0.75
private float loadFactor;
//记录结构性修改次数,用于快速失败
private transient int modCount = 0;

/**
* 静态内部类,存储数据的节点
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
    //节点的hash值
    final int hash;
    //节点的key值
    final K key;
    //节点的value值
    V value;
    //下一个节点的引用
    Entry<K,V> next;
}
快速失败原理是在并发场景下进行遍历操作时,如果有另外一个线程对它执行了写操作,此时迭代器可以发现并抛出 ConcurrentModificationException,而不需等到遍历完后才报异常。


数据结构:链表的数组,数组 + 链表,Entry 结构:hash|key|value|next

特征:

  1. key 和 value 都不允许为 Null;
  2. HashTable 默认的初始大小为 11,之后每次扩充为原来的 2 倍;
  3. 线程安全。

原理:

与 HashMap 不一样的流程是定位数组下标逻辑,HashTable 是在 key.hashcode() 后使用取模,HashMap 是位运算。HashTable 是 put() 之前进行判断是否扩容 resize(),而 HashMap 是 put() 之后扩容


ConcurrentHashMap

ConcurrentHashMap 在 Java 8 版本中丢弃了 Segment(分锁段)、ReentrantLock、HashEntry 数组这些概念,而是采用CAS + Synchronized 实现锁操作Node 改名为 HashEntry,引入了红黑树保证查询效率,底层数据结构由数组 + 链表 + 红黑树组成,Node 数组默认为 16

数据结构(Java 8):Node[] 数组 + 单链表 + 红黑树

put() 存储的流程(Java 8):

  1. 判断待新增数据 key 和 value 是否为空,如果是则抛空指针异常;
  2. 计算待新增数据 key 的 hash 值;
  3. 判断 Node[] 数组是否为空或者数据长度为 0 的情况,则需要进行初始化;
  4. 根据 hash 值通过位运算定计算出 Node 数组的下标,【判断该数组第一个 Node 节点是否有数据,如果没有数据,则使用 CAS 操作将这个新值插入;】 先尝试轻量级锁来进行解锁,后面复杂的在进行synchized进行加锁。
  5. 如果有数据,则判断头结点的 hashCode 是否等于 MOVED(即 -1),即检查是否正在扩容,如果等于 - 1 则帮助扩容;【头节点的hashcode值还有妙用,正在扩容,你来帮我扩容,还能根据hashcode判断我采用的是什么数据结构】
  6. 如果有数据,则对头结点进行加锁(synchronized),如果头结点的 hashCode>=0,说明是链表,遍历链表,如果找到 key 和 hash 值同时相等,则进行覆盖,如果没有找到,则将新值插入到链表的最后面(尾插法);如果 hashCode<0,说明是红黑树,调用红黑树的插值方法插入新节点;
  7. 插值完成之后,判断链表元素是否 >=8,如果 >=8 并且数组长度 >=64 才转为红黑树,如果 >=8 并且数组长度 < 64 则进行扩容

resize() 扩容的流程(Java 8):

扩容的原理是创建新的数组,长度是原来的两倍,然后把旧数组数据迁移到新的数组中,在多线程情况下,需要注意线程安全问题,在解决安全问题的同时,还需要关注其效率。

get() 查询的流程(Java 8):

  1. 计算获取数据 key 的 hash 值;
  2. 根据 hashCode 通过位运算定得到 Node 数组的下标,即得到头节点;
  3. 如果头结点为空,则返回 null;
  4. 如果头结点的 key 与参数 key 可以相等,则返回头结点的值;
  5. 如果头结点的 hashCode 小于 0,说明是红黑树,则调用 find() 方法按照树的方式获取值;
  6. 如果都不满足 3、4 和 5 条件,说明是链表,则按照链表的方式遍历获取值。整个过程都不需要加锁。

get() 注意事项:

整个过程都不需要加锁,【因为读取数据的属性使用 volatile 修饰,实现线程可见性。】

remove() 删除的流程(Java 8):

  1. 计算待新增数据 key 的 hash 值;
  2. 判断 Node[] 数组是否为空或者数据长度为 0 的情况,如果是则返回 null;如果不是则根据 hashCode 通过位运算定得到 Node 数组的下标,即得到头结点;
  3. 判断头结点的 hashCode 是否等于 MOVED(即 -1),检查是否正在扩容,如果是则帮助扩容;
  4. 如果都不满足 2 和 3 条件,则加锁进行删除操作;【直接加锁删除】
  5. 首先判断头结点有无发生变化(步骤 3 点转移操作会改变头结点),如果有改变则返回 null;
  6. 如果头结点的 hashCode 大于 0 说明是链表,则按照链表方式遍历删值;
  7. 如果头结点是 TreeBin 类型,说明是红黑树,则按照树的方式删值。

remove() 注意事项:

remove 函数底层是调用 replaceNode 函数实现结点的删除。

使用场景:并发、线程不安全场景

ConcurrentHashMap 在 Java 7 和 Java 8 中的区别:

  1. Java 7 使用 Segment 分段加锁机制,Segment 继承 ReentrantLock 实现锁操作,而 Java 8 使用 CAS + Synchronized 实现锁操作;
  2. Java 7 查询时遍历链表效率低,而 Java 8 采用红黑树提高查询效率;
  3. Java 7 使用 HashEntry 存放数据,而 Java 8 改名为 Node,作用都是一样,存放的都是 hashcode、key、value、next 等数据。
  4. Java 7 是把数据插入到链表的表头(头插法),而 Java 8 是将数据插入到链表的最后面(尾插法);
  5. Java 7 先扩容,再插值,而 Java 8 先插值,再扩容;
  6. Java 7 的最大并发个数是 Segment 的个数默认值是 16,锁住整个段,不影响其他段;而 Java 8 去掉了分段锁,更细粒度,只锁住一个 Node 节点,不影响其他 Node 节点;
  7. Java 7 在扩容时锁住一个段,当前段可读不能写,其他段可读写,只开启一个线程执行扩容操作;而 Java 8 锁住一个 Node 结点,当前结点可读不能写,其他结点可读写,【1 个线程执行扩容 + 可能多个 put()/remove 线程帮助扩容。】

HashMap、Hashtable、ConccurentHashMap 三者的区别(Java 8):

  1. HashMap 线程不安全,没有锁机制,数组 + 链表 + 红黑树
  2. Hashtable 线程安全,锁住整个对象,数组 + 链表
  3. ConccurentHashMap 线程安全,CAS+Synchronized,数组 + 链表 + 红黑树
  4. HashMap 的 key 和 value 都可为 null,其他两个都不可以。


TreeMap

TreeMap 实现了 SotredMap 接口,意味着可以排序,是一个有序的集合。底层数据结构是红黑树结构,TreeMap 中的每个元素都存放在红黑树的节点上,默认使用自然排序,也可以自定排序,线程不安全。
主要属性:
//排序比较器
private final Comparator<? super K> comparator;
//红黑树根节点
private transient Entry<K,V> root;
//集合长度
private transient int size = 0;
//记录结构性修改次数,用于快速失败
private transient int modCount = 0;

//红黑树常量
private static final boolean RED   = false;
private static final boolean BLACK = true;

/**
* 实际存储数据的节点 
*/
static final class Entry<K,V> implements Map.Entry<K,V> {
    //节点的key值
    K key;
    //节点的value值
    V value;
    //左子树引用
    Entry<K,V> left;
    //右子树引用
    Entry<K,V> right;
    //父节点引用
    Entry<K,V> parent;
    //节点颜色(默认黑色)
    boolean color = BLACK;
}

数据结构:红黑树(高效的检索二叉树),Entry 结构:key|value|left|right|parent|color

特征:

  1. key 不允许为 Null,但允许多个 value 为 Null
  2. 线程不安全

put() 存储的流程:

主要分为两个步骤,构建排序二叉树构建平衡二叉树

构建排序二叉树,过程如下:

  1. 从根节点 root 开始查找;
  2. 如果 root 节点比待插入节点值小,则在 root 节点左子树查找,如果大于,则在右子树查找;
  3. 递归循环步骤 2,找到合适的节点为止;
  4. 把待插入节点与步骤 3 中找到的节点进行比较,如果待插入节点小于找到节点,则把待插入节点作为左子节点;否则作为右子节点。
构建平衡二叉树,经过左旋、右旋、着色这些步骤后,得到一棵平衡二叉树。


remove() 的流程:比 put() 复杂,也是分两个步骤,删除节点着色旋转

删除节点,删除时出现以下 3 种情况:

  1. 待删除节点,如果没有左和右子节点时,则直接删除;
  2. 待删除节点,如果有一个子节点时,则把它的子节点指向它的上级节点(即父节点);
  3. 待删除节点,如果有两个非空的子节点时,流程复杂,暂不在此解释。

着色旋转,进行颜色的对调和旋转,达到红黑树的特征。

LinkedHashMap

LinkedHashMap 是使用 HashMap 机制实现。LinkedHashMap 在 HashMap 的基础上增加 before 和 after 两个属性来保证了迭代顺序。迭代顺序可以是插入顺序(默认),也可以是访问顺序。线程不安全

主要属性:

/**
* 静态内部类,存储数据的节点
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

//头结点
transient LinkedHashMap.Entry<K,V> head;
//尾结点
transient LinkedHashMap.Entry<K,V> tail;
//排序标识,true访问顺序迭代; false插入顺序迭代(默认)
final boolean accessOrder;
数据结构:数组 + 双向链表,Entry 结构:before|hash|key|value|next|after,before 和 after 用于维护整个双向链表。

特征:

  1. 只允许一个 key 为 Null(多个则覆盖),允许多个 value 为 Null;
  2. 线程不安全。

原理:

LinkedHashMap 继承了 HashMap,hash 算法也是跟 HashMap 一致。LinkedHashMap 在 Entry 中新增了 before 和 after 两个属性来维护双向链表的迭代顺序。Entry 的 next 属性是维护 Entry 连接顺序,而 after 是维护迭代顺序。LinkedHashMap 使用 LRU 算法实现访问顺序排序,比如 get() 操作后的元素会移动到链表末尾,从而实现按访问顺序迭代。

使用场景:保证插入和访问顺序

插入顺序(默认)和访问顺序区别

WeakHashMap

WeakHashMap 中的 Weak 是“弱”的含义,即弱化版的 HashMap。key 和 value 都允许为 null,线程不安全。

HashMap 与 Hashtable 的区别

  1. HashMap 只允许一个 key 为 Null(多个则覆盖),允许多个 value 为 Null,HashTable 中的 key 和 value 都不允许为 null;
  2. HashMap 线程不安全,效率高,HashTable 线程安全,效率低;
  3. HashMap 和 Hashtable 二者都实现了 Map 接口,HashMap 是继承于 AbstractMap,HashTable 继承于 Dictionary 类;
  4. 定位存储位置逻辑不一样,HashMap 是在 key.hashcode() 后使用位运算,HashTable 是在 key.hashcode() 后使用取模;
  5. 判断扩容顺序不一样,HashMap 是 put() 之后扩容,HashTabel 是 put() 之前扩容;
  6. 初始容量不一样,HashMap 默认 16,HashTabel 默认 11。

HashMap 与 TreeMap 的区别

  1. 数据结构不一样,HashMap 基于“数组 + 单链表”实现(达到一定条件时转为红黑树),TreeMap 基于红黑树实现 ;
  2. HashMap 随机存储,TreeMap 默认按 key 的字典升序排序;
  3. HashMap 只允许一个 key 为 Null(多个则覆盖),允许多个 value 为 Null,TreeMap 的 key 不允许为 Null,但允许多个 value 为 Null;
  4. HashMap 效率高,TreeMap 效率低。