JAVA集合源码-Map

本文最后更新于：May 10, 2022 am

积土成山，风雨兴焉；积水成渊，蛟龙生焉；积善成德，而神明自得，圣心备焉。故不积跬步，无以至千里，不积小流无以成江海。齐骥一跃，不能十步，驽马十驾，功不在舍。面对悬崖峭壁，一百年也看不出一条裂缝来，但用斧凿，能进一寸进一寸，能进一尺进一尺，不断积累，飞跃必来，突破随之。

目录

Set用于存储不重复的元素集合。

  • HashSet是无序的，因为它实现了Set接口，并没有实现SortedSet接口；
  • TreeSet是有序的，因为它实现了SortedSet接口。

HashMap源码分析

非线程安全的。HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。（存储结构理解成邻接表）

  • 在JDK8中，HashMap底层是采用“数组+链表+红黑树”来实现的。HashMap是基于哈希算法来确定元素的位置的，当我们向集合中存入数据时，它会计算传入的Key的哈希值，并利用哈希值取余（对当前数组的长度进行取余）来确定数组的位置。如果这个数组已经存在其他的元素了，则HashMap会通过链表将这些元素组织起来。遍历链表查看是否存在相同的（通过equals进行比较），如果存在相同则进行覆盖，否则添加进去。如果有链表长度大于8但数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树；如果链表长度大于8且数组长度大于64则才会将链表转化为红黑树，从而提高对这个槽中数据的查找的速度（O(logn)）。若链表的长度小于等于6时，红黑树会退化为数组+链表。

  • HashMap中，数组的默认初始容量为16，这个容量会以2的指数（即两倍扩容）进行扩容。具体来说，当数组中的元素达到一定比例的时候HashMap就会扩容，这个比例叫做负载因子，默认为0.75。自动扩容机制，是为了保证HashMap初始时不必占据太大的内存，而在使用期间又可以实时保证有足够大的空间。采用2的指数（即两倍扩容）进行扩容，是为了利用位运算，提高扩容运算的效率。

    创建时如果给定了容量初始值， HashMap 会将其扩充为 2的幂次方大小（HashMap 中的tableSizeFor()方法保证，可见下方源码）。

  • HashMap是非线程安全的，所以在多线程环境下，各线程同时触发HashMap的改变时，都有可能会发生冲突。所以，在多线程环境下不建议使用HashMap，可以考虑使用Collections将HashMap转为线程安全的HashMap，更为推荐的方式则是使用ConcurrentHashMap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 数组
transient Node<K,V>[] table;
 
// 链表
static class Node<K,V> implements Map.Entry<K,V> {
    ...
    Node<K,V> next;
}

// 红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}


// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// 最大容量（2^30）
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 转为树的临界点
static final int TREEIFY_THRESHOLD = 8;

// 转链表的临界点
static final int UNTREEIFY_THRESHOLD = 6;

// 支持树结构的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

指定大小创建，保证了 HashMap 总是使用2的幂作为哈希表的大小。：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static final int MAXIMUM_CAPACITY = 1 << 30;

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

System.out.println(tableSizeFor(7)); //8
System.out.println(tableSizeFor(10)); //16

put方法

  1. 根据key通过哈希算法与与运算得出数组下标。
  2. 如果数组下标元素为空，则将key和value封装为Entry对象（JDK1.7是Entry对象，JDK1.8是Node对象）并放入该位置。
  3. 如果数组下标位置元素不为空，则要分情况：
  • 如果是在JDK1.7，则首先会判断是否需要扩容，如果要扩容就进行扩容，如果不需要扩容就生成Entry对象，并使用头插法添加到当前链表中。
  • 如果是在JDK1.8中，则会先判断当前位置上的TreeNode类型，看是红黑树还是链表Node。

如果是红黑树TreeNode，则将key和value封装为一个红黑树节点并添加到红黑树中去，在这个过程中会判断红黑树中是否存在当前key，如果存在则更新value。

如果此位置上的Node对象是链表节点，则将key和value封装为一个Node并通过尾插法插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历过程中会判断是否存在当前key，如果存在则更新其value，当遍历完链表后，将新的Node插入到链表中，插入到链表后，会看当前链表的节点个数，如果大于8，则会将链表转为红黑树

将key和value封装为Node插入到链表或红黑树后，在判断是否需要扩容，如果需要扩容，就结束put方法。

Hashtable源码分析

线程安全的。HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。但，Hashtable 基本被淘汰，不要在代码中使用它。具体原因

  • 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。
1
2
3
4
public Hashtable() {
  this(11, 0.75f); //默认11
}

  • 创建时如果给定了容量初始值，那么 Hashtable 会直接使用给定的大小。
1
2
3
public Hashtable(int initialCapacity) {
  this(initialCapacity, 0.75f);
}

ConcurrentHashMap源码分析

线程安全。

采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。