算法基础③（哈希表简介及部分源码分析）
0x0001. 简介
-
基本概念
-
由两部分组成，数组 + 链表（红黑树，根据链表大小决定是否用）
-
链表实现：查找时间复杂度 --
红黑树实现：查找时间复杂度 --
-
-
关键难点
LoadFactor(负载因子) * Capacity(当前长度) > size==> 动态扩容- 解决
hash碰撞，链表+红黑树 - 扰动函数，使得概率分部平均
0x0002. put 函数源码解析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 为空处理，直接动态扩容（逻辑较为复杂，单独分析）
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 {
Node<K,V> e; K k;
// 数组的第一个位置
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 红黑树处理
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 链表处理，无限循环，找到要覆盖的节点 e，break 出局
for (int binCount = 0; ; ++binCount) {
// e 指向下一个节点
if ((e = p.next) == null) {
// 尾部插入
p.next = newNode(hash, key, value, null);
// 如果链表超过 8 个，转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 找到对应位置，key 相同，结束循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 链表迭代指向下一个
p = e;
}
}
// e 不为空，覆盖 e, 返回原值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 空
afterNodeAccess(e);
return oldValue;
}
}
// ？？
++modCount;
//更新size，并判断是否需要扩容。
if (++size > threshold)
resize();
//空
afterNodeInsertion(evict);
return null;
}
// hash 计算，扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
0x0003. put时内存状态和运算过程
TestHashMap.java
public class TestHashMap {
public static void main(String[] args) {
HashMap<String, Integer> programLanguage = new HashMap<>();
programLanguage.put("语文", 1);
programLanguage.put("数学", 2);
programLanguage.put("英语", 3);
programLanguage.put("历史", 4);
programLanguage.put("政治", 5);
programLanguage.put("地理", 6);
programLanguage.put("生物", 7);
programLanguage.put("化学", 8);
for (Entry<String, Integer> entry : programLanguage.entrySet()) {
System.out.println("key:" + entry.getKey() + " value:"+ entry.getValue());
System.out.println("hash code:" + entry.hashCode() + "\n");
}
}
}
输出结果
key:政治 value:5
hash code:831321
key:生物 value:7
hash code:958765
key:历史 value:4
hash code:684328
key:数学 value:2
hash code:828404
key:化学 value:8
hash code:682776
key:语文 value:1
hash code:1136443
key:英语 value:3
hash code:1074975
key:地理 value:6
hash code:721616
- 内存状态 （解决哈希碰撞）
>table: HashMap$Node[16]@17
> 0: HashMap$Node@31 "政治":"5"
1: null
2: null
3: null
4: HashMap$Node@32 "生物":"7"
5: null
6: HashMap$Node@33 "历史":"4"
7: null
8: null
9: null
10: HashMap$Node@19 "数学":"2"
11: HashMap$Node@34 "语文":"1"
12: HashMap$Node@35 "英语":"3"
13: HashMap$Node@36 "地理":"6"
14: null
15: null
>table[10].next: HashMap$Node@22 "化学":"8"
table[10].hash: 828410
-
扰动函数计算过程（让高位和低位同时影响最终的
hashCode）公式：
(h = key.hashCode()) ^ (h >>> 16)key.hashCode() = 682768(化学) hashCode = 682768 ^ (682768 >>> 16) = 682778 二进制状态下转换过程 682768 = 1010 0110 1011 0001 0000 补齐 0 后 ==> 0000 0000 0000 1010 0110 1011 0001 0000 >>> 16 （高位移至低位） = 0000 0000 0000 0000 0000 0000 0000 1010 0000 0000 0000 1010 0110 1011 0001 0000 ^ （高低位作异或运算） 0000 0000 0000 0000 0000 0000 0000 1010 = 0000 0000 0000 1010 0110 1011 0001 1010 补充:异或运算取决于两个值，与和或运算只取决于单个值补充：
-
取模
获取在数组中的位置:
tab[i = (n - 1) & hash]==>tab[10]n 是 HashMap 的长度，2^m ， 上述情景中 m = 4，n 为 16（数组长度），n = 0B10000
0000 0000 0000 0000 0000 0000 0001 0000 - 1 => 0000 0000 0000 0000 0000 0000 0000 1111 = 15 & 0000 0000 0000 1010 0110 1011 0001 1010 （682778，扰动函数得到的 hashCode) => 0000 0000 0000 0000 0000 0000 0000 1100 = 10 -
数组中已经有值，插入链表末端：
p.next = newNode(hash, key, value, null);