HashMap整理

2017-09-29 本文已影响0人 huashu

一、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的死循环

参考

疫苗：JAVA HASHMAP的死循环
 JDK7与JDK8中HashMap的实现
 How does a HashMap work in JAVA
(译)Java7/Java8中HashMap解析