HashMap原理详解，包括底层原理

HashMap

是什么

HashMap是一个用于存储Key-Value键值对的聚集，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。
HashMap可以以平均O(1)的时间复杂度去获取聚集中某个元素是否存在。
1.7

数组 + 链表 实现的  每个数据单位是一个Entry
初始化
new 的时候默认创建一个长度为默认值16的Entry[]数组，假如事先知道大概的数据量大小，可以通过构造函数传入，以减少动态扩容的次数，这样可以大大进步性能
插入元素 计算位置
为了进步性能，HashMap在根据对象计算hashcode()后，还举行了扰动计算来减少哈希冲突
哈希函数一共有九次扰动计算   四次位运算  五次异或运算   只管做到任何一位的厘革都能对最终得到的结果产生影响  降低哈希冲突概率

1. // 获取对象的 hashCode 值
2. h = k.hashCode();
4. // 扰动运算
5. h ^= (h >>> 20) ^ (h >>> 12);
6. return h ^ (h >>> 7) ^ (h >>> 4);

复制代码

得到扰动函数的返回值后 再计算索引

1. int index = hash & (capacity - 1);// hash是扰动函数的结果 capacity 是哈希表的容量  

复制代码

发生冲突
当不同的key计算出的hash值相同时（发生冲突），就用链表的情势将Node结点（冲突的key及key对应的value）插在链表的头部（头插法）
扩容机制
默认负载因子是0.75。当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
扩容后  HashMap会将旧数组中的数据重新分配到新数组中，不需要重新计算哈希值，但是需要根据新的容量重新计算索引位置。
计算完毕索引位置后，会举行数据转移，从原链表尾部开始转移，转移到新链表的对应位置的时候采用头插法，正因为这样，元素的序次会被颠倒
转移数据完毕后，插入刚才要插入的新元素。
1.8

JDK1.8的底层由  数组+链表+红黑树  组成。每个数据单位都是一个Node布局，里面有四个字段分别是  key，value，hash和next 。其中hash就是将key的hashCode()的高16位异或低16位的值，next字段就是发生hash冲突后，当前桶位中的Node与冲突Node连成一个链表用的字段。
初始化
在初次调用put()方法的时候，底层创建长为16的数组
插入
计算哈希值
key不为空的话，就调用hashcode()方法计算，得到的值，再举行高16位和低16位的异或运算

1. static final int hash(Object key) {
2.     int h;
3.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 两次扰动  一次位运算 一次异或
4. }

复制代码

接着计算索引

1. index = (hash & (capacity - 1));

复制代码

发生冲突时的办理方案
当发生冲突时，新节点会挂在链表的尾部，这样就不会向头插法一样可能出现死循环问题。
ps: 死循环问题
在jdk1.7的扩容过程中，利用头插法举行重建，假如某些情况下，出现多个线程同时对链表举行操作，可能会导致链表断裂并出现环形布局
当链表长度过长的时候，遍历的服从就会下降到O(n),为了办理这个问题， 当链表的长度超过8，并且数组的容量大于64的时候，HashMap会将链表转化为红黑树(红黑树是一种自平衡的二叉搜索树，增删改查服从是O(logn)).
扩容机制
当容量超过0.75的时候，触发扩容机制。 扩容为原来的两倍。数据迁移相对于1.7有了优化。
新位置计算
无需重新计算哈希值，只需要颠末简单的位运算就可以确定新的位置。  对于每个元素，将他的哈希值和旧容量举行与运算，假如结果为0，保持旧索引不变，新索引就是旧索引，结果为1，新索引为旧索引加上旧容量值。
数据迁移 利用的是尾插法
①   假如旧数组的这个位置是null , 就直接给新数组中他要放到的位置也赋值为null，当然默认值也是null
②   假如旧数组的这个位置只有一个Node,就直接放到新数组他要放到的位置就行了
③   假如旧数组的这个位置是一个链表  ，就初始化一个低位链表头尾指针，一个高位链表的头尾指针，遍历旧链表，哈希值和旧容量举行与运算即是0的节点，放到低位链表中，不为0的放到高位链表中。低位链表直接放到新索引=旧索引的地方  高位链表放到新索引=旧索引+旧容量的位置
④   假如旧数组的这个位置是一个树，就调用TreeNode.split() 方法，将红黑树拆成两个树或者两个链表。分别对应低位和高位。低位的放到新索引=旧索引的地方  高位放到新索引=旧索引+旧容量的位置。假如拆分后树节点的数目小于即是6，就把红黑树退化为链表
get(key)操作
根据传入的key，计算哈希值 计算索引位置。

1. static final int hash(Object key) {
2.     int h;
3.     // key.hashCode() 计算原始哈希值
4.     // 与自身右移16位的值进行异或，混合高低位哈希码，减少冲突
5.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
6. }
7. int index = (n - 1) & hash;

复制代码

对应位置为空  返回null
对应位置不为空
只有头结点 用equals()比较头结点的键和目标键  一样则返回头结点的值  不一样返回null
头结点有next   判断是不是树形布局 e instanceof TreeNode       
是树 进入红黑树的查找流程 找到返回值 找不到null
是链表  遍历链表  逐个节点举行比较  找到返回值  找不到返回null

