HashMap Java1.7源码

从

从源码最开头的注释我们可以看出1.7的HashMap是一个经典的哈希表数据结构的实现，数组+链表。但是不保证链表元素的顺序一直不变，这是1.7中HashMap使用出现问题的最大来源。

HashMap基本参数：初始大小16，最大大小2*31-1，负载因子0.75。size为map中放置Entry<key,value>的数量，threshold = 容量*负载因子，当size超过负载因子时，进行扩容。因此负载因子较大时，去给table数组扩容的可能性就会少，所以相对占用内存较少；负载因子较少的时候，给table数组扩容的可能性就高，那么内存空间占用就多，但是entry链上的元素就会相对较少，查出的时间也会减少。是一个空间/时间的选择。

我们这里来看HashMap最核心的put方法：

核心put方法

让我们看一下put方法做了什么，首先调用inflateTable方法，初始化Entry数组，数组的大小为：

Integer.highestOneBit((number -1) <<1)

即取超过threshold的最小的2次方，然后单独处理key为null的情况，最后对Entry数组的key位置上的链表进行遍历，如果找到相应的key就修改key位置上的value，否则addEntry添加节点，添加节点时先检查插入之后是否大小超过threshold，超过就resize()扩容，未超过就头插法插入一个链表节点。

为什么HashMap容量为2^n

默认的链表大小为16，链表初始化时的大小也是2^n，面试的时候面试官可能会问为什么？答案就是HashMap的数组下标计算方式：

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数组下表是将hash()&length-1得到的，这样如果length不是2^n倍，就会导致indexFor()得到的数组下标不是每一位都为1，导致HashMap数组中总有一些桶没有数据投入，增加HashMap的哈希碰撞。

Java1.7中HashMap并发情况死循环

死循环的过程发生在HashMap的重组过程中，HashMap在容量不够时，会新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。新建表的代码如下：

void resize(int newCapacity) {

    Entry[] oldTable =table;

    int oldCapacity = oldTable.length;

    if (oldCapacity ==MAXIMUM_CAPACITY) {

        threshold = Integer.MAX_VALUE;

        return;

    }

    Entry[] newTable =new Entry[newCapacity];

    transfer(newTable, initHashSeedAsNeeded(newCapacity));

    table = newTable;

    threshold = (int)Math.min(newCapacity *loadFactor,MAXIMUM_CAPACITY +1);

}

其中迁移的部分：

void transfer(Entry[] newTable,boolean rehash) {

int newCapacity = newTable.length;

for (Entry e :table) {

        while(null != e) {

            Entry next = e.next;

            if (rehash) {

                e.hash =null == e.key ?0 : hash(e.key);

            }

            int i =indexFor(e.hash, newCapacity);

            e.next = newTable[i];

            newTable[i] = e;

            e = next;

        }

    }

}

这里发生死循环的原因就在于HashMap的扩容过程中并不是按照原有顺序插入新的HashMap，而是运用头插法，在原有HashMap中靠前的节点在新的插入过程中会先被插入，头插法中会先把当前节点Node1的next节点Node2保存下来，下一步应该是把Node1.next置为这个key链表的头位置。如果此时在并发环境下，线程2进入单独开辟一块内存区域，将原有HashMap中的下一个节点Node2头插在了该节点之前，Node2指向Node1，Node2就成为了Node1.next的链表头位置，然后线程1继续进行，将next设置为Node2，就形成了循环链表。

这样在下一次对于这个key的查找过程中，会进入死循环。

https://coolshell.cn/articles/9606.html

Java8中HashMap的变化

在Java8中HashMap文件中实现了一个红黑树TreeSet

在put方法中，先检查当前key数组上有没有元素，如果没有就插入

if (p.hash == hash &&((k = p.key) == key || (key !=null && key.equals(k))))

然后检查是否为树

else if (pinstanceof TreeNode)

如果不是树，则链表长度达到8之后树化成为红黑树，如果没有达到就在链表尾插入节点

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;

}

为什么树化的长度判断是8？

注释中其实已经解释了这个问题，因为树化之后的节点大小为正常链表节点的两倍，所以应该尽量减少红黑树使用的场景。

在hash()均匀的情况下，按照默认的配置，即容量16，负载因子0.75。插入是红黑树长度遵循泊松分布，长度大于8时的概率只有百万分之一，所以将树化的threshold设为8

增加了replace(),merge()等方法

改变了扩容中重建HashMap链表的方法为顺序插入

虽然HashMap不是线程安全的，但是通过这个改进大大减少了并发情况下进入死循环的可能性

扩展阅读：

Hash Collision DoS

由于HashMap中的hash()函数是非随机的hash()方法，而且tomcat在POST请求中使用HashMap存储请求的参数，这样如果请求的参数是人为制造的有相同hash()结果的话，就会造成HashMap退化为链表，导致服务器宕机

对于这样的攻击手段我们有三种防御方法

    打补丁，把hash算法改了。

    限制POST的参数个数，限制POST的请求长度。

    最好还有防火墙检测异常的请求。

于是Tomcat在2012年(Java7)推出了补丁，默认限制POST最大参数数量为10000