一、hashmap 数据结构
HashMap 主要的操作一般包括：
- V put(K key, V value)
- V get(Object key)
- V remove(Object key)
- Boolean containsKey(Object key)
jdk7 之前的hashmap
HashMap内部存储数据的方式是通过内部类Entry 来实现的，其中Entry 类的结构如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;//key 的hash 值
Entry<K,V> next;//指向该entry下一个元素
int hash;
}
HashMap put操作
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)//key 为null,
return putForNullKey(value);
int hash = hash(key);//获取key 的hash 值
int i = indexFor(hash, table.length);//将hash 值映射到数组中对应的索引位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//如果该元素在hashmap 中已存在，则替换原有的值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);//添加新的entry 元素到hashmap 中
return null;
}
hashmap内部存储的结构，其实就是一个entry 的数组，然后数组的每个位置(也称之为bucket)存储的是一个entry 的单链表，如下图所示。
image.png
- hash(key)相同的元素，存放在同一个entry 单链表中，
- 不同的元素，存放在entry 数组中不同的bucket中
当进行get (key) 操作时，首先会计算key对应在数组的位置，然后根据key 的equal() 方法，遍历entry 单链表 ，找到对应key 的值，反之 put(key,value)操作时类似，不同之处在于，是将该元素插入到entry 链表的头部。
整个bucket 链表的形成过程可以分为如下几步:
- 获取key 的hashcode 值
- 为了减少hash 冲突，需要对hashcode 值进行rehash 操作 （java8中hashcode右移16位 与hashcode 做异或运算，即高位与低位）
- 为了让元素存放到数组中对应的索引位置，需要对rehash 后的值与（数组长度-1）进行位运算。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
//让hashcode 的每一位都参与到了运算中来，减少了hash 冲突的发生
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
hashmap 什么情况下出现单链表
在createEntry方法中，主要有两步操作：
-
Entry<K,V> e = table[bucketIndex]获取数组中原来索引index位置的entry对象。 - 创建一个新的entry 对象 放入到数组中索引index位置处，
table[bucketIndex] = new Entry<>(hash, key, value, e);，从Entry 的构造函数就可以知道，如果原来的索引index位置的数据对象e 不为null，则此时新entry对象next->e。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
hashmap 扩容操作
hashmap 的一系列操作（get，put，remove）都会涉及到map中单链表的key遍历查找操作，假使忽略修改操作，这也是一个非常消耗性能的issue，例如，hashmap 的数组大小为16，存放20w的数据，在这种场景下，每一个entry 链表的平均大小为20w/16，这种情况之下一个key 的遍历查找次数和一个很可怕的数字，在这种情况之下，为了避免这种长度巨大的单链表的产生，hashmap有了一个自动扩容的操作，即resize。下面两个图，分别展示了扩容前后map 中数据分布情况。
image.png
hashmap 的默认初始大小为16
DEFAULT_INITIAL_CAPACITY = 1 << 4，负载因子为DEFAULT_LOAD_FACTOR = 0.75f
为什么hashmap 不是线程安全的？
因为，在hashmap 自动扩容的过程中，get和put 操作时，有可能获得是扩容前的数据，更糟糕的情况是，并发情况下，多个线程同时进行put 操作，此时可能会引起resize 操作，导致entry 链表中形成一个循环链表。
jdk8 hashmap
java8 中hashmap 有了很大的改进，java8 中hashmap 内部还是通过数组的存储方式，只不过，数组中存储的单元由java7 中的Entry 换成了Node,但是类结构和包含的信息是一样的，与java7 最大的不同之处在于Node 可以扩展成TreeNode，其中TreeNode 可以扩展成红黑树的数据结构，如下图所示。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
java8 hashmap数据结构.png
什么情况下扩展成红黑树呢?
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
* @param evict if false, the table is in creation mode.
* @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;
//当前hashmap 为空，触发map 的自动扩容resize 操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//i = (n - 1) & hash 就是java7 中的indexFor 的操作，判断数组当前位置是否已经为空，如果为空，就实例化一个node，将该node放入数组中这个索引位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//key 存在，就替换掉原有的value,与java 7 类似
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 {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//当单链表的长度大于等于TREEIFY_THRESHOLD - 1时，链表就转换成一棵红黑树了
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
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;
}
为什么HashMap 数组大小是2的幂次方
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
假如数组的长度为17，参与位运算值为length-1=16，对应的二进制为0000,....,0001,0000,此时任意一个数h与16 进行位运算，结果只有16,0两种结果，这意味着数组只有两个bucket，再有元素存放hashmap 时，必然会发生hash 冲突，导致hashmap 变成了两个单链表。
而假如数组长度为16，参与位运算的值为15，对应的二进制为0000,....,0000,1111，，此时任意一个数与15 位运算后，结果必然在[0,15]之间，这刚好对应着数组的下标索引。
这就是为什么hashmap 中数组的大小必须为2 的幂次方。
为什么 hashmap 会出现死循环
参考
疫苗：JAVA HASHMAP的死循环
JDK7与JDK8中HashMap的实现
How does a HashMap work in JAVA
(译)Java7/Java8中HashMap解析
网友评论