1.7版本：https://blog.csdn.net/LawssssCat/article/details/103211583
hash(Object k)
hashmap理所当然先知道hash值怎么计算的。
源码+翻译：(1.8)
/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. (调用key的方法计算hash值，并且把得到的hash值前16位和后16位做异或运算) * Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. * (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) (因为这个hash表用2的幂次作为masking，一些列随机的hash值在这种masking中非常容易发生碰撞。) Note： --- masking：掩码，冗余、容错， ==》 可扩展容量（我这里的理解） * So we apply a transform that spreads the impact of higher bits * downward. (因此我们应用了一种转换，把hash值中高的位向下扩展) * There is a tradeoff between speed, utility, and * quality of bit-spreading. (这要权衡到“位扩展”的处理速度、实用性和处理质量) * Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), (因为考虑到，有很多常见的一系列hash值是合理分布的(也就是这一些列hash值不会在“为扩展”中受益)) * and because we use trees to handle large sets of * collisions in bins, (其次考虑到，我们会使用tree结构来处理大量hash碰撞的情况) * we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, (所以，我们只是用最廉价的方式去减少 systematic lossage ，也就是说仅仅通过对一些位进行偏移异或操作。) --- systematic lossage 系统性损失 * as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. (而且，这样做，我们还能吸收到高位对hash的影响。否则，因为hash表的限制，那些高位的数会被丢弃，永远不会参与到index的计算。) */
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看完上面的注释，我们知道，1.8和1.7相比，hash计算简单的原因。
1.8中只是把 key 的 hashCode 前16位和后16位二进制数进行一次异或运算。
e.g.
put(K key, V value)
源码：(1.8)
/** * * Associates the specified value with the specified key in this map. * (把key和value关联进this.map) * If the map previously contained a mapping for the key, the old * value is replaced. * (如果map中已经包含了key映射，那么旧的value就会被替代) * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) * * return：如果没有存在key映射，就返回null，否则就返回之前的映射值。 * (返回null的情况还包含，存在key映射，但是key映射值为null的去情况) */
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * //TODO (待翻译) * @param evict if false, the table is in creation mode. * //TODO (待翻译) * @return previous value, or null if none */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初始化
//判断table是否为空，如果是空的就创建一个table，并获取他的长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//插入新数据 - 无碰撞
//如果计算出来的索引位置之前没有放过数据，就直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//覆盖 or 发生碰撞
//进入这里说明索引位置已经放入过数据了
Node<K,V> e; K k;
//查看table[0]的桶 的 hash、key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//key的地址或key的equals()只要有一个相等就认为key重复了，就直接覆盖原来key的value
e = p;
//hash或者，key不同 =》 碰撞 =》 判断是否已经是树
//判断是否是红黑树，如果是红黑树就直接插入树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果不是红黑树，就遍历每个节点，判断链表长度是否大于8，如果大于就转换为红黑树
//hash碰撞 - - 链表插入
for (int binCount = 0; ; ++binCount) {
//循环遍历到最后的节点， p->尾节点 ， e->尾节点下一个节点 -> null ,
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// ！！！ 注意 这里 ！！！！
// binCount >= 7 那么就把 链表 转成 红黑树
// 1个节点 循环0次
// 2个节点 循环1次 binCount=0
// 3个节点 循环2次 binCount=1
// 4个节点 循环3次 binCount=2
// ....
// 8个节点 循环7次 binCount=6
// 9个节点 循环8次 binCount=7
//所以，转树阈值TREEIFY_THRESHOLD=8时，是当第九节点被创立后，才开始链表到树的转换
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//判断索引每个元素的key是否可要插入的key相同，
//如果相同就跳出循环，跳出循环后，的语句就是，把元素直接覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// ** ** ** * **这里！！！！！ 把元素直接覆盖
//如果e不是null，说明没有迭代到最后就跳出了循环，
//说明链表中有相同的key，因此只需要将value覆盖，并将oldValue返回即可
//key完全相同，覆盖value
// ** ** ** * **这里！！！！！ 把元素直接覆盖
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;
}
京公网安备 11010502036488号