HashMap_详解
简述
- 实现了什么接口
- Map 和 抽象类AbstractMap
- Cloneable
- Serializable
- 核心内容
- 线程不同步。根据
key的hashcode进行存储，内部使用静态内部类Node的数组进行存储，默认初始大小为 16，默认负载因子 0.75，每次扩大一倍。 - 当发生 Hash 冲突时，采用拉链法（链表）。JDK 1.8优化：当单个桶中元素个数大于等于8时，链表实现改为红黑树实现；当元素个数小于6时，变回链表实现
- HashMap 是 Hashtable 的轻量级实现，可以接受为 null 的键值 (key) 和值 (value)，而 Hashtable 不允许
- 线程不同步。根据
- 优缺
- 扩容消耗大，建议自定义初始容量
- key为复杂类型时，的内存溢出问题
重要的属性
-
默认常量
1/** 2 * The default initial capacity - MUST be a power of two. 3 * 默认容量16 建议容量为2的n次幂 4 */ 5static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 6 7/** 8 * 默认负载因子 9 * The load factor used when none specified in constructor. 10 */ 11static final float DEFAULT_LOAD_FACTOR = 0.75f; 12 13// 所以默认可以容纳元素个数(阈值) 16 * 0.75 = 12 14 15/** 16 * 最大容量 17 * The maximum capacity, used if a higher value is implicitly specified 18 * by either of the constructors with arguments. 19 * MUST be a power of two <= 1<<30. 20 */ 21static final int MAXIMUM_CAPACITY = 1 << 30; -
hash桶数组中存储方式：链表、红黑树转换的阈值
1/** 2 * hash桶的存储方式由list转为tree的转换阈值(插入第9个元素时，list转为tree) 3 * 该阈值必须大于2，并且至少应为8才能与树删除中的假设（收缩时转换回普通箱）相啮合 4 */ 5static final int TREEIFY_THRESHOLD = 8; 6 7/** 8 * 在调整hash桶大小的操作中，取消hash桶的树化存储的计数阈值 9 * (当一个hash桶中的元素小于该值时，转换成链表存储) 10 * 应该小于TREEIFY_THRESHOLD，且最大为6，用于删除操作后的收缩检查 11 */ 12static final int UNTREEIFY_THRESHOLD = 6; 13 14/** 15 * hash桶树化存储的table的最小容量。（否则，如果hash桶中的节点过多，将调整table的大小。） 16 * 应至少为 4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。 17 * 因为一个比较小，比较满的散列表的性能不如一个比较大，比较空的散列表， 18 * 这种请款先考虑变大，而不是树化存储 19 */ 20static final int MIN_TREEIFY_CAPACITY = 64; -
几个核心属性
-
table：哈希桶，存储的entry的数组
-
capacity：table的最大容量
-
size：table中实际存储的了多少个元素
-
threshold：当size大于该阈值时table容量扩容1倍，threshold值刷新
/**
- hash桶数组
- 第一次使用时初始化，根据需要调整大小(始终为2的n次幂)
- 在某些操作中，我们还允许长度为零，以允许使用当前不需要的引导机制。 */ transient Node<K,V>[] table;
// 集合中键值对的数量 transient int size;
// 结构修改的次数 transient int modCount;
// 下一个要调整大小的大小值 （容量*负载系数）【相当于扩容的阈值】 // 如果hash桶数组没有初始化，则该字段持有出事容量，或者是0(表示使用 DEFAULT_INITIAL_CAPACITY) int threshold;
// 负载因子 final float loadFactor;
-
-
计算hash值得方法
1int hash = hash(key); 2// jdk7中确认entry存储在table[] 中的index 3int i = indexFor(hash, table.length); 4 5// 计算hash值 6final int hash(Object k) { 7 int h = hashSeed; 8 if (0 != h && k instanceof String) { 9 return sun.misc.Hashing.stringHash32((String) k); 10 } 11 12 h ^= k.hashCode(); 13 14 // This function ensures that hashCodes that differ only by 15 // constant multiples at each bit position have a bounded 16 // number of collisions (approximately 8 at default load factor). 17 h ^= (h >>> 20) ^ (h >>> 12); 18 return h ^ (h >>> 7) ^ (h >>> 4); 19} 20public final int hashCode() { 21 return Objects.hashCode(key) ^ Objects.hashCode(value); 22} -
哈希桶数组**table[]**中的Node数据类型：链表 or 红黑树
1// 链表 2static class Node<K,V> implements Map.Entry<K,V> { 3 final int hash; //用来定位数组索引位置 4 final K key; 5 V value; 6 Node<K,V> next; //链表的下一个node 7 8 Node(int hash, K key, V value, Node<K,V> next) { ... } 9 public final K getKey(){ ... } 10 public final V getValue() { ... } 11 public final String toString() { ... } 12 public final int hashCode() { ... } 13 public final V setValue(V newValue) { ... } 14 public final boolean equals(Object o) { ... } 15} 16 17// 红黑树node 18static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 19 TreeNode<K,V> parent; // 父 20 TreeNode<K,V> left; // 左 21 TreeNode<K,V> right; // 右 22 TreeNode<K,V> prev; // needed to unlink next upon deletion 23 boolean red; // 判断颜色 24 TreeNode(int hash, K key, V val, Node<K,V> next) { 25 super(hash, key, val, next); 26 } 27 // 返回根节点 28 final TreeNode<K,V> root() { 29 for (TreeNode<K,V> r = this, p;;) { 30 if ((p = r.parent) == null) 31 return r; 32 r = p; 33 }
从构造方法--核心put()方法--到扩容resize()方法
-
构造方法
-
只针对(loadFactor + threshold)两个字段初始化，没有初始化 哈希桶数组table[]
1public HashMap(int initialCapacity, float loadFactor) { 2 if (initialCapacity < 0) 3 throw new IllegalArgumentException("Illegal initial capacity: " + 4 initialCapacity); 5 if (initialCapacity > MAXIMUM_CAPACITY) 6 initialCapacity = MAXIMUM_CAPACITY; 7 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 8 throw new IllegalArgumentException("Illegal load factor: " + 9 loadFactor); 10 this.loadFactor = loadFactor; 11 // 获得对应容量的 2的n次幂 12 this.threshold = tableSizeFor(initialCapacity); 13} 14 15// 构造新的HashMap 使用Map接口的集合: 使用默认loadFactor(0.75) 足以(最小可用)将映射保存在指定Map中的初始容量 16public HashMap(Map<? extends K, ? extends V> m) { 17 // int threshold; 这个字段没有赋值，应为默认值 threshold = 0 18 this.loadFactor = DEFAULT_LOAD_FACTOR; 19 putMapEntries(m, false); 20} 21 22//特定容量 + 默认负载因子0.75 23public HashMap(int initialCapacity) { 24 this(initialCapacity, DEFAULT_LOAD_FACTOR); 25} 26 27//默认负载因子0.75 + threshold = 0 (数据类型默认值) 28public HashMap() { 29 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 30}
-
-
putAll()方法
1 // 实现 Map.putAll and Map constructor 这俩方法 2 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 3 int s = m.size(); 4 if (s > 0) { 5 // 判断table是否已经初始化 6 // 可能是在构造器中调用putMapEntries() 7 if (table == null) { // pre-size 8 //threshold = capacity * loadFactor（最小可用 入参map的size=threshold） 9 float ft = ((float)s / loadFactor) + 1.0F; 10 // 得到保存入参map(size)需要的最小 capacity 11 int t = ((ft < (float)MAXIMUM_CAPACITY) ? 12 (int)ft : MAXIMUM_CAPACITY); 13 //根据容量 刷新阈值 14 if (t > threshold) 15 // 调用构造器后，table == null， 继续调用putAll()，就可能threshold != 0 16 threshold = tableSizeFor(t); 17 } 18 // 已初始化，并且m元素个数大于阈值，进行扩容处理 19 else if (s > threshold) 20 resize(); 21 22 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 23 K key = e.getKey(); 24 V value = e.getValue(); 25 // constructor-evict:false 26 // putAll-evict:true 27 putVal(hash(key), key, value, false, evict); 28 } 29 } 30 } -
核心put()方法 逻辑图解
注意
tab[i = (n - 1) & hash]用来确认插入的新Node在哈希桶**table[]**中的index（后面详解）1 /** 2 * Implements Map.put and related methods 3 * 4 * @param hash hash for key 5 * @param key the key 6 * @param value the value to put 7 * @param onlyIfAbsent if true, don't change existing value 8 * @param evict if false, the table is in creation mode. 9 * @return previous value, or null if none 10 */ 11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 12 boolean evict) { 13 Node<K,V>[] tab; 14 Node<K,V> p; 15 int n, i; 16 // table为空，创建，扩容table 17 if ((tab = table) == null || (n = tab.length) == 0) 18 n = (tab = resize()).length; 19 // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中) 20 if ((p = tab[i = (n - 1) & hash]) == null) 21 tab[i] = newNode(hash, key, value, null); 22 else { 23 // 桶中【已经存】在元素，找出重复的元素 24 Node<K,V> e; K k; 25 // 比较桶中第一个元素(数组中的结点)的hash值相等，且key已经存在！ 26 if (p.hash == hash && 27 ((k = p.key) == key || (key != null && key.equals(k)))) 28 // 将第一个元素赋值给e，用e来记录 29 e = p; 30 // 判断节点是否为树 31 else if (p instanceof TreeNode) 32 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 33 else { 34 // 判断节点是否为链表 35 for (int binCount = 0; ; ++binCount) { 36 // 链表中后续节点没有重复值，插入为新节点 37 if ((e = p.next) == null) { 38 p.next = newNode(hash, key, value, null); 39 // 树化阈值校验 40 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 41 treeifyBin(tab, hash); 42 break; 43 } 44 // 找到链表中重复的元素 45 if (e.hash == hash && 46 ((k = e.key) == key || (key != null && key.equals(k)))) 47 break; 48 p = e; 49 } 50 } 51 // 存在重复的key在map 52 if (e != null) { // existing mapping for key 53 V oldValue = e.value; 54 if (!onlyIfAbsent || oldValue == null) 55 // 覆盖旧值 56 e.value = value; 57 afterNodeAccess(e); 58 return oldValue; 59 } 60 } 61 // 插入元素后，检查是否超过阈值 62 ++modCount; 63 if (++size > threshold) 64 resize(); 65 afterNodeInsertion(evict); 66 return null; 67 } -
扩容resize()方法
1 /** 2 * 初始化或加倍数组的大小。如果为空，则根据属性阈值中保持的初始容量目标进行分配。 3 * 否则，因为我们使用的是2的幂，所以每个bin中的元素必须保持相同的索引，或者在新表中以2的幂偏移。 4 * 5 * @return the table 6 */ 7 final Node<K,V>[] resize() { 8 Node<K,V>[] oldTab = table; 9 int oldCap = (oldTab == null) ? 0 : oldTab.length; 10 int oldThr = threshold; 11 int newCap, newThr = 0; 12 // 扩容前 Hash桶数组不为空 13 if (oldCap > 0) { 14 // 超过最大值就不再扩充了，就只好随你碰撞去吧 15 if (oldCap >= MAXIMUM_CAPACITY) { 16 threshold = Integer.MAX_VALUE; 17 return oldTab; 18 } 19 // 没超过最大值，就扩充为原来的2倍(翻倍后不能大于最大容量) 20 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 21 oldCap >= DEFAULT_INITIAL_CAPACITY) 22 newThr = oldThr << 1; // double threshold 23 } 24 // 扩容前 Hash桶数组为空(刚初始化之后) 25 else if (oldThr > 0) // initial capacity was placed in threshold 26 newCap = oldThr; 27 // 初始化时 threshold=0（表示使用默认值 DEFAULT_INITIAL_CAPACITY） 28 else { // zero initial threshold signifies using defaults 29 newCap = DEFAULT_INITIAL_CAPACITY; 30 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 31 } 32 33 // 计算新的resize上限 34 if (newThr == 0) { 35 float ft = (float)newCap * loadFactor; 36 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 37 (int)ft : Integer.MAX_VALUE); 38 } 39 threshold = newThr; 40 @SuppressWarnings({"rawtypes","unchecked"}) 41 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 42 table = newTab; 43 if (oldTab != null) { 44 // 把每个bucket都移动到新的buckets中 45 for (int j = 0; j < oldCap; ++j) { 46 Node<K,V> e; 47 if ((e = oldTab[j]) != null) { 48 oldTab[j] = null; 49 if (e.next == null) 50 newTab[e.hash & (newCap - 1)] = e; 51 else if (e instanceof TreeNode) 52 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 53 else { // preserve order 54 // 链表优化重hash的代码块 55 Node<K,V> loHead = null, loTail = null; 56 Node<K,V> hiHead = null, hiTail = null; 57 Node<K,V> next; 58 do { 59 next = e.next; 60 // 原index 61 if ((e.hash & oldCap) == 0) { 62 if (loTail == null) 63 loHead = e; 64 else 65 loTail.next = e; 66 loTail = e; 67 } 68 // 原index + oldCap 69 else { 70 if (hiTail == null) 71 hiHead = e; 72 else 73 hiTail.next = e; 74 hiTail = e; 75 } 76 } while ((e = next) != null); 77 // 原index放到bucket里 78 if (loTail != null) { 79 loTail.next = null; 80 newTab[j] = loHead; 81 } 82 // 原index + oldCap放到bucket里 83 if (hiTail != null) { 84 hiTail.next = null; 85 newTab[j + oldCap] = hiHead; 86 } 87 } 88 } 89 } 90 } 91 return newTab; 92 }
Why HashMap insert new Node on index (n - 1) & hash?
-
任何HashMap中的哈希桶数组**table[]**有
size = 2 ^ n(n >= 0)1//这个方法可以保证大小一定是 2的n次幂 2// cap - 指定hashmap的容量 3// 返回值 - 扩容的阈值，即 table[]的可以大小 4static final int tableSizeFor(int cap) { 5 int n = cap - 1; 6 n |= n >>> 1; 7 n |= n >>> 2; 8 n |= n >>> 4; 9 n |= n >>> 8; 10 n |= n >>> 16; 11 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 12} -
例：给定容量 cap = 5
1 cap = 5 2 n = cap - 1 = 4 = 0 1 0 0 3 n |= n >>> 1; 0 1 0 0 | 0 0 1 0 = 0 1 1 0 = 6 4 n |= n >>> 2; 0 0 1 1 | 0 1 1 0 = 0 1 1 1 = 7 5 n |= n >>> 4; 0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7 6 n |= n >>> 8; 0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7 7 n |= n >>> 16; 0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7 8 return n + 1 7 + 1 = 8
table的size = 8 新节点的index计算为：Node<K,V> p = tab[i = (n - 1) & hash]; n=8 模运算方式：Node<K,V> p = tab[i = hash % n]; 这里就将取模转换成了两数相& hash % n == (n-1) & hash
-
HashMap中设计hash算法的两处：
1//重新计算哈希值 2static final int hash(Object key) { 3 int h; 4 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key如果是null 新hashcode是0 5 否则 计算新的hashcode 6} 7 8//计算数组槽位 9(n - 1) & hash^：按位异或运算，只要位不同结果为1，不然结果为0
>>> ：无符号右移：右边补0
举例子：
1h=key.hashcode() 1111 1101 1101 1111 0101 1101 0010 1111 2h >>> 16 0000 0000 0000 0000 1111 1101 1101 1111 3 4h ^ (h >» 16) 1111 1101 1101 1111 1010 0000 1111 0000 5h=key.hashcode() 1111 1101 1101 1111 0101 1101 0010 1111将h无符号右移16为相当于将高区16位移动到了低区的16位，再与原hashcode做异或运算，可以将高低位二进制特征混合起来
根据异或真值高区16位没有改变，低区的16位发生了变化
通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算，可以把_高区与低区的二进制特征混合到低区_（疑问），那么为什么要这么做呢？
我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算，计算公式：(n - 1) & hash，假如这时数组槽位有16个，则槽位计算如下：
1hash 1111 1101 1101 1111 1010 0000 1111 0000 216-1 0000 0000 0000 0000 0000 0000 0000 1111 3 416-1 & hash 0000 0000 0000 0000 0000 0000 0000 0000解释
可以发现，高区的16位很有可能会被数组槽位数的二进制码锁屏蔽（被0且弄成了0），如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征
1因为在使用 n-1 & hash 这种方式取哈希桶的index的操作中，高位很有可能被(n-1)&操作忽略掉了。 2增加了低位相同，而高位不通时的碰撞概率，所以才用了上面的^异或操作将高位的数字和低位混合起来也许你可能会说，即使丢失了高区特征不同hashcode也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现
那为什么选择^异或操作呢？
异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值会向1靠拢，采用|运算计算出来的值会向0靠拢
开头我们讲过hashmap如何保证table[]的size一直是2的n次幂，那为什么槽位数必须使用2^n？
1、为了让哈希后的结果更加均匀
这个原因我们继续用上面的例子来说明
假如槽位数不是16，而是17，则槽位计算公式变成：(17 - 1) & hash
从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难
2、可以通过位运算e.hash & (newCap - 1)来计算，a % (2^n) 等价于 a & (2^n - 1) ，位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算
关于红黑树对hashmap的性能（插入，查找，删除）提升，可以去看红黑树的文章。
最后发挥钻牛角尖的精神，为什么m % (2^n) 等价于m & (2^n - 1)呢？
证明：
//todo 待完善...
原理： 当c是2的幂时，例如0111111 当c-1的二进制为：0111110； 而b的二进制为：01010101011； 结果：101010 求与运算后，b的高位值舍去，结果只能小于c，并且低位值不变（最后一位是0），正好是余数。为什么c要减1，因为余数必须是0到（c-1）,不能等于c。
补充
数学知识回顾
- << : 左移运算符，num << 1,相当于num乘以2 低位补0 举例：3 << 2 将数字3左移2位，将3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011，然后把该数字高位(左侧)的两个零移出，其他的数字都朝左平移2位，最后在低位(右侧)的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，则转换为十进制是12。 数学意义： 在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。
- >>: 右移运算符 举例：11 >> 2 则是将数字11右移2位，11 的二进制形式为：0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010。转换为十进制是3。 数学意义： 右移一位相当于除2，右移n位相当于除以2的n次方。这里是取商哈，余数就不要了。
- >>> : 无符号右移，忽略符号位，空位都以0补齐 按二进制形式把所有的数字向右移动对应位数，低位移出(舍弃)，高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同。 其他结构和>>相似。
- % : 模运算 取余 简单的求余运算
- ^ : 位异或 第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0 0^0=0， 1^0=1， 0^1=1， 1^1=0
- & : 与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0 0&0=0， 0&1=0， 1&0=0， 1&1=1
- | : 或运算 第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0 0|0=0， 0|1=1， 1|0=1， 1|1=1
- ~ : 非运算 操作数的第n位为1，那么结果的第n位为0，反之，也就是取反运算（一元操作符：只操作一个数） ~1=0， ~0=1
参考链接：
https://stackoverflow.com/questions/27230938/why-hashmap-insert-new-node-on-index-n-1-hash
https://www.cnblogs.com/zxporz/p/11204233.html
https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java
https://www.cnblogs.com/wang-meng/p/9b6c35c4b2ef7e5b398db9211733292d.html