HashMap底层实现和原理（源码解析）

不念不忘少年蓝@ 2022-12-17 10:57 159阅读 0赞

Note：文章的内容基于JDK1.7进行分析，1.8做的改动文章末尾进行讲解。

大家可以看一下:[https://www.imooc.com/article/267756][https_www.imooc.com_article_267756]

## 一、先来熟悉一下我们常用的HashMap ##

### 1、概述 ###

HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null 建和null　值，　因为key不允许重复，因此只能有一个键为null,另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。

### 2、继承关系 ###

1.  `public class HashMap<K,V>extends AbstractMap<K,V>`
2.  `implements Map<K,V>, Cloneable, Serializable`

3、基本属性

1.  `static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16`
2.  `static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子0.75`
3.  `static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默认数组`
4.  `transient int size; //HashMap中元素的数量`
5.  `int threshold; //判断是否需要调整HashMap的容量`

Note：HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。HashMap的线程是不安全的，多线程环境中推荐是ConcurrentHashMap。

## 二、常被问到的HashMap和Hashtable的区别 ##

### 1、线程安全 ###

两者最主要的区别在于Hashtable是线程安全，而HashMap则非线程安全。

Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。

Note：

Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类，这个类实现了Map接口，在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例，简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步，类似的其它Collections.synchronizedXX方法也是类似原理。

### 2、针对null的不同 ###

HashMap可以使用null作为key，而Hashtable则不允许null作为key  
虽说HashMap支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事。  
Note：HashMap以null作为key时，总是存储在table数组的第一个节点上。

### 3、继承结构 ###

HashMap是对Map接口的实现，HashTable实现了Map接口和Dictionary抽象类。

### 4、初始容量与扩容 ###

HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。

HashMap扩容时是当前容量翻倍即:capacity\*2，Hashtable扩容时是容量翻倍+1即:capacity\*2+1。

### 5、两者计算hash的方法不同 ###

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

1.  `int hash = key.hashCode();`
2.  `int index = (hash & 0x7FFFFFFF) % tab.length;`

HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸。

1.  `int hash = hash(key.hashCode());`
2.  `int i = indexFor(hash, table.length);`
3.   
4.  `static int hash(int h) {`
5.  `// This function ensures that hashCodes that differ only by`
6.  `// constant multiples at each bit position have a bounded`
7.  `// number of collisions (approximately 8 at default load factor).`
8.  `h ^= (h >>> 20) ^ (h >>> 12);`
9.  `return h ^ (h >>> 7) ^ (h >>> 4);`
10. `}`
11.  
12. `static int indexFor(int h, int length) {`
13. `return h & (length-1);`

## 三、HashMap的数据存储结构 ##

### 1、HashMap由数组和链表来实现对数据的存储 ###

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70 2][]

从上图我们可以发现数据结构由数组+链表组成，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key.hashCode())%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap里面实现一个静态内部类Entry，其重要的属性有 hash，key，value，next。

HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry\[0\] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:*B.next = A*,Entry\[0\] = B,如果又进来C,index也等于0,那么*C.next = B*,Entry\[0\] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

1.  `public V put(K key, V value) {`
2.  `if (key == null)`
3.  `return putForNullKey(value); //null总是放在数组的第一个链表中`
4.  `int hash = hash(key.hashCode());`
5.  `int i = indexFor(hash, table.length);`
6.  `//遍历链表`
7.  `for (Entry<K,V> e = table[i]; e != null; e = e.next) {`
8.  `Object k;`
9.  `//如果key在链表中已存在，则替换为新value`
10. `if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {`
11. `V oldValue = e.value;`
12. `e.value = value;`
13. `e.recordAccess(this);`
14. `return oldValue;`
15. `}`
16. `}`
17.  
18. `modCount++;`
19. `addEntry(hash, key, value, i);`
20. `return null;`
21. `}`
22.  
23.  
24.  
25. `void addEntry(int hash, K key, V value, int bucketIndex) {`
26. `Entry<K,V> e = table[bucketIndex];`
27. `table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next`
28. `//如果size超过threshold，则扩充table大小。再散列`
29. `if (size++ >= threshold)`
30. `resize(2 * table.length);`
31. `}`

## 四、重要方法深度解析 ##

### 1、构造方法 ###

1.  `HashMap() //无参构造方法`
2.  `HashMap(int initialCapacity) //指定初始容量的构造方法`
3.  `HashMap(int initialCapacity, float loadFactor) //指定初始容量和负载因子`
4.  `HashMap(Map<? extends K,? extends V> m) //指定集合，转化为HashMap`

HashMap提供了四个构造方法，构造方法中 ，依靠第三个方法来执行的，但是前三个方法都没有进行数组的初始化操作，即使调用了构造方法此时存放HaspMap中数组元素的table表长度依旧为0 。在第四个构造方法中调用了inflateTable()方法完成了table的初始化操作，并将m中的元素添加到HashMap中。

### 2、添加方法 ###

