Talk is cheap , show me your code!
欢迎来到付振南Java博客,让我们一起学习Java吧!

Java集合之HashMap详解 HashMap的前生今世,一点一点剖析!

Java集合之HashMap详解

前面我们讲解了Collection接口里面的ListSet,现在我们再讲讲Map这个接口。
Map接口里面主要有我们非常非常非常非常常用的HashMap,和线程安全的ConcurrentHashMap,还有基于红黑树排序的TreeMap,保留插入记录顺序的LinkedHashMap,还有不常用的WeakHashMap,ConcurrentSkipListMap等。

Map和之前List和Set最大的不同就是,Set和List往里面存元素的时候是以对象的形式存进去的,而map的以映射Key-Value方式存进去的,Map的key是不可变的。

HashMap

我们先来讲一讲HashMap,因为HashMap真的太常用了,网上搜讲解HashMap的博客,教程多的数不胜数。

基本概念

HashMap是线程不安全的,是基于Key-Value的映射关系存储的键值对。在jdk1.7底层是数组+链表实现的,1.8开始是数组+链表/红黑树实现的,HashMap的默认初始容量是16,两倍扩容,负载因子是0.75,HashMap总是使用2的幂作为哈希表的大小。
HashMap结构图
HashMap中有一个东西叫做Node,简单解释就是哈希桶数组,每一对key-value都可以称作哈希桶数组,HashMap由很多个哈希桶数组组成,HashMap使用HashTable来存储数据的。
jdk1.8中Node的代码:

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

HashMap的构造函数

HashMap有无参构造函数和有参构造函数。
在你new HashMap的时候,如果你什么也不指定,就会默认调用无参的构造函数。

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

也就是说负载因子是默认的0.75,当你put第一个键值对进去的时候会给你扩容到16。

如果你在构造HashMap的时候只指定了容量大小,那么就会调用这个构造函数。

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

如果你既指定了初始容量大小,又指定了负载因子,就会调用这个构造函数。

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

前面我们说到,HashMap总是使用2的幂作为哈希表的大小,那么是怎么保证的呢?通过这个构造函数我们可以看到,loadFactor的值就是你指定的负载因子大小,但是初始容量大小会通过tableSizeFor这个方法加工一下,也正是这个方法实现了HashMap总是使用2的幂作为哈希表的大小。

我们来具体看一下这个方法是怎么实现的。

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

这个方法的作用就是找到大于等于initialCapacity的最小的2的幂(initialCapacity如果就是2的幂,则返回的还是这个数)。比如你指定初始容量为10,那么大于等于10的最小的2的幂就是16,返回的初始容量就是16。
首先将初始容量-1,然后经过五次右移然后或的操作之后在+1返回。这花里胡哨的操作相信大家都会看懵,没事,我们一点一点来剖析。

1.为什么要将初始容量-1呢?
这是因为当你指定的默认初始容量正好是2的幂的时候,经过后面五次右移操作之后,结果将会变成原来的2倍。
我们用8来试试。8的二进制表现形式是1000。

  • 第一次右移1位,0100,在和原来的1000做或操作,结果为1100;
  • 第二次右移2位,0011,或操作,1111;
  • 第三次右移4位,0000,或操作,1111;
  • 第四次右移8位,0000,或操作,1111;
  • 第五次右移16位,0000,或操作,1111;

我们看到结果已经变成了1111,再加上1,结果就是10000了,16,很明显最高位左移了一位,也就是结果已经是原来的二倍了。

2.五次右移+或操作,+1
这里我们用不是2的幂来试试,比如说10。
初始容量为10进行tableSizeFor操作
10的二进制表示为1001,经过-1和五次右移+或操作后在+1,结果为10000,也就是16,大于等于10的最小的2的幂正好也是16。

相信大家也看出来了,简单总结这个算法就是将传进来的初始容量不是2的幂的最高位左移一位,然后只需要这个最高位的值。如果传进来的已经是2的幂了,经过这些操作后返回的还是原来的值,我们再用之前的8来试试。
8的二进制表现形式为1000,-1之后为0111,

  • 第一次右移1位,0011,在和原来的0111做或操作,结果为0111;
  • 第二次右移2位,0001,或操作,0111;
  • 第三次右移4位,0001,或操作,0111;
  • 第四次右移8位,0001,或操作,0111;
  • 第五次右移16位,0001,或操作,0111;

我们看到结果还是0111,再加上1,结果还是1000了,8,所以当传进来的已经是2的幂了,经过这些操作后返回的还是原来的值。

那么为什么右移到16就结束了?因为哈希表的容量为42亿多,也就是2的32次,最后一次右移16位,高位的16位右移到低位的16位,已经需要32位了,所以已经够了,不需要再往后继续右移操作了。

HashMap是如何计算数组下标索引的?

不论我们通过哪种构造函数创建HashMap的时候,当我们往HashMap里put内容的时候,是怎么找到要存放的位置的呢?

