2020/10/23
Java集合之HashMap源码解析_gyl-coder - SegmentFault 思否
https://segmentfault.com/a/1190000015213253 1/12
gyl_coder 74
Java集合之HashMap源码解析
java hashmap的工作原理
发布于 2018-06-07
原文地址
HashMap
HashMap 是 Map 的一个实现类,它代表的是一种键值对的数据存储形式。
大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。
HashMap最多只允许一条记录的键为null,允许多条记录的值为null。不保证有序(比如插入的顺序)、也不保证序不随时间变化。
jdk 8 之前,其内部是由数组+链表来实现的,而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。
HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用
Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。
下面我们先来看一下HashMap内部所用到的存储结构
HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的
Node是HashMap的一个内部类,实现了Map.Entry接口,本质上就是一个映射(键值对)。
有时两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取
效率就会越高。
HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组。
如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞。
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}