1.  `public V put(K key, V value) {`
2.  `if (table == EMPTY_TABLE) { //是否初始化`
3.  `inflateTable(threshold);`
4.  `}`
5.  `if (key == null) //放置在0号位置`
6.  `return putForNullKey(value);`
7.  `int hash = hash(key); //计算hash值`
8.  `int i = indexFor(hash, table.length); //计算在Entry[]中的存储位置`
9.  `for (Entry<K,V> e = table[i]; e != null; e = e.next) {`
10. `Object k;`
11. `if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {`
12. `V oldValue = e.value;`
13. `e.value = value;`
14. `e.recordAccess(this);`
15. `return oldValue;`
16. `}`
17. `}`
18.  
19. `modCount++;`
20. `addEntry(hash, key, value, i); //添加到Map中`
21. `return null;`
22. `}`

在该方法中，添加键值对时，首先进行table是否初始化的判断，如果没有进行初始化（分配空间，Entry\[\]数组的长度）。然后进行key是否为null的判断，如果key==null ,放置在Entry\[\]的0号位置。计算在Entry\[\]数组的存储位置，判断该位置上是否已有元素，如果已经有元素存在，则遍历该Entry\[\]数组位置上的单链表。判断key是否存在，如果key已经存在，则用新的value值，替换点旧的value值，并将旧的value值返回。如果key不存在于HashMap中，程序继续向下执行。将key-vlaue, 生成Entry实体，添加到HashMap中的Entry\[\]数组中。

### 3、addEntry() ###

1.  `/*`
2.  `* hash hash值`
3.  `* key 键值`
4.  `* value value值`
5.  `* bucketIndex Entry[]数组中的存储索引`
6.  `* /`
7.  `void addEntry(int hash, K key, V value, int bucketIndex) {`
8.  `if ((size >= threshold) && (null != table[bucketIndex])) {`
9.  `resize(2 * table.length); //扩容操作，将数据元素重新计算位置后放入newTable中，链表的顺序与之前的顺序相反`
10. `hash = (null != key) ? hash(key) : 0;`
11. `bucketIndex = indexFor(hash, table.length);`
12. `}`
13.  
14. `createEntry(hash, key, value, bucketIndex);`
15. `}`
16. `void createEntry(int hash, K key, V value, int bucketIndex) {`
17. `Entry<K,V> e = table[bucketIndex];`
18. `table[bucketIndex] = new Entry<>(hash, key, value, e);`
19. `size++;`
20. `}`

添加到方法的具体操作，在添加之前先进行容量的判断，如果当前容量达到了阈值，并且需要存储到Entry\[\]数组中，先进性扩容操作，空充的容量为table长度的2倍。重新计算hash值，和数组存储的位置，扩容后的链表顺序与扩容前的链表顺序相反。然后将新添加的Entry实体存放到当前Entry\[\]位置链表的头部。在1.8之前，新插入的元素都是放在了链表的头部位置，但是这种操作在高并发的环境下容易导致死锁，所以1.8之后，新插入的元素都放在了链表的尾部。

### 4、获取方法：get ###

1.  `public V get(Object key) {`
2.  `if (key == null)`
3.  `//返回table[0] 的value值`
4.  `return getForNullKey();`
5.  `Entry<K,V> entry = getEntry(key);`
6.   
7.  `return null == entry ? null : entry.getValue();`
8.  `}`
9.  `final Entry<K,V> getEntry(Object key) {`
10. `if (size == 0) {`
11. `return null;`
12. `}`
13.  
14. `int hash = (key == null) ? 0 : hash(key);`
15. `for (Entry<K,V> e = table[indexFor(hash, table.length)];`
16. `e != null;`
17. `e = e.next) {`
18. `Object k;`
19. `if (e.hash == hash &&`
20. `((k = e.key) == key || (key != null && key.equals(k))))`
21. `return e;`
22. `}`
23. `return null;`
24. `}`

在get方法中，首先计算hash值，然后调用indexFor()方法得到该key在table中的存储位置，得到该位置的单链表，遍历列表找到key和指定key内容相等的Entry，返回entry.value值。

### 5、删除方法 ###

1.  `public V remove(Object key) {`
2.  `Entry<K,V> e = removeEntryForKey(key);`
3.  `return (e == null ? null : e.value);`
4.  `}`
5.  `final Entry<K,V> removeEntryForKey(Object key) {`
6.  `if (size == 0) {`
7.  `return null;`
8.  `}`
9.  `int hash = (key == null) ? 0 : hash(key);`
10. `int i = indexFor(hash, table.length);`
11. `Entry<K,V> prev = table[i];`
12. `Entry<K,V> e = prev;`
13.  
14. `while (e != null) {`
15. `Entry<K,V> next = e.next;`
16. `Object k;`
17. `if (e.hash == hash &&`
18. `((k = e.key) == key || (key != null && key.equals(k)))) {`
19. `modCount++;`
20. `size--;`
21. `if (prev == e)`
22. `table[i] = next;`
23. `else`
24. `prev.next = next;`
25. `e.recordRemoval(this);`
26. `return e;`
27. `}`
28. `prev = e;`
29. `e = next;`
30. `}`
31.  
32. `return e;`
33. `}`

