HashMap的变化

文章目录

1、JDK1.7
- 1.1、HashMap源码
- 1.2、链表循环的原因
2、JDK1.8
- 2.1、结构变化

1、JDK1.7

HashMap的结构为：数组+链表
采用头插法，发生碰撞的时候，新元素指向旧元素。
存在的问题：链表循环。

1.1、HashMap源码

put()方法：

public V put(K key, V value) {
    //第一次向map中添加元素
    if (table == EMPTY_TABLE) {
        //初始化
        inflateTable(threshold);
    }
    //如果key为null，存储位置为table[0]或table[0]的冲突链上
    if (key == null)
        //保存null值，放入链表首位
        return putForNullKey(value);
    //将key计算hash值，尽量散列均匀分布
    int hash = hash(key);
    //计算key的位置,保证下标不会越界
    int i = indexFor(hash, table.length);
    //hash冲突解决
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        //判断hash和equals
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            ;//调用value的回调函数，其实这个函数也为空实现
            e.recordAccess(this);
            return oldValue;
        }
    }
    //保证并发访问时，若HashMap内部结构发生变化，快速响应失败
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

addEntry():

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

resize():

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];
        //将旧的集合放入新的集合，会重新计算hash值
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

transfer():

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

负载因子是0.75，初始容量是12，扩容的阈值就是12。

1.2、链表循环的原因

在上面已经知道了HashMap在放入元素会经过put()、addEntry()、以及扩容的时候resize()、transfer()方法。问题其实就是处在transfer()方法上。
假设现在HashMap的大小为2，放入的元素为3,5,7，都冲突在了数组下标1的位置，然后Hash表扩容。这是单线程的情况。
假设有两个线程呢？
当线程1执行到do-while语句第一句的时候就被调度挂起，那么情况如图：

那么这里意思就是：线程1还没有完全扩容，但是e和next都已经指向了线程2正常扩容的了。
当线程1重新被调度回来执行的时候：
1. newTalbe[i] = e;，此时线程1的HashMap数组下标3的位置指向了Key(3)。
2. e=next;，此时e指向了Key(7)
3. 而下次循环的next=e.next;，就导致了next指向了Key(3)
4. 继续执行newTable[i] = e;，那么情况如下图，接着e和next接着下移
5. 此时Key(7).next=Key(3)，而此时e指向了Key(3)，继续执行newTable[i] = e;，那么Key(3).next=Key(7)，循环出现了。
6. 线程2生成的e和next的关系影响到了线程1的情况。从而打乱了正常的e和next的链。于是，当我们的线程一调用到，HashTable.get(11)时，即又到了3这个位置，需要插入新的，那这会就e 和next就乱了。

2、JDK1.8 2.1、结构变化

结构变为了数组+链表+红黑树。
具体触发条件为：某个链表的个数大于8，并且数组的大小大于64的时候，那么会把原来的链表转换成红黑树。
为什么会是红黑树？
1. 红黑树的查询、删除和添加时间复杂度是 O ( l o g 2 n ) O(log_2n) O(log2n)
2. 链表的查询和删除的时间复杂度为 O ( n ) O(n) O(n)，插入为： O ( 1 ) O(1) O(1)
为什么是红黑树而不是AVL平衡树？
1. 红黑树和AVL树都是常见的平衡二叉树，它们的查找，删除，修改的时间复杂度都是 O ( l o g n ) O(log n) O(logn)
2. AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树
3. 红黑树更适合插入修改密集型任务
4. 两个都是O(logN)查找，但是平衡二叉树可能需要 $O(logN$)旋转，而红黑树需要最多两次旋转使其达到平衡（尽可能需要检查O(logN)节点以确定旋转的位置），旋转本身是O(1)操作，因为只需要移动指针。
由头插法改为了尾插法。

HashMap的变化

Java相关栏目本月热门文章