1. public V get(Object key) {
2.     Node<K,V> e;
3.     return (e = getNode(hash(key), key)) == null ? null : e.value;
4. }
6. final Node<K,V> getNode(int hash, Object key) {
7.     Node<K,V>[] tab;
8.     Node<K,V> first, e;
9.     int n;
10.     K k;
11.     if ((tab = table) != null && (n = tab.length) > 0 &&
12.         (first = tab[(n - 1) & hash]) != null) {
13.         // 检查头节点
14.         if (first.hash == hash && // 检查哈希值是否相等
15.             ((k = first.key) == key || (key != null && key.equals(k))))
16.             return first;
17.         if ((e = first.next) != null) {
18.             if (first instanceof TreeNode)
19.                 // 红黑树查找
20.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
21.             do {
22.                 // 链表查找
23.                 if (e.hash == hash &&
24.                     ((k = e.key) == key || (key != null && key.equals(k))))
25.                     return e;
26.             } while ((e = e.next) != null);
27.         }
28.     }
29.     return null;
30. }

复制代码

put()操作
检查哈希表是不是为空
空的话调用resize方法，以默认的16为容量初始化   计算哈希值  计算索引  插入即可
不是空 计算出索引位置  获取索引位置上的头结点
头结点为空   直接插入即可
头结点不为空
是树 调用putTreeVal()方法在红黑树中举行操作
键存在  更新对应值并返回旧值
键不存在  插入新节点  维护红黑树平衡
是链表   遍历链表
键存在  更新对应值并返回旧值
键不存在 尾插法    记录链表长度  判断 是否需要树化 需要则举行树化
插入操作完成后  实行++size  更新元素数目  判断是否超过阈值  是否举行扩容

1. public V put(K key, V value) {
2.     return putVal(hash(key), key, value, false, true);
3. }
5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
6.     Node<K,V>[] tab;
7.     Node<K,V> e;
8.     int n, i;
9.     if ((tab = table) == null || (n = tab.length) == 0) {
10.         // 初始化 table
11.         n = (tab = resize()).length;
12.     }
13.     // 计算索引位置
14.     if ((e = tab[i = (n - 1) & hash]) == null) {
15.         // 插入新节点
16.         tab[i] = newNode(hash, key, value, null);
17.     } else {
18.         Node<K,V> existing;
19.         K k;
20.         if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
21.             // 头节点的键相同，覆盖值
22.             existing = e;
23.         } else if (e instanceof TreeNode) {
24.             // 红黑树节点，调用树的插入方法
25.             existing = ((TreeNode<K,V>)e).putTreeVal(this, tab, hash, key, value);
26.         } else {
27.             // 链表节点，遍历链表
28.             for (int binCount = 0; ; ++binCount) {
29.                 if ((existing = e.next) == null) {
30.                     // 插入到链表尾部
31.                     e.next = newNode(hash, key, value, null);
32.                     if (binCount >= TREEIFY_THRESHOLD - 1) {
33.                         // 链表长度超过阈值，树化
34.                         treeifyBin(tab, hash);
35.                     }
36.                     break;
37.                 }
38.                 if (existing.hash == hash && ((k = existing.key) == key || (key != null && key.equals(k)))) {
39.                     // 找到相同的键
40.                     break;
41.                 }
42.                 e = existing;
43.             }
44.         }
45.         if (existing != null) {
46.             // 覆盖值
47.             V oldValue = existing.value;
48.             if (!onlyIfAbsent || oldValue == null) {
49.                 existing.value = value;
50.             }
51.             afterNodeAccess(existing);
52.             return oldValue;
53.         }
54.     }
55.     ++modCount;
56.     if (++size > threshold) {
57.         resize();
58.     }
59.     afterNodeInsertion(evict);
60.     return null;
61. }

复制代码

线程安全问题

为什么线程不安全？

• 在多线程环境下，JDK1.7的HashMap举行扩容时容易发生死链现象，主要因为往链表里面新添加元素的时候利用头插法。
  
• 在多线程环境下，JDK1.8的HashMap扩容后举行数据迁移利用的时候尾插法，而且会将链表拆分成一个低位链表和一个高位链表，然后分别放在对应的位置上，这样就能防止死链的产生。但是举行扩容时可能发生丢失数据现象。（多线程下容易发生数据覆盖和size不正确）
  

线程不安全怎么办？

• 替换成Hashtable，Hashtable通过对整个表上锁实现线程安全，但是服从比较低。
  
• 利用Collections.synchronizedMap(new HashMap());底层其实利用装饰器模式将HashMap的全部方法重写，然后用synchronized()来修饰每个重写后的方法，从而保证线程安全。
  
• 利用JUC包下的ConcurrentHashMap，它利用分段锁来保证线程安全。
  

为什么HashMap的长度总是2的n次方？
当 length 为 2 的 n 次方时，h & (length-1) 就相称于对 length 取模，而且速度比直接取模快得多，这是 HashMap 在速度上的一个优化。而且每次扩容时都是翻倍。
扩容后数组的长度变成原来的2倍，还是2的幂次方。那么数据举行迁移时，要么在原来位置，要么在原来位置+扩容长度。不需要举行再次哈希计算，进步服从。
数据会更加匀称
为什么HashMap中String、Integer这样的包装类适合做为Key？

• 都是final范例，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况。
  
• 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范，不容易出现Hash值计算错误的情况。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。