1. 基本原理
- HashMap 是基于哈希表的数据结构实现的
- 哈希表的主干部分是由数组实现的，查找元素效率很高；
- put(E) 插入一个元素时，对这个元素进行哈希计算 hashCode = hash(E)，然后对数组的长度进行 % 模运行，确定元素在数组中的位置；
- hash 冲突：
- 造成的原因：
- 由于不同的两个关键值的 hashCode 会由很小的可能性是相同的，会造成在数组中元素的地址冲突；
- 也有可能两个关键值的 hashCode 不同，但是在对数组长度进行模运算的结果是相同的，造成数组中的元素地址冲突；
- 解决办法：
- JDK 1.7 中，哈希表的主干还是数组，当由于 hash 冲突造成两个元素在数组的位置相同时，就会把这些相同的元素串成一个链表；（链表比较）
- JDK 1.8 对哈希表性能进行了优化，当链表上数据过多时（大于8），会将链表转化成红黑树，利用红黑树快速增删改查的特点提高 HashMap 的性能，其中会用到红黑树的插入、删除、查找等算法。
- 造成的原因：
2. 核心成员变量作用分析
//默认初始容量，必须是2的幂，值为16。static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//构造函数中没有指定时，默认使用的负载因子 0.75fstatic final float DEFAULT_LOAD_FACTOR = 0.75f;//最大容量限制：2的30次方，大概10亿static final int MAXIMUM_CAPACITY = 1 << 30;//当桶(bucket)上的结点数大于这个值时会转成红黑树static final int TREEIFY_THRESHOLD = 8;//当桶(bucket)上的结点数小于这个值时树转链表，前提是它当前是红黑树结构static final int UNTREEIFY_THRESHOLD = 6;//当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。static final int MIN_TREEIFY_CAPACITY = 64;//transient://* 1.在已序列化的类中使变量不序列化——在已实现序列化的类中，有的变量不需要保存在磁盘中，就要transient关键字修饰.//* 2.transient只能修饰成员变量，不能修饰方法。// 哈希表的主干数组，里面的元素都是Node，可以串成单向链表来解决 hash 冲突，数组长度总是2的幂次倍transient Node<K,V>[] table;// map中包含的key-value对的个数，注意这个不等于数组的长度transient int size;// 每次扩容和更改map结构的计数器transient int modCount;//threshold = capacity * loadFactor，当Size>=threshold的时候，//那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准。//临界值 当实际大小超过临界值(容量*负载因子)时，会进行扩容int threshold;//loadFactor负载因子是控制数组存放数据的疏密程度//loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。final float loadFactor;// 一个关键内部类，主干数组中的元素类型，包含：key的hash值，Key，Value，next指针// 可以串成一个单向链表static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;}
3. 核心方法的原理（JDK1.8）
3.1 构造函数
- 使用构造函数创建 HashMap 实例时，并不会立刻创建哈希主干数组和分配内存空间，而是在 put(K,V) 第一个元素的时候才会调用 resize() 方法初始化数组，并分配内存空间；
构造函数执行的时候，主要是准备一些关键成员变量的值，如果没有传参就使用默认值；
(1) 默认构造函数 new HashMap()
HashMap 使用默认初始容量（16）和默认加载因子（0.75）构造
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
(2) 带参构造函数 new HashMap(initialCapacity, loadFactor)
创建 map 时指定初始容量，负载因子；
根据输入的初始容量，计算出 threshold 的值，这个值是2的整数次幂中大于容量，且最接近容量的整数；例如指定容量 10，threshold 就是 16；
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}
3.2 tableSizeFor(initialCapacity)
// n|=n>>1 等价于 n=n|(n>>1)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;}
作用：
- 如果 cap 是2的整数次幂，则返回当前值，如输入 16，返回 16
- 如果 cap 不是2的整数次幂，则返回一个比给定整数 cap 大，且最接近2的幂次方的整数，如输入10，返回16
- 代码分析：
cap=17，n=cap-1=16，经过五次右移位运算之后，n变为（cap-1）的掩码，即全为0001 1111，返回最后结果（掩码+1）时即变为0010 0000（32），正好是2的整数次幂
int n = cap -1，目的就是防止 cap 正好是2的整数次幂，如果不减的话，经过5次位运算和或运算后，变为 cap 二进制的掩码，最后 cap+1 就相当于将当前的数值乘2，扩大了范围，并不是我们想要（我们希望的是如果 cap 满足2的幂次，如果不满足就扩大到最接近的2的幂次）
- 为什么数组容量一定要满足 2 的幂次呢？
- 这与 HashMap 中元素在 table 中下标的计算有关：
- index = (table.length-1) & hash;
- 当 table.length 一定满足 2 的幂次时，（table.length-1）就会得到一个数字的掩码（1111*），这样用掩码与 hash 进行 “&” 运算时，最终下标的位置取决于 hash 值，如果 hash 值是1，那么最终结果也是1，hash 值是0，那么最终结果也是0；
- hash 算法的目的就是为了让 hash 值均匀的分布在数组中，如果数组容量满足2的幂次，那么在计算元素位置下标时，才能最大限度的利用 hash 值进行更好的散列；如果不适用 2 的幂次作为数组长度，那么 key 在数组中的散列结果会受到数组长度的影响，散列不均匀，会导致大量不同的 key 的元素有很大概率进入到相同的数组槽中，形成链表，性能下降；
- 这与 HashMap 中元素在 table 中下标的计算有关：
3.2 put(K, V)
- 如果插入的是新的 key，返回 null
如果插入的 key 已存在，新的 value 覆盖原来的值，并返回原来的值；
(1) 代码分析
创建 map 实例
- new HashMap(10, 0.75f)
- loadFactor=0.75，threshold=16
- table=null
- new HashMap(10, 0.75f)
putVal() 插入第一个元素 <”100”, “100”>
- 获取 key 的 hash 值：0000 0000 0000 0000 1011 1101 1111 0001
- hashCode=48625: 0000 0000 0000 0000 1011 1101 1111 0001
- h>>>16: 0000 0000 0000 0000 0000 0000 0000 0000
- 异或运算: 0000 0000 0000 0000 1011 1101 1111 0001
- 调用 resize() 初始化了数组 table[16]，并为之分配内存空间
- oldCap=table.length=0，oldThr=threshold=16，newThr=0，newCap=0
- newCap=oldThr=16，newThr=newCaploadFactor=160.75=12
- threshold=newThr=12
- table = Node
tab[i = (table.length - 1) & hash]定位 map 中的元素，例如：- hash： 0000 0000 0000 0000 1011 1101 1111 0001
- length-1=15 0000 0000 0000 0000 0000 0000 0000 1111
- &与运算： 0000 0000 0000 0000 0000 0000 0000 0001
- 定位到 table[1]，如果这是一个空位置，直接放入 Node(48625, “100”, “100”, null)
- 获取 key 的 hash 值：0000 0000 0000 0000 1011 1101 1111 0001
putVal() 插入第二个元素 <”1000”, “1000”>
- 获取 key 的 hash 值：0000 0000 0001 0111 0000 0000 0100 1000
- hashCode/1507423: 0000 0000 0001 0111 0000 0000 0101 1111
- h>>>16: 0000 0000 0000 0000 0000 0000 0001 0111
- 异或运算： 0000 0000 0001 0111 0000 0000 0100 1000
tab[i = (table.length - 1) & hash]定位 map 中的元素，例如：- hash： 0000 0000 0001 0111 0000 0000 0100 1000
- length-1=15 0000 0000 0000 0000 0000 0000 0000 1111
- &与运算： 0000 0000 0000 0000 0000 0000 0000 1000
- 定位到 table[8]，如果这是一个空位置，直接放入 Node(48625, “1000”, “1000”, null)
- 获取 key 的 hash 值：0000 0000 0001 0111 0000 0000 0100 1000
putVal() 插入第三个元素 <”1000”, “2000”>
- 获取 key 的 hash 值
- Node
tab[i = (table.length - 1) & hash]定位 map 中的元素不为 null，发生 hash 冲突了
如果 p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))，即新元素和旧元素 p 的 key 相同，则用新的 value 覆盖原来的 value；
JDK1.8 之后，如果出现大量 hash 冲突，链表长度达到8，就会将链表转为红黑树，像 get() 操作的时间复杂度就会从链表的 O(n) 变为红黑树的 O(logn)，性能是有很大提升的。
- 当你遍历一个链表达到第7个节点的时候，binCount 是6
- 当你遍历到第8个节点，此时 binCount 是7，同时你挂上了第9个节点，然后就会发现 binCount >= 7，达到了临界值，即当你的链表节点的数量超过8的时候，此时就会将链表转换为红黑树。(红黑树太复杂，不深入JDK中红黑树的实现了…)
因为 HashMap 底层是基于数组来实现的主干数据结构，这就涉及到数组满了后必须要扩容的问题
- JDK1.7采用的是数组长度2倍扩容 + rehash（对数组长度求模，性能低），每个 key-value 对，都会基于 key 的 hash 值重新寻址找到新数组的新的位置。
- JDK1.8采用的是数组长度2的 n 次方扩容（newThr = oldThr << 1;） + rehash（key 的 hash 值和（数组长度-1）进行与操作符来实现 hash 寻址）。
resize() 方法实现了扩容+rehash，当 map 中元素的个数达到扩容阈值 threshold（构建map的时候，初始值16，之后就是32）
- 如果当前数组未初始化，则会初始化数组 Node
- 如果数组已经初始化，则会将数组扩容到之前的两倍（tab.length<<1，位运算左移1位，扩大两倍）
- 进行对元素进行 rehash： ```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
- 如果当前数组未初始化，则会初始化数组 Node
// hashMap中的key哈希算法 // 先获取key的hash值 // h >>> 16，将key的hash值作为32位的二进制数，右移16位。再与key的hash(32位二进制)异或操作 //例如，key.hashCode()=48625，32位二进制：0000 0000 0000 0000 1011 1101 1111 0001 // 0000 0000 0000 0000 1011 1101 1111 0001，再右移16位： // 0000 0000 0000 0000 0000 0000 0000 0000，再异或运算 // 0000 0000 0000 0000 1011 1101 1111 0001 => key的最后hash值 // h^(h>>>16) 的目的是为了通过这样算出来的hash值，可以降低hash冲突的概率 // 因为后面根据hash定位数组index的时候，一般都是用hash的低16位参与位运算 // 而使用右移和异或运算，相当于将高16位与低16位异或，让高16位和低16位都参与了数组定位的计算， // 这样就降低了hash冲突的概率 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node
// 进入这个条件分支，说明通过hash定位到的数组位置，是已经有了Node了
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// Key相同，覆盖旧的 value
e = p;
// 如果这个位置已经是一个红黑树的话，使用 TreeNode.putTreeVal() 方法插入新节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// key不一样，出现了hash冲突
// 然后此时还不是红黑树的数据结构，还是链表的数据结构，在这里，就会通过链表来处理
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 遍历到链表的最后一个节点，插入新节点
p.next = newNode(hash, key, value, null);
//如果当前链表长度(binCount)大于等于TREEIFY_THRESHOLD-1，
//即链表长度达到8的话，此时需要将这个链表转为一个红黑树的数据结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final Node
// 分析 rehash 过程
if (oldTab != null) {
// 遍历旧数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 1.如果旧数组中不存在碰撞,则直接移动到新数组的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 2.如果存在碰撞，且节点类型是树节点，则进行树节点拆分(挂载到扩容后的数组中或者转为链表)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 3.如果存在 hash冲突，且链表的情况,会保留原有节点的顺序
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 4. 判断扩容后元素是否在原有的位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 5. 元素不是在原有位置
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 6. 将扩容后未改变index的元素复制到新数组
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 7. 将扩容后改变了index位置的元素复制到新数组
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} ```
若有收获，就点个赞吧
0 人点赞
