Java 集合 - HashMap
# HashMap 引入
问题：建立学生学号和学生姓名间的键值映射，并通过 Key 对 Value 进行操作，应该如何实现数据的存储和操作呢？
Map 接口专门处理键值映射数据的存储，可以根据键实现对值的操作。 最常用的实现类是 HashMap。
public static void main(String[] args) {
Map<String,String> map = new HashMap<String,String>();
map.put("004","李清照");
map.put("001","李白");
map.put("003","王羲之");
map.put("002","杜甫");
System.out.println(map.get("003"));
//获取所有key 值
Set<String> keySet = map.keySet();
for (String s : keySet){
String s1 = map.get(s);
System.out.println(s+" "+s1);
}
//获取所有值
Collection<String> values = map.values();
for (String s : values){
System.out.println(s);
}
//entrySet() 获取值
Set<Map.Entry<String, String>> entrySet = map.entrySet();
for (Map.Entry<String, String> m : entrySet){
String key = m.getKey();
String value = m.getValue();
System.out.println(key+","+value);
}
}
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
# HashMa数据结构
HashMap 是基于哈希表的 Map 接口实现的，它存储的是内容是键值对映射。此类不保证映射的顺序，假定哈希函数将元素适当的分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。
在 API 中给出了相应的定义：
又到了最激动人心的源码分析环节**😄**
第一段
哈希表基于 Map 接口的实现，这个实现提供了 Map 所有的操作，并且提供了 Key 和 Value，可以为 null，(HashMap 和 HashTable 大致上是一样的，除了 HashMap 是异步的，和允许 Key 和 Value 为 null，而 HashTable 不允许 Value 为 null)
这个类不确定 Map 中元素的位置，特别要提的是，这个类也不确定元素的位置随着时间会不会保持不变。
第二段
假设哈希函数将元素合适的分到了每个桶（其实就是指的数组中位置上的链表）中，则这个实现为基本的操作（get、put）提供了稳定的性能，迭代这个集合视图需要的时间跟 HashMap 实例（Key-Value 映射的数量）的容量（在桶中）成正比，因此，如果迭代的性能很重要的话，就不要将初始容量设置的太高或者 loadfactor 设置的太低，（这里的桶，相当于在数组中每个位置上放一个桶装元素）
第三段
HashMap 的实例有两个参数影响性能，初始化容量（initialCapacity）和 loadFactor 加载因子，在哈希表中这个容量是桶的数量（也就是数组的长度），一个初始化容量仅仅是在哈希表被创建时容量，在容量自动增长之前加载因子是衡量哈希表被允许达到的多少的。当 Entry 的数量在哈希表中超过了加载因子乘以当前的容量，那么哈希表被修改（内部的数据结构会被重新建立）所以哈希表有大约两倍的桶的数量。
第四段
通常来讲，默认的加载因子（0.75）能够在时间和空间上提供一个好的平衡，更高的值会减少空间上的开支但是会增加查询花费的时间（体现在 HashMap 类中 get、put 方法上），当设置初始化容量时，应该考虑到 Map 中会存放 Entry 的数量和加载因子，以便最少次数的进行 rehash 操作，如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
第五段
如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。
# HashMap在JDK1.8以前数据结构和存储原理
链表散列
首先我们要知道什么是链表散列？通过数组和链表结合在一起使用，就叫做链表散列。这其实就是 HashMap 存储的原理图。
HashMap 的数据结构和存储原理
HashMap 的数据结构就是用的链表散列。那 HashMap 底层是怎么样使用这个数据结构进行数据存取的呢？分成两个部分：
第一步：HashMap 内部有一个 Entry 的内部类，其中有四个属性，我们要存储一个值，则需要一个 key 和一个 value 存到 Map 中，就会先将 key 和 value 保存在这个 Entry 类创建的对象中，Entry 本质是一个 KV 映射。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 就是我们说的 Map 的 key
V value; // value 值，这两个都不陌生
Entry<K,V> next;// 指向下一个 Entry 对象
int hash;// 通过 key 算过来的 hashcode 值。
}
2
3
4
5
6
Entry 的物理模型图：
第二步：构造好了 Entry 对象，然后将该对象放入数组中，如何存放就是这 HashMap 的精华所在了。
大概的一个存放过程是：通过 Entry 对象中的 hash 值来确定将该对象存放在数组中的哪个位置上，如果在这个位置上还有其他元素，则通过链表来存储这个元素。
Hash 存放元素的过程
通过 key、value 封装成一个 Entry 对象，然后通过 key 的值来计算该 Entry 的 hash 值，通过 Entry 的 hash 值和数组的长度 length 来计算出 Entry 放在数组中的哪个位置上面。
每次存放都是将 Entry 放在第一个位置。在这个过程中，就是通过 hash 值来确定将该对象存放在数组中的哪个位置上。
# JDK1.8后HashMap的数据结构
JDK1.8 版本后把 Entry 类改 为Node 类，重要属性依然是 Key、Value、哈希值、指向下一个元素地址，而 Entry 类则存的是红黑树的信息。
上图很形象的展示了 HashMap 的数据结构（数组 + 链表 + 红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。
# 简单模拟
- 当 HashMap 为
[{12,"aa"},{7,"bb"},{19,"cc"},{12,"dd"},{14,"ee"},{20,"ff"}]，内部调用了hasCode方法计算数组元素的哈希值 - 假设数组元素的哈希值就是 HashMap 的 key，接下来通过一个算法计算在数组元素存放的位置，假设位置为
[1,6,2,1,3,1] - 接下来把 Key、Value、哈希值封装为
Entry类，并且拥有一个指向下一个元素的地址空间 - 根据位置把封装的
Entry类存入底层数组（数组的一个个元素就是 Entry 类） - 存放过程，使用
equals进行判断，发现后面的{12,"dd"}的位置和{12,"aa"}的位置重复，且 key 相同，则把新的 value（aa）替换旧的 value（bb） - 最后发现
{20,"ff"}的位置和{12,"dd"}重复，但是 key 不同，则进行处理- JDK1.7 版本前：头插法，即把新数据
{20,"ff"}的地址先放入底层数组，然后该数据的指向下一个元素地址的「指针」指向旧数据{12,"dd"}的地址（旧数据会先取出来备份） - JDK1.8 版本后：尾插法，即直接在旧数据
{12,"dd"}后追加新数据{20,"ff"}，就是把旧数据的指向下一个元素地址的「指针」指向新数据的地址
- JDK1.7 版本前：头插法，即把新数据
# HashMap的属性
HashMap 的实例有两个参数影响其性能。
初始容量：哈希表中桶的数量
加载因子：哈希表在其容量自动增加之前可以达到多满的一种尺度
当哈希表中条目数超出了 当前容量 * 加载因子（其实就是 HashMap 的实际容量）时，则对该哈希表进行 rehash 操作，将哈希表扩充至两倍的桶数。
Java 中默认初始容量为 16，加载因子为 0.75。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
2
loadFactor 加载因子
定义：loadFactor 译为加载因子、装载因子。装载因子用来衡量 HashMap 满的程度。loadFactor 的默认值为 0.75f。计算 HashMap 的实时装载因子的方法为：size / capacity，而不是占用桶的数量去除以 capacity。
loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么数组中存放的数据（Entry）也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，那么数组中存放的数据也就越稀，也就是可能数组中每个位置上就放一个元素。
那有人说，就把 loadFactor 变为 1 最好吗，存的数据很多，但是这样会有一个问题，就是我们在通过 key 拿到我们的 value 时，是先通过 key 的 hashcode 值，找到对应数组中的位置，如果该位置中有很多元素，则需要通过 equals 来依次比较链表中的元素，拿到我们的 value 值，这样花费的性能就很高，如果能让数组上的每个位置尽量只有一个元素最好，我们就能直接得到 value 值了，所以有人又会说，那把 loadFactor 变得很小不就好了，但是如果变得太小，在数组中的位置就会太稀，也就是分散的太开，浪费很多空间，这样也不好，所以在 HashMap 中 loadFactor 的初始值就是 0.75，一般情况下不需要更改它。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
桶
根据前面画的 HashMap 存储的数据结构图，你这样想，数组中每一个位置上都放有一个桶，每个桶里就是装一个链表，链表中可以有很多个元素（Entry），这就是桶的意思。也就相当于把元素都放在桶中，所以一个桶等于数组某个下标 + 衍生的链表。
capacity
capacity 译为容量代表的数组的容量，也就是数组的长度，同时也是 HashMap 中桶的个数。默认值是 16。
一般第一次扩容时会扩容到 64，之后是 2 的倍数。总之，容量都是 2 的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
size 的含义
size 就是在该 HashMap 的实例中实际存储的元素的个数，而不是数组的整个长度。
threshold 的作用
int threshold;
threshold = capacity * loadFactor，当 size >= threshold 的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准。
注意这里说的是考虑，因为实际上要扩增数组，除了这个 size >= threshold 条件外，还需要另外一个条件。
什么时候会扩增数组的大小？在 put 一个元素时先 size >= threshold 并且还要在对应数组位置上有元素，这才能扩增数组。
我们通过一张 HashMap 的数据结构图来分析：
# HashMap的源码分析
# HashMap的层次关系与继承结构
HashMap 继承结构
上面就继承了一个 AbstractMap，也就是用来减轻实现 Map 接口的编写负担。
实现接口
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
}
2
3
4
- Map<K,V>：在 AbstractMap 抽象类中已经实现过的接口，这里又实现，实际上是多余的。但每个集合都有这样的错误，也没过大影响
- Cloneable：能够使用
Clone()方法，在 HashMap 中，实现的是浅层次拷贝，即对拷贝对象的改变会影响 被拷贝的对象 - Serializable：能够使之序列化，即可以将 HashMap 对象保存至本地，之后可以恢复状态
# JDK7的HashMap源码
public class HashMap<K,V>{
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 定义了常量16，赋值给底层数组的长度
static final int MAXIMUM_CAPACITY = 1 << 30;// 定义了一个很大的数
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 定义了一个值：0.75，负载因子，加载因子，装填因子
static final int TREEIFY_THRESHOLD = 8; // 树形阈值：当链表长度达到8时，将链表转化为红黑树
transient Node<K,V>[] table; // 底层主数组
transient int size; // 添加元素的数量
int threshold; // 没赋值默认为0，用来表示数组扩容的边界值，门槛值
final float loadFactor; // 用来接收 负载因子，加载因子，装填因子
// 无参构造器，把装填因子给loadFactor
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR);
}
// 有参构造器，把capacity初始为16，数组长度为16
public HashMap(int initialCapacity,float loadFactory) {
int capacity = 1;
// 当前capacity小于16，则乘以2，流程1<<1=2，2<<1=4，4<<1=8，8<<1=16，这也是为什么日后数组扩容都是2的整数倍(2^n)
while(capacity < initialCapacity)
capacity << 1;
//确定了装载因子：0.75
this.loadFactory = loadFactory;
// threshold最后等于16*0.75 = 12，为扩容的边界值，当数组长度超过12，则进行扩容
threshold = (int) Math.min(capacity * loadFactory,MAXIMUM_CAPACITY + 1);
//创建主数组，长度为16
table = new Entry[capacity];
}
// 添加元素方法
public V put(K key,V value){
// 允许key为null
if(key == null){
return putForNullKey(value);
}
// 获取哈希值
int hash = hash(key);
// 得到元素在数组中的位置
int i = indexFor(hash,table.length);
// 该for循环解决哈希冲突问题，即位置重复问题，第一个放入元素不会走这个循环
for(Entry<K,V> e = table[i];e != null;e = e.next){
Object K;
// 如果哈希值一样，并且key也一样，则执行判断，总体是同一个key的情况下，旧value会被新的替换，但是key还是旧value的key
if(e.hash == hash && ((k = e.key) == key || key.equals(k))){
// 把旧值拿出
V oldValue = e.value;
// 把新值覆盖旧值
e.value = value;
e.recordAccess(this);
// 返回旧值
return oldValue;
}
}
modCount++;
addEntry(hash,key,value,i);
return null;
}
// 获取哈希值方法
final int hash(Object k){
int h = 0;
if(useAltHashing){
if(k instanceof String){
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
// 二次散列，没有直接使用HashCode的值，解决哈希冲突
h ^= k.hashCode();
// 再一次增加哈希值的不确定性
h ^= (h >>> 20) ^ (h >> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 根据哈希获取位置方法
static int indexFor(int h,int length){
// 高位运算和取模运算
return h & (length - 1); // 实际就是取余操作：h % (length - 1)，直接用取余运算，效率低
}
// 封装数据，并且插入数组方法
void addEntry(int hash,K key,V value,int bucketIndex){
// 如果数组长度大于边界值，执行判断
if((size >= threshold) && (null != table[bucketIndex])){
//需要调用resize进行扩容，获得新的数组，为原来长度的2倍数，最终table是新的大数组，并且拥有原来数组的内容
resize(2 * table.length);
// 重新计算哈希值
hash = (null != key) ? hash(key) : 0;
// 重新获取位置
bucketIndex = indexFor(hash,table.length);
}
// 创建Entry对象，插入数组
createEntry(hash,key,value,bucketIndex);
}
//创建Entry对象，插入数组
void createEntry(int hash,K key,V value,int bucketIndex){
// 使用头插法，先获取旧的数据，然后把新数据封装为Entry对象，插入数组，在把旧数据放入新数据的后面
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash,key,value,bucketIndex);
size++;
}
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# JDK8的HashMap源码
# HashMap类的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶（bucket）上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶（bucket）上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的 table 的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是 2 的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小（容量*填充因子）超过临界值时，会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
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
# HashMap的构造方法
有四个构造方法，构造方法的作用就是记录一下 16 这个数给 threshold（这个数值最终会当作第一次组的长度）和初始化加载因子。注意，HashMap 中 table 数组一开始就已经是个没有长度的数组了。
构造方法中，并没有初始化数组的大小，数组在一开始就已经被创建了，构造方法只做两件事情，一个是初始化加载因子，另一个是用 threshold 记录下数组初始化的大小。注意是记录。
HashMap()
// 看上面的注释就已经知道，DEFAULT_INITIAL_CAPACITY=16，DEFAULT_LOAD_FACTOR=0.75
// 初始化容量：也就是初始化数组的大小
// 加载因子：数组上的存放数据疏密程度。
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
2
3
4
5
6
7
HashMap(int)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
2
3
HashMap(int,float)
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于 0，否则报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量不能大于最大值，否则为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 填充因子不能小于或等于 0，不能为非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 初始化填充因子
this.loadFactor = loadFactor;
// 初始化 threshold 大小
this.threshold = tableSizeFor(initialCapacity);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
// 初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将 m 中的所有元素添加至 HashMap 中
putMapEntries(m, false);
}
2
3
4
5
6
putMapEntries(Map<? extends K, ? extends V> m, boolean evict) 函数将 m 的所有元素存入本 HashMap 实例中
/**
* Implements Map.putAll and Map constructor.
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 判断 table 是否已经初始化
if (table == null) { // pre-size
// 未初始化，s 为 m 的实际元素个数
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 计算得到的 t 大于阈值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 已初始化，并且 m 元素个数大于阈值，进行扩容处理
else if (s > threshold)
resize();
// 将 m 中的所有元素添加至 HashMap 中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
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
# HashMap常用方法
put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
2
3
putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table 未初始化或者长度为 0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中（此时，这个结点是放在数组中）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 桶中已经存在元素
else {
Node<K,V> e; K k;
// 比较桶中第一个元素(数组中的结点)的 hash 值相等，key 相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给 e，用 e 来记录
e = p;
// hash 值不相等，即 key 不相等；为红黑树结点
else if (p instanceof TreeNode)
// 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 为链表结点
else {
// 在链表最末插入结点
for (int binCount = 0; ; ++binCount) {
// 到达链表的尾部
if ((e = p.next) == null) {
// 在尾部插入新结点
p.next = newNode(hash, key, value, null);
// 结点数量达到阈值，转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断链表中结点的 key 值与插入的元素的 key 值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的 e = p.next 组合，可以遍历链表
p = e;
}
}
// 表示在桶中找到 key 值、hash 值与插入元素相等的结点
if (e != null) { // existing mapping for key
// 记录 e 的 value
V oldValue = e.value;
// onlyIfAbsent 为 false 或者旧值为 null
if (!onlyIfAbsent || oldValue == null)
// 用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
HashMap 并没有直接提供 putVal 接口给用户调用，而是提供的 put 函数，而 put 函数就是通过 putVal 来插入元素的。
get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
2
3
4
getNode(int hash,Pbject key)
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table 已经初始化，长度大于 0，根据 hash 寻找 table 中的项也不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 桶中第一项（数组元素）相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中不止一个结点
if ((e = first.next) != null) {
// 为红黑树结点
if (first instanceof TreeNode)
// 在红黑树中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 否则，在链表中查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
HashMap 并没有直接提供 getNode 接口给用户调用，而是提供的 get 函数，而 get 函数就是通过 getNode 来取得元素的。
resize 方法
final Node<K,V>[] resize() {
// 当前 table 保存
Node<K,V>[] oldTab = table;
// 保存 table 大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 保存当前阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 之前 table 大小大于 0
if (oldCap > 0) {
// 之前 table 大于最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值为最大整形
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍，使用左移，效率更高
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值翻倍
newThr = oldThr << 1; // double threshold
}
// 之前阈值大于 0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap = 0 并且 oldThr = 0，使用缺省值（如使用 HashMap() 构造函数，之后再插入一个元素会调用 resize 函数，会进入这一步）
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新阈值为0
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 初始化table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 之前的 table 已经初始化过
if (oldTab != null) {
// 复制元素，重新进行 hash
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 将同一桶中的元素根据（e.hash & oldCap）是否为 0 进行分割，分成两个不同的链表，完成 rehash
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。
在 resize 前和 resize 后的元素布局如下:
上图只是针对了数组下标为2的桶中的各个元素在扩容后的分配布局，其他各个桶中的元素布局可以以此类推。
# 重要源码
这里截取重要的源码展示。
public class HashMap<K,V>{
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 定义了常量 16，赋值给底层数组的长度
static final int MAXIMUM_CAPACITY = 1 << 30;// 定义了一个很大的数
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 定义了一个值：0.75，负载因子，加载因子，装填因子
static final int TREEIFY_THRESHOLD = 8; // 树形阈值：当链表长度达到8时，将链表转化为红黑树
transient Node<K,V>[] table; // 底层主数组
transient int size; // 添加元素的数量
int threshold; // 没赋值默认为 0，用来表示数组扩容的边界值，门槛值
final float loadFactor; // 用来接收 负载因子，加载因子，装填因子
// 无参构造器,并没有进行数组的初始化
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 添加元素方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 添加元素的具体操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab：哈希数组，p：该哈希桶的首节点（数组的某个位置存放的值），n：hashMap的长度，i：计算出的数组下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 获取长度并进行扩容，使用的是懒加载（JDK1.8 的普遍操作模式），table 一开始是没有创建，等 put 后才开始创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // resize 进行扩容，开始数组为空，初始为 16 长度
// 如果计算出的该哈希桶的位置没有值，则把新插入的 key-value 放到此处，此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予 p
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 发生哈希冲突的几种情况
else {
// e：临时节点的作用（标识是否需要覆盖旧值），k：存放该当前节点的 key
Node<K,V> e; K k;
// 第一种，表示如果插入的 hash 值与首节点的 hash 值相等，且 key 值也相同就直接覆盖（说明 HashMap 不允许 key 相同）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 第二种，hash 值不等于首节点，判断该 p 是否属于红黑树的节点
else if (p instanceof TreeNode)
// 为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点，否则返回 null,后面会判断，如果 e 不为空则把值覆盖
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 第三种，hash 值不等于首节点，不为红黑树的节点，则为链表的节点
else {
// 遍历该链表
for (int binCount = 0; ; ++binCount) {
// 如果找到尾部，则表明添加的 key-value 没有重复，在尾部进行添加
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断是否要转换为红黑树结构
// 因为 binCount 从 0 开始循环，当大于等于 7 的时候，也就是循环到第 8 次的时候才转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
// 重要
// 由于最开始 p 已经存在 1 个 Node 节点了，而到这里之前又新增了 8 个节点，也就是说转红黑树的时候，链表中有 9 个节点，所以链表长度大于 8，就转红黑树
treeifyBin(tab, hash);
break;
}
// 如果在 p.next == null 之前（也就是链表循环结束之前）这个判断成立，则表示链表中有重复的 key，e 则为当前重复的节点，结束循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 有重复的 key，则用待插入值进行覆盖，返回旧值。（说明 HashMap 不允许 key 相同）
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 到了此步骤，则表明待插入的 key-value 是没有 key 的重复，因为插入成功 e 节点的值为 null
// 修改次数 + 1
++modCount;
// 实际长度 + 1，判断是否大于阈值（临界值），大于则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// 添加成功
return null;
}
// 初始化或扩容方法
final Node<K,V>[] resize() {
// 创建一个 Node 数组用于存放 table 中的元素
Node<K,V>[] oldTab = table;
// 获取旧 table 的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取旧的扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果旧的 table 中有元素
if (oldCap > 0) {
//如果旧 table 长度 >= 最大容量限制时不进行扩容，并将扩容阈值赋值为 Integer.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将新 table 长度赋值为旧 table 的 2 倍，
// 判断旧 table 长度的二倍是否小于最大容量，且旧容量大于等于初始容量 16
// 以上判断成立则将新的扩容阀值赋值为旧的扩容阈值的二倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 双倍阈值
}
// 否则如果旧的扩容阈值却大于 0（HashMap 初始化指定容量的时候，会把容量赋值 threshold（扩容阈值）-> oldThr，后面会设置新的扩容阈值）
else if (oldThr > 0)
newCap = oldThr; // 设置初始容量
// 初始阈值表示使用默认值
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阈值等于 0 则根据新的 容量 * 负载因子 获得新的阈值赋值给 threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 设置阈值
// 将旧 table 中的元素放到扩容后的 newTable 中 因为扩容后，可能有的位置需要发生改变
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果数组对应下标位置只有一个元素，对 hashCade 取余并根据结果直接放到 newTable 相应的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果数组对应下标位置的元素是一个红黑树，则拆分红黑树放到 newTable 中
// 如果拆分后的红黑树元素小于 6，则转化为链表
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 数组对应下标位置的元素是一个链表的情况
// 根据（e.hash & oldCap）条件对链表进行拆分并放到 newTable
Node<K,V> loHead = null, loTail = null; // 不需要改变位置的 头链表和尾链表
Node<K,V> hiHead = null, hiTail = null; // 需要改变位置的 头链表和尾链表
Node<K,V> next;
do {
next = e.next;
// 根据某种规律得知，当等于 0 的时候，哪怕扩容到新的长度后，也不需要改变位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 否则扩容到新的长度后，需要改变位置
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; // 位置不需要改变的链表则直接赋值
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; // 位置需要发生变化的链表则加上旧的容量长度 为扩容后数组的位置，同理规律
}
}
}
}
}
return newTab;
}
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
get 和 push 原理类似，push 的时候经过 hash 值与数组长度的位运算确定数组下标，（h & (length - 1)），那么 get 的时候也是通过这个算法获取下标，然后就能获取该位置的数据（只有一个）或者链表（有多个数据形成链表），如果是前者，直接返回需要的 value，如果是后者，首先需要进行 hash 值的比较，相等则再比较 Key，还相等则返回 Value。不相等则继续遍历下去直到找到 hash 值和 Key 值相等的 Value。
# 版本区别
JDK1.8 版本后创建 HashMap 并不会初始化数组，而是在 put 的时候，进行判断，从而初始化数组长度为 16。减少内存
JDK1.8 版本把 Entry 类改为 Node 类，重要属性依然是 key、value、哈希值、指向下一个元素地址
JDK1.8 版本把头插法改为尾插法，因为尾插法在多线程产生环链问题
JDK1.8 版本把由数组 + 链表结构变为数组 + 链表 + 红黑树，当链表长度大于 8 时，会将链表转换为红黑树，当链表长度小于 6 时，会将红黑树转换为链表
红黑树的类为
TreeNode，链表为Node类，后者是前者的父类，也就说 Node 可能是链表结构，也可能是红黑树结构static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {} // 红黑树 static class Entry<K,V> extends HashMap.Node<K,V> {} // LinkedHashMap 的 Entry，红黑树的父类 static class Node<K,V> implements Map.Entry<K,V> {} // LinkedHashMap 的 Entry 的父类，链表，所以也是红黑树的父类1
2
3
# 源码总结
- HashMap 刚创建时，table 是 null，节省空间，当添加第一个元素时，table 容量调整为 16
- 当元素个数大于阈值（16 * 0.75 = 12）时，会进行扩容，扩容后的大小为原来的两倍，目的是减少调整元素的个数
- JDK1.8 当每个链表长度 > 8 ，并且数组元素个数 ≥ 64 时，会调整成红黑树，目的是提高效率
- JDK1.8 当链表长度 < 6 时 调整成链表
- JDK1.8 以前，链表时头插入，之后为尾插入
# JDK7头插法产生环链问题
多线程操作，同时去扩容，当一个线程已经操作完毕了，将原来的顺序反过来了；另一个线程再开始执行扩容代码，此时就会出现环链。
如原来内容是 3 -> 2 -> 1，线程一扩容先把 3 拿出，再把 2 拿出放到 3 的前面，形成 2 -> 3，此时线程 2 执行 put 操作开启扩容，将 3 拿出来，形成了 3 -> 2 -> 3，这就是环链，卡住了，可能导致 IDEA 等工具都无法运行（无响应）。
因为环链问题，JDK 8 就优化成了 尾插法，修复了环链这个问题。但在并发环境中仍是不安全的。
# 经典面试题
装填因子，负载因子，加载因子为什么 0.75，而不是 1（装填因子类似于折扣，初始数组长度为 16，但是不是长度满了才扩容，而是到了
16 * 0.75 = 12时，进行扩容）装填因子设置为 1：空间利用率得到了满足，但是容易发生碰撞，产生链表，查询效率低
装填因子设置为 0.75：碰撞的概率低，扩容，产生链表的几率低，查询效率高，空间利用率低
主数组的长度为什么是 2^n
- 计算哈希值，代码为
h & (length - 1)，等效h % (length - 1)操作，但是 & 等效求余的前提是 length 必须是 2 的整数倍，因为 2 的整数幂 - 1 的二进制比较特殊，就是一串 11111，可以等价于求余 - 防止哈希冲突，位置冲突，因为通过哈希值计算位置的时候，不是 2 的整数倍容易位置一样
- 计算哈希值，代码为
# 总结
关于数组扩容
从 putVal 源代码中我们可以知道，当插入一个元素的时候 size 就加 1，若 size 大于 threshold 的时候，就会进行扩容。假设我们的 capacity 大小为 32，loadFator 为 0.75，则 threshold 为 24 = 32 * 0.75。
此时，插入了 25 个元素，并且插入的这 25 个元素都在同一个桶中，桶中的数据结构为红黑树，则还 有 31 个桶是空的，也会进行扩容处理，其实，此时，还有 31 个桶是空的，好像似乎不需要进行扩容处理，但是是需要扩容处理的，因为此时我们的 capacity 大小可能不适当。我们前面知道，扩容处理会遍历所有的元素，时间复杂度很高；前面我们还知道，经过一次扩容处理后，元素会更加均匀的分布在各个桶中，会提升访问效率。所以，说尽量避免进行扩容处理，也就意味着，遍历元素所带来的坏处大于元素在桶中均匀分布所带来的好处。
总结
- 要知道 HashMap 在 JDK1.8 以前是一个链表散列这样一个数据结构，而在 JDK1.8 以后是一个数组加链表加红黑树的数据结构
- 通过源码的学习，HashMap 是一个能快速通过 key 获取到 value 值得一个集合，原因是内部使用的是 hash 查找值得方法