基于 Hash 的原理。
2 什么是哈希？最简略模式的 hash，是一种在对任何变量 / 对象的属性利用任何公式 / 算法后， 为其调配惟一代码的办法。
一个真正的 hash 办法必须遵循上面的准则：
“
哈希函数每次在雷同或相等的对象上利用哈希函数时, 应每次返回雷同的哈希码。换句话说, 两个相等的对象必须统一地生成雷同的哈希码。
Java 中所有的对象都有 Hash 办法，Java 中的所有对象都继承 Object 类中定义的 hashCode() 函数的默认实现。此函数通常通过将对象的外部地址转换为整数来生成哈希码，从而为所有不同的对象生成不同的哈希码。
Map 的定义是：将键映射到值的对象。
因而，HashMap 中必须有一些机制来存储这个键值对。答案是必定的。HashMap 有一个外部类 Node，如下所示：
static class Node implements Map.Entry {
final int hash; // 记录hash值， 以便重hash时不须要再从新计算
final K key;
V value;
Node next;
...// 其余的代码
}
当然，Node 类具备存储为属性的键和值的映射。
key 已被标记为 final，另外还有两个字段：next 和 hash。
在上面中， 咱们将会了解这些属性的必须性。
4 键值对在 HashMap 中是如何存储的键值对在 HashMap 中是以 Node 外部类的数组寄存的， 如下所示：
transient Node[] table;
哈希码计算出来之后， 会转换成该数组的下标， 在该下标中存储对应哈希码的键值对， 在此先不具体解说 hash 碰撞的状况。
该数组的长度始终是 2 的次幂， 通过以下的函数实现该过程
static final int tableSizeFor(int cap) {
int n = cap - 1;// 如果不做该操作， 则如传入的 cap 是 2 的整数幂， 则返回值是料想的 2 倍
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) 的低二进制全副变为 1， 最初加 1 即可取得对应的大于 cap 的 2 的次幂作为数组长度。
为什么要应用 2 的次幂作为数组的容量呢？
在此有波及到 HashMap 的 hash 函数及数组下标的计算， 键 (key) 所计算出来的哈希码有可能是大于数组的容量的， 那怎么办？
能够通过简略的求余运算来取得， 但此办法效率太低。HashMap 中通过以下的办法保障 hash 的值计算后都小于数组的容量。
(n - 1) & hash
这也正好解释了为什么须要 2 的次幂作为数组的容量。因为 n 是 2 的次幂， 因而， n &＃8211; 1 相似于一个低位掩码。
通过与操作， 高位的 hash 值全副归零，保障低位才无效， 从而保障取得的值都小于 n。同时， 在下一次 resize() 操作时， 从新计算每个 Node 的数组下标将会因而变得很简略， 具体的后文解说。
以默认的初始值 16 为例：
01010011 00100101 01010100 00100101
& 00000000 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000000 00000101 //高位全副归零，只保留末四位
// 保障了计算出的值小于数组的长度 n
然而， 应用了该性能之后， 因为只取了低位， 因而 hash 碰撞会也会相应的变得很重大。这时候就须要应用 「扰动函数」
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
该函数通过将哈希码的高 16 位的右移后与原哈希码进行异或而失去， 以以上的例子为例
异或
此办法保障了高 16 位不变， 低 16 位依据异或后的后果扭转。计算后的数组下标将会从原先的 5 变为 0。
应用了 「扰动函数」 之后， hash 碰撞的概率将会降落。有人专门做过相似的测试， 尽管应用该 「扰动函数」 并没有取得最大概率的防止 hash 碰撞， 但思考其计算性能和碰撞的概率， JDK 中应用了该办法， 且只 hash 一次。
5 哈希碰撞及其解决在现实的状况下， 哈希函数将每一个 key 都映射到一个惟一的 bucket， 然而， 这是不可能的。哪怕是设计在良好的哈希函数， 也会产生哈希抵触。
前人钻研了很多哈希抵触的解决办法， 在维基百科中， 总结出了四大类
哈希碰撞解决办法
在 Java 的 HashMap 中， 采纳了第一种 Separate chaining 办法 (大多数翻译为拉链法)+ 链表和红黑树来解决抵触。
JDK8 中 HashMap 后果
在 HashMap 中， 哈希碰撞之后会通过 Node 类外部的成员变量 Node 来造成一个链表 (节点小于 8) 或红黑树（节点大于 8， 在小于 6 时会从新转换为链表）， 从而达到解决抵触的目标。
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
public HashMap();
public HashMap(int initialCapacity);
public HashMap(Map m);
public HashMap(int initialCapacity, float loadFactor);
HashMap 中有四个构造函数， 大多是初始化容量和负载因子的操作。以 public HashMap(int initialCapacity, float loadFactor) 为例
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;
this.threshold = tableSizeFor(initialCapacity);
}
通过该函数进行了容量和负载因子的初始化，如果是调用的其余的构造函数， 则相应的负载因子和容量会应用默认值（默认负载因子 = 0.75， 默认容量 = 16）。
在此时， 还没有进行存储容器 table 的初始化， 该初始化要提早到第一次应用时进行。HashMap 面试 21 问！面试的举荐你看下。关注公众号 Java 技术栈回复面试获取更多面试材料。
7 HashMap 中哈希表的初始化或动静扩容所谓的哈希表， 指的就是上面这个类型为外部类Node的 table 变量。
transient Node[] table;
作为数组， 其在初始化时就须要指定长度。在理论应用过程中， 咱们存储的数量可能会大于该长度，因而 HashMap 中定义了一个阈值参数 (threshold)， 在存储的容量达到指定的阈值时， 须要进行扩容。
我集体认为初始化也是动静扩容的一种， 只不过其扩容是容量从 0 扩大到构造函数中的数值（默认 16）。而且不须要进行元素的重 hash.
初始化的话只有数值为空或者数组长度为 0 就会进行。而扩容是在元素的数量大于阈值（threshold）时就会触发。
threshold = loadFactor * capacity
比方 HashMap 中默认的 loadFactor=0.75, capacity=16, 则
threshold = loadFactor * capacity = 0.75 * 16 = 12
那么在元素数量大于 12 时， 就会进行扩容。扩容后的 capacity 和 threshold 也会随之而扭转。
负载因子影响触发的阈值， 因而， 它的值较小的时候， HashMap 中的 hash 碰撞就很少， 此时存取的性能都很高， 对应的毛病是须要较多的内存；而它的值较大时， HashMap 中的 hash 碰撞就很多， 此时存取的性能绝对较低， 对应长处是须要较少的内存；不倡议更改该默认值， 如果要更改， 倡议进行相应的测试之后确定。
后面说过了数组的容量为 2 的整次幂， 同时， 数组的下标通过上面的代码进行计算
index = (table.length - 1) & hash
该办法除了能够很快的计算出数组的索引之外， 在扩容之后， 进行重 hash 时也会很奇妙的就能够算出新的 hash 值。因为数组扩容之后， 容量是当初的 2 倍， 扩容之后 n-1 的无效位会比原来多一位， 而多的这一位与原容量二进制在同一个地位。示例
扩容前后
这样就能够很快的计算出新的索引啦
具体的看代码吧
final Node[] resize() {
//新建oldTab数组保留扩容前的数组table
Node[] oldTab = table;
//获取原来数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原来数组扩容的临界值
int oldThr = threshold;
int newCap, newThr = 0;
//如果扩容前的容量 > 0
if (oldCap > 0) {
//如果原来的数组长度大于最大值(2^30)
if (oldCap >= MAXIMUM_CAPACITY) {
//扩容临界值进步到正无穷
threshold = Integer.MAX_VALUE;
//无奈进行扩容，返回原来的数组
return oldTab;
//如果当初容量的两倍小于MAXIMUM_CAPACITY且当初的容量大于DEFAULT_INITIAL_CAPACITY
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//临界值变为原来的2倍
newThr = oldThr << 1;
} else if (oldThr > 0) //如果旧容量 <= 0，而且旧临界值 > 0
//数组的新容量设置为老数组扩容的临界值
newCap = oldThr;
else { //如果旧容量 <= 0，且旧临界值 <= 0，新容量裁减为默认初始化容量，新临界值为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
newCap = DEFAULT_INITIAL_CAPACITY;//新数组初始容量设置为默认值
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//计算默认容量下的阈值
}
// 计算新的resize下限
if (newThr == 0) {//在当下面的条件判断中，只有是初始化时(oldCap=0, oldThr > 0)时，newThr == 0
//ft为长期临界值，上面会确定这个临界值是否非法，如果非法，那就是真正的临界值
float ft = (float) newCap * loadFactor;
//当新容量< MAXIMUM_CAPACITY且ft < (float)MAXIMUM_CAPACITY，新的临界值为ft，否则为Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//将扩容后hashMap的临界值设置为newThr
threshold = newThr;
//创立新的table，初始化容量为newCap
@SuppressWarnings({"rawtypes", "unchecked"})
Node[] newTab = (Node[]) new Node[newCap];
//批改hashMap的table为新建的newTab
table = newTab;
//如果旧table不为空，将旧table中的元素复制到新的table中
if (oldTab != null) {
//遍历旧哈希表的每个桶，将旧哈希表中的桶复制到新的哈希表中
for (int j = 0; j < oldCap; ++j) {
Node e;
//如果旧桶不为null，应用e记录旧桶
if ((e = oldTab[j]) != null) {
//将旧桶置为null
oldTab[j] = null;
//如果旧桶中只有一个node
if (e.next == null)
//将e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的地位
newTab[e.hash & (newCap - 1)] = e;
//如果旧桶中的构造为红黑树
else if (e instanceof TreeNode)
//将树中的node拆散
((TreeNode) e).split(this, newTab, j, oldCap);
else { //如果旧桶中的构造为链表,链表重排，jdk1.8做的一系列优化
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
//遍历整个链表中的节点
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {// 原索引+oldCap
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
尽管 HashMap 设计的十分优良， 然而应该尽可能少的防止 resize(), 该过程会很消耗工夫。
同时， 因为 hashmap 不能主动的放大容量。因而， 如果你的 hashmap 容量很大， 但执行了很多 remove 操作时， 容量并不会缩小。如果你感觉须要缩小容量， 请从新创立一个 hashmap。
8 HashMap.put() 函数外部是如何工作的？在应用屡次 HashMap 之后， 大体也能说出其增加元素的原理：计算每一个 key 的哈希值， 通过肯定的计算之后算出其在哈希表中的地位，将键值对放入该地位，如果有哈希碰撞则进行哈希碰撞解决。
而其工作时的原理如下（图是我很早之前保留的， 忘了出处了）
源码如下：
/* @param hash 指定参数key的哈希值
* @param key 指定参数key
* @param value 指定参数value
* @param onlyIfAbsent 如果为true，即便指定参数key在map中曾经存在，也不会替换value
* @param evict 如果为false，数组table在创立模式中
* @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的value就是null。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab;
Node p;
int n, i;
//如果哈希表为空，调用resize()创立一个哈希表，并用变量n记录哈希表长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 如果指定参数hash在表中没有对应的桶，即为没有碰撞
* Hash函数，(n - 1) & hash 计算key将被搁置的槽位
* (n - 1) & hash 实质上是hash % n，位运算更快
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//间接将键值对插入到map中即可
tab[i] = newNode(hash, key, value, null);
else {// 桶中曾经存在元素
Node e;
K k;
// 比拟桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
// 以后桶中无该键值对，且桶是红黑树结构，依照红黑树结构插入
else if (p instanceof TreeNode)
e = ((TreeNode) 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;
}
// 链表节点的与put操作雷同时，不做反复操作，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到或新建一个key和hashCode与插入元素相等的键值对，进行put操作
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;
// 键值对数目超过阈值时，进行rehash
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
在此过程中， 会波及到哈希碰撞的解决。
9 HashMap.get() 办法外部是如何工作的？/**
* 返回指定的key映射的value，如果value为null，则返回null
* get能够分为三个步骤：
* 1.通过hash(Object key)办法计算key的哈希值hash。
* 2.通过getNode( int hash, Object key)办法获取node。
* 3.如果node为null，返回null，否则返回node.value。
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node e;
//依据key及其hash值查问node节点，如果存在，则返回该节点的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
其最终是调用了 getNode 函数。其逻辑如下
getNode 工作逻辑
源码如下：
/**
* @param hash 指定参数key的哈希值
* @param key 指定参数key
* @return 返回node，如果没有则返回null
*/
final Node getNode(int hash, Object key) {
Node[] tab;
Node first, e;
int n;
K k;
//如果哈希表不为空，而且key对应的桶上不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果桶中的第一个节点就和指定参数hash和key匹配上了
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//返回桶中的第一个节点
return first;
//如果桶中的第一个节点没有匹配上，而且有后续节点
if ((e = first.next) != null) {
//如果以后的桶采纳红黑树，则调用红黑树的get办法去获取节点
if (first instanceof TreeNode)
return ((TreeNode) first).getTreeNode(hash, key);
//如果以后的桶不采纳红黑树，即桶中节点构造为链式构造
do {
//遍历链表，直到key匹配
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//如果哈希表为空，或者没有找到节点，返回null
return null;
} 作者：阿进的写字台
出处：https://www.cnblogs.com/homejim/
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有