阅读 10058

HashMap原理技术知识整理

HashMap涉及的技术点非常多,典型的数据结构和算法有机结合,JDK对HashMap优化变化中不断权衡时间复杂和空间复杂度。

一. 存储结构

1.JDK1.8之前 HashMap = 数组(O(1))+ 单向链表(O(n))

2.JDK1.8之后 HashMap = 数组(O(1))+ 单向链表(O(n))+ 红黑树(O(log n)

HashMap结构图.png
关于结构的几个关键数字:

1.默认初始化数组容量大小是16。

2.数组扩容刚好是2的次幂。

3.默认的加载因子是0.75。

4.链表长度超过8时将链表转化成红黑树结构。 5.红黑树节点数减少到6的时候退化成链表。

以上几个数字关系,又为什么是上边的几个数字接下来一个个分析。

二. 操作原理

1. put储存流程

①计算桶的位置,根据key的hashcode求出hash值,位置index = hash%length。

②判断是否达到扩容条件,threshold=DEFAULT_INITIAL_CAPACITY * loadFactor(16*0.75=12)大于这个阀门值就需要扩容,否则下一步。

③判断桶位置是否为空,如果为空直接在数据插入数据。如果不为空,下一步。

④判断是链表还是红黑树,链表是否到达转化红黑树,当前链表节点数<=8,插入节点;如果是红黑树插入节点,否则下一步。

⑤链表转化成红黑树,插入节点。

⑥插入节点后计算当前size是否需要扩容,如果大于阀门值需要扩容resize。

/**
 * 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;
    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 {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    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;
}
复制代码

以上是JDK1.8的HashMap的get调用关键方法源码。

2. get获取过程

①计算桶的位置,根据key的hashcode求出hash值,位置index = hash%length。

②无论是数值,链表还是红黑树,for循环判断hash值冲突就比对key是否相等,相等就返回对应的value。

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final 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) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)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;
}
复制代码

以上是JDK1.8的HashMap的put调用关键方法源码。

三. 数据结构和算法思考

1.为什么选择数组和链表结构?

①数组内存连续块分配,效率体现查询更快。HashMap中用作查找数组桶的位置,利用元素的key的hash值对数组长度取模得到。

②链表效率体现增加和删除。HashMap中链表是用来解决hash冲突,增删空间消耗平衡。

扩展: 为什么不是ArrayList而是使用Node<K,V>[] tab?因为ArrayList的扩容机制是1.5倍扩容,而HashMap扩容是2的次幂。

2.为什么扩容是2次幂,根据key的hashcode再求hash值?
①key的hash值计算
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码

代码意思是hash = hashcode的高16位异化低16位,而不是直接hashcode。

②计算桶的位置代码
index = (n - 1) & hash
复制代码

思想:

一是,为了减少hash冲突使用hash%length计算,求模计算保证了得到的结果一定在0-length范围之内。

二是,为了提高运算速度,模运算比不上位运算,当n是2的次幂才满足hash%length == (n-1)&hash。

确定公式中(n-1)符合最优等式,剩下考虑hash值的最优,hash值这个因子考虑影响结果尽可能不冲突。

因为计算速度体现在位运算上,条件n是2的次幂,那么n-1的换算成二进制前边都是连续的0,后边都是连续的1,。比如n=16,则n-1=15,15的二进制1111。hash & 1111 = 只要关注的hash的二进制的最后四位数进行&运算。

(n-1)& length.png
如上图,最终会与15的二进制进行1111四位运算,如果与key.hashcode进行与运算的话,只要key的hashcode最后四位为0000前边无论是什么都没关系,这样出现相同值的概率高很多。所以,引入hashcode先高低16位进行异或运算,减少hash冲突。

扩展: hashcode与equals相等判断对比: 两个key的hashcode相等,key不一定equals。 两个key的equals,hashcode一定相等。

3.为什么加载因子为0.75,链表长度大于8转成红黑树?

思想:

上边问题不是两个独立问题而是相互相关,目的尽量减少冲突前提提高空间利用率和减少查询成本的折中。

加载因子决定了HashMap的扩容的阀门值,如果桶是16,那么扩容值16* 0.75=12,也就是12的时候就要考虑扩容,还有4个没有被利用到,牺牲的空间。如果加载因子是1,空间利用率高,但是查询速度变慢。

原理:

权衡依据是以上情况符合泊松分布(一种统计与概率学里常见到的离散概率分布,适合于描述单位时间(或空间)内随机事件发生的次数),用0.75作为加载因子,每个碰撞位置的链表长度超过8个概率非常低,少于千万分之一。

源码说明:

 * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 *
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million 
复制代码

扩展:

为什么不一开始选择红黑树?

红黑树近乎于平衡二叉树,结构适合均匀分布节点,减少树的深度像链表长度情况。原因主要是插入效率上,红黑树增加节点很可能需要进行左旋,右旋,着色操作,这些时间效率并没有链表形式高。

4.HashMap的key选择

1)选择不可变的对象,比如字符串或int类型。

2)如果要用一个自定义实体类作为key:

①类添加final修饰符,保证类不被继承。

②保证所有成员变量必须私有,并且加上final修饰。

③不提供改变成员变量的方法,包括setter。

④通过构造器初始化所有成员,进行深拷贝(deep copy)。

5.String类中的hashcode计算
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
    char val[] = value;
        for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
}
复制代码

哈希计算公式:s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]

四. 横向扩展

1.HashMap出现线程问题

①多线程扩容,引起的死循环问题(jdk1.8中,死循环问题已经解决)。

②多线程put的时候可能导致元素丢失。

③put非null元素后get出来的却是null。

2.使用线程安全Map

①HashMap并不是线程安全,要实现线程安全可以用Collections.synchronizedMap(m)获取一个线程安全的HashMap。

②CurrentHashMap和HashTable是线程安全的。CurrentHashMap使用分段锁技术,要操作节点先获取段锁,在修改节点。

3.Android提倡使用ArrayMap

①ArrayMap数据结构是两个数组,一个存放hash值,另一个存放key和value。

②根据key的hash值利用二分查找在hash数组中找出index。

③根据index在key-value数组中对应位置查找,如果不相等认为冲突了,会以key为中心,分别上下展开,逐一查找。

优势,数据量少时(少于1000)相比HashMap更节省内存。劣势,删除和插入时效率要比HashMap要低。

关注下面的标签,发现更多相似文章
评论