Java HashMap

1、HashMap的实现原理

JDK1.7：

基于Entry数组和链表实现，内部维护着一个数组table，该数组保存着每个链表的表头结点。

JDK1.8：

基于Node数组和链表（或者红黑树）实现。Node与Entry结构大体相同，只是Node有个导出类TreeNode子类，一个链表很容易被转换成树。

2、HashMap是如何遍历的

查找时，先通过hash函数计算key的hash值，再根据key的hash值计算数组索引（取余法），然后根据索引找到链表表头结点，然后遍历查找该链表（JDK1.8可能会是红黑树）。

3、HashMap key为null的情况

HashMap允许key为null，默认存在table[0]。

4、HashMap中新插入的数据在链表的什么位置

JDK1.7添加在链表的表头；JDK1.71.8添加在链表的表尾。

5、HashMap为什么是线程不安全的

//JDK1.7
public V put(K key, V value) {
    ...
    //插入新元素
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    ...
    createEntry(hash, key, value, bucketIndex);
}

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++;
}

Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

如果存在两个线程同时写入一个链表节点，从源码可知，有一个节点会写入无效。

6、HashMap在Java1.7与1.8中的区别

JDK1.7：

如果所有元素节点都在一个链表上，put/get的时间复杂度会退化到O(n)。

JDK1.8：

为了解决Hash Collision DoS攻击造成巨大的开销，即使所有元素节点都在一个链表上（由于引入了红黑树），时间复杂度最差只有O(log n)，但是需要key的对象正确的实现了Compare接口。