首先根据put的key调用HashCode方法得到HashCode值,然后通过Hash算法得到Hash值,最后通过Hash&(length-1)这个操作找到哈希桶数组下标索引值。
我们看看1.7和1.8版本的Hash算法。
1.7Hash算法

        static int hash(int h) {
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

扰动了4次,花里胡哨,性能稍差。
我们再看看1.8的Hash算法

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

我们明显看到1.8的Hash简化多了,而且性能会有所提升。

我们来详细讲讲这个Hash算法。
key调用HashCode方法得到HashCode值,然后异或哈希码右移16的结果,换个思路说就是高16位和低16位进行异或操作。

那么为什么要这么干呢?这个Hash算法为什么这么设计?
我们先来用默认容量16来演示一下这个Hash算法。

[]

因为哈希表的大小总是2的幂,所以Hash&(length-1)这个操作永远只与Hash值的低几位有关,很容易产生哈希冲突,所以将HashCode的高16位右移到低16位,将高16位和低16位都参与操作,减小哈希冲突的影响。

HashMap的长度为什么总是2的幂?

前面我们说了,Hash值的范围是2的-31次到2的31次+1,42多亿数据,只要设计一个良好的Hash算法,让映射的比较松散,分配均匀,这样的话产生冲突的概率就会大大降低。但是这么庞大的数据根本没有这么多内存来存放,所以哈希表有一个计算数组下标的方法Hash&(length-1)来存放这个值,当长度为2的幂的时候Hash&(length-1)也就等于Hash%length,但是&比%具有更高的效率,因为%在计算机底层本质上是一直做除法,所以这也就解释了为什么HashMap的长度为什么总是2的幂了。

1.7与1.8 HashMap的put方法与扩容机制

我们都知道,在1.7中,HashMap是通过数组+链表实现的,当put的内容超过容量之后会进行扩容操作,这是put的执行过程。
put

1.7的put方法,扩容机制以及造成死锁的原因

我们在来看看1.7的put方法。

public V put(K key, V value)
{
    ......
    //算Hash值
    int hash = hash(key.hashCode());
    //计算数组下标索引
    int i = indexFor(hash, table.length);
    //如果该key已被插入,则替换掉旧的value (链接操作)
    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))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //该key不存在,需要增加一个结点
    addEntry(hash, key, value, i);
    return null;
}

我们再来看看addEntry方法,

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //查看当前的size是否超过了我们设定的阈值threshold,如果超过,需要resize
    if (size++ >= threshold)
        resize(2 * table.length);
} 

当add元素的时候size已经超过了阈值,就要调用resize方法进行2倍扩容了,我们来看看resize方法,

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //创建一个新的Hash Table
    Entry[] newTable = new Entry[newCapacity];
    //将Old Hash Table上的数据迁移到New Hash Table上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

就是创建一个新的哈希表,将旧的哈希表通过transfer方法迁移到新的哈希表中,并计算出新的阈值,我们看看transfer方法到底是怎么迁移的,

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是:
    //  从OldTable里摘一个元素出来,然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
} 

通过这个transfer方法我们可以看出来他是从旧的哈希表中通过for循环一个一个把元素用头插法迁移过去的,正是因为这个头插法不能保证原有的顺序,会导致在多线程环境下形成一个环形链表,从而造成死锁!!!关于1.7版本的HashMap造成死锁的具体原因分析大家可以看coolshell的这篇文章,讲的是非常好!

HashMap 1.7潜在的安全隐患

String的HashCode方法是公开的,如果有人通过精心构造大量的的hashcode相同字符串使哈希表每次都产生碰撞,该数组解决哈希碰撞的链表就会非常长,以至于最后会退化成链表,链表的查询速度是很低的,这样就会能造成hash碰撞攻击,消耗大量CPU资源,导致系统无法快速响应请求,从而达到拒绝服务攻击(DoS)的目的。
比如Tomcat Oracle 等都是使用HashMap进行http请求储存的,当时tomcat就公开了一封邮件说明这个潜在的安全隐患并提供了临时的补丁。

1.8HashMap的改进

在1.8的版本中,HashMap的改进我们主要讲由原来的数组+链表升级为数组+链表/红黑树,还有扩容插入顺序由原来的头插法改成了尾插法

数组+链表/红黑树

当数组长度达到64且链表长度达到8的时候会将链表转化成红黑树。
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
为什么是链表到8才转化成红黑树呢?
因为他服从了参数为0.5的泊松分布,当为8的时候,产生碰撞的概率为千万分之6,非常小了。

     * 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

扩容插入顺序

我们先来看看1.8之后的put方法,真硬核!

 /**
     * 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;
    }

直接逐行读代码可能会很吃力,这需要结合上面的那张put执行流程来看会更好的理解。我们直接看resize扩容方法吧。

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        ...
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                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 { // preserve order
                        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 {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

这里我们主要看一下他注释的那个// preserve order,保持顺序,因为1.7扩容之后的插入是头插法,没有保持顺序,所以才会引发后面的一序列问题,1.8特意强调了保持了顺序。

因为扩容是2倍扩容,元素在重新计算hash之后在高位上多了个1,低位保持不变,比如原先某个元素数组索引值是0101,扩容之后变成了10101,换句话说经过扩容后,高位要么是1,要么是0,所以我们不需要重新计算每一个桶的哈希值,只需要判断多的那个高位是0还是1就行了,0说明扩容后索引位置没有改变,1说明改变了,变成了原来的索引+oldCapcity。

我们可以看到上面的代码,由原来的头插法改为了尾插法,同时将高位和低位赋值给了newTable,实现了保持顺序的扩容。

不过最后还是要说一句,虽然1.8版本的HashMap解决了1.7的死锁和安全隐患问题,但毕竟还是非线程安全的,在多线程的环境下还是得用ConrrentHashMap。

参考资料

Java 8系列之重新认识HashMap
Java 7/8 HashMap源码详解与面试题分析
疫苗:JAVA HASHMAP的死循环

赞(6) 打赏
未经允许不得转载:付振南Java博客 » Java集合之HashMap详解

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