1. 了解Map接口及其内部的Entry接口
Map接口及Entry内部接口
2. 理解HashMap的实现原理(jdk1.8)
-
内部类
Node
Node是HashMap的一个内部类, 实现了Map.Entry接口, 本质是一个映射(键值对)
内部类Node
-
重要的字段
HashMap重要的字段
-
重要的常量
HashMap重要的常量
-
HashMap的构造函数(4个)
HashMap的构造函数
HashMap构造函数中用到一个静态方法tableSizeFor, 其作用是: 返回一个大于或等于initialCapacity且为2的次幂的整数;
tableSizeFor
tableSizeFor的例子
-
哈希函数("扰动函数")
扰动函数
上面代码里的key.hashCode()函数调用的是key类型自带的哈希函数, 返回int类型散列值;
理论上散列值是一个int类型, 将其作为下标访问table数组, 考虑到32位int类型的取值范围为[-2147483648, 2147483647], 前后加起来大概40亿的映射空间, 若哈希函数映射得比较松散, 一般应用是很难出现碰撞的;
实际考虑的是一个40亿长度的数组, 内存是放不下的, 所以这个散列值是不能直接拿来用的, 用之前要先对数组的长度取模运算, 得到的余数才能用来访问数组下标 :
hash(key) & (n- 1) // n 为 table数组的长度
这里解释了为什么table数组的长度一定要取2的整次幂
因为这样(数组长度 - 1)正好相当于一个"低位掩码"; "与"操作的结果就是散列值的高位全部归零, 只保留低位值, 用来做数组下标访问;
例子
由于与操作只取最后几位, 可能会造成严重的碰撞情况, 此时"扰动函数"的作用就体现出来了:
例子2
无符号右移16位, 正好是32位的一半, 自己的高半区和低半区做异或, 就是为了混合原始哈希码的高位和低位, 以此来加大低位的随机性, 而且混合后的低位夹杂有高位的部分特征, 从而变相地保留了高位的信息;
hash算法本质上就是三步：取 key 的 hashCode 高位异或运算 取模运算
- 扩容机制
JDK1.8使用2次幂的拓展(指长度扩为原来2倍), 所以, 元素的位置要么是在原位置, 要么是在原位置再移动2次幂的位置;
resize方法大致流程
源码分析:
/**
* 扩容机制
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table; // 原来的table数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 原来的table数组的容量
int oldThr = threshold; // 原来的table数组对应的阈值
// 拓容
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // 原来的table数组容量超过最大值, 则不再扩充
threshold = Integer.MAX_VALUE; // 更新threshold为Integer.MAX_VALUE
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) { // 原来的table数组容量没有超过最大值, 则扩充为原来的2倍
newThr = oldThr << 1;
}
} else if (oldThr > 0) { // 对应初始化函数中的this.threshold = tableSizeFor(initialCapacity);语句
newCap = oldThr;
} else { // 使用默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY) ?
(int) ft : Integer.MAX_VALUE;
}
threshold = newThr;
// 新建数组
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { // 把每一个bucket 移动到 新的buckets中
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) {
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) { // 红黑树重构
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
} else { // 链表重构
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> 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);
if (loTail != null) { // 原索引放到新的bucket里
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) { // 新索引(原索引 + oldCap)放到新的bucket里
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-
put方法
put方法的大致流程
源码分析：
/**
* 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) { // table 为 null 或 table.length == 0
n = (tab = resize()).length;
}
if ((p = tab[i = (n - 1) & hash]) == null) { // tab[i] 为 null 时直接插入
tab[i] = newNode(hash, key, value, null);
} else {
Node<K, V> e;
K k;
// key 与 table[i].key 相等的情况
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
} else if (p instanceof TreeNode) { // talbe[i]是TreeNode对象实例的情况
e.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) {
treeifyBin(tab, hash); // 将链表装换为红黑树
}
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))) {
break;
}
p = e;
}
}
if (e != null) { // 已经存在键值对(更新操作)
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
}
// 不存在键值对(插入操作)
++modCount; // 注意只有插入新结点时modCount才会加一
if (++size == threshold) { // 注意是否要扩容
resize();
}
afterNodeInsertion(evict);
return null;
}
}
-
get方法
get方法大致流程
源码分析:
/**
* get方法
*/
public V get(Object key) {
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
fianl Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
if ((tab == table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) { // 数组table 不为空, 数组table的长度大于0, 索引位置的值不为null
if (first.hash == hash &&
(k = first.key) == key || (key != null && key.equals(k))) { // 索引位置上第一个结点就是要查找的结点
return first;
}
if ((e = first.next) != null) {
if (first instanceof TreeNode) { // 索引位置上数据结构为红黑树则在树上查找对应的结点
return first.getTreeNode(hash, key);
}
// 索引位置上数据结构为链表则在链表上查找对应的结点
do {
if (e.hash == hash &&
((k = e.key) == key) || (key != null && key.equals(k))) {
return e;
}
} while ((e = e.next) != null);
}
}
return null; // 无对应的key值故返回null
}
网友评论