删除操作，先计算指定key的hash值，然后计算出table中的存储位置，判断当前位置是否Entry实体存在，如果没有直接返回，若当前位置有Entry实体存在，则开始遍历列表。定义了三个Entry引用，分别为pre, e ,next。 在循环遍历的过程中，首先判断pre 和 e 是否相等，若相等表明，table的当前位置只有一个元素，直接将table\[i\] = next = null 。若形成了pre -> e -> next 的连接关系，判断e的key是否和指定的key 相等，若相等则让pre -> next ,e 失去引用。

### 6、containsKey ###

1.  `public boolean containsKey(Object key) {`
2.  `return getEntry(key) != null;`
3.  `}`
4.  `final Entry<K,V> getEntry(Object key) {`
5.  `int hash = (key == null) ? 0 : hash(key.hashCode());`
6.  `for (Entry<K,V> e = table[indexFor(hash, table.length)];`
7.  `e != null;`
8.  `e = e.next) {`
9.  `Object k;`
10. `if (e.hash == hash &&`
11. `((k = e.key) == key || (key != null && key.equals(k))))`
12. `return e;`
13. `}`
14. `return null;`
15. `}`

containsKey方法是先计算hash然后使用hash和table.length取摸得到index值，遍历table\[index\]元素查找是否包含key相同的值。

### 7、containsValue ###

1.  `public boolean containsValue(Object value) {`
2.  `if (value == null)`
3.  `return containsNullValue();`
4.   
5.  `Entry[] tab = table;`
6.  `for (int i = 0; i < tab.length ; i++)`
7.  `for (Entry e = tab[i] ; e != null ; e = e.next)`
8.  `if (value.equals(e.value))`
9.  `return true;`
10. `return false;`
11. `}`

containsValue方法就比较粗暴了，就是直接遍历所有元素直到找到value，由此可见HashMap的containsValue方法本质上和普通数组和list的contains方法没什么区别，你别指望它会像containsKey那么高效。

## 五、JDK 1.8的 改变 ##

### 1、HashMap采用数组+链表+红黑树实现。 ###

在Jdk1.8中HashMap的实现方式做了一些改变，但是基本思想还是没有变得，只是在一些地方做了优化，下面来看一下这些改变的地方,数据结构的存储由数组+链表的方式，变化为数组+链表+红黑树的存储方式，当链表长度超过阈值（8）时，将链表转换为红黑树。在性能上进一步得到提升。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70 3][]

2、put方法简单解析：

1.  `public V put(K key, V value) {`
2.  `//调用putVal()方法完成`
3.  `return putVal(hash(key), key, value, false, true);`
4.  `}`
5.   
6.  `final V putVal(int hash, K key, V value, boolean onlyIfAbsent,`
7.  `boolean evict) {`
8.  `Node<K,V>[] tab; Node<K,V> p; int n, i;`
9.  `//判断table是否初始化，否则初始化操作`
10. `if ((tab = table) == null || (n = tab.length) == 0)`
11. `n = (tab = resize()).length;`
12. `//计算存储的索引位置，如果没有元素，直接赋值`
13. `if ((p = tab[i = (n - 1) & hash]) == null)`
14. `tab[i] = newNode(hash, key, value, null);`
15. `else {`
16. `Node<K,V> e; K k;`
17. `//节点若已经存在，执行赋值操作`
18. `if (p.hash == hash &&`
19. `((k = p.key) == key || (key != null && key.equals(k))))`
20. `e = p;`
21. `//判断链表是否是红黑树`
22. `else if (p instanceof TreeNode)`
23. `//红黑树对象操作`
24. `e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);`
25. `else {`
26. `//为链表，`
27. `for (int binCount = 0; ; ++binCount) {`
28. `if ((e = p.next) == null) {`
29. `p.next = newNode(hash, key, value, null);`
30. `//链表长度8，将链表转化为红黑树存储`
31. `if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st`
32. `treeifyBin(tab, hash);`
33. `break;`
34. `}`
35. `//key存在，直接覆盖`
36. `if (e.hash == hash &&`
37. `((k = e.key) == key || (key != null && key.equals(k))))`
38. `break;`
39. `p = e;`
40. `}`
41. `}`
42. `if (e != null) { // existing mapping for key`
43. `V oldValue = e.value;`
44. `if (!onlyIfAbsent || oldValue == null)`
45. `e.value = value;`
46. `afterNodeAccess(e);`
47. `return oldValue;`
48. `}`
49. `}`
50. `//记录修改次数`
51. `++modCount;`
52. `//判断是否需要扩容`
53. `if (++size > threshold)`
54. `resize();`
55. `//空操作`
56. `afterNodeInsertion(evict);`
57. `return null;`
58. `}`

如果存在key节点，返回旧值，如果不存在则返回Null。

[https_www.imooc.com_article_267756]: https://www.imooc.com/article/267756
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70]: /images/20221122/6789d4bf77044accae0d4a216dfa74ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70 1]: /images/20221122/5b6ae9525c8f43b38f0b1110e57caab0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70 2]: /images/20221122/5700e71086cd438c833cad5d1335274f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQ1Nzcz_size_16_color_FFFFFF_t_70 3]: /images/20221122/02dd2d0c84d64727bac2382b0d270d93.png