1.底层结构

Java 7及之前版本

在Java 7及之前的版本中，HashMap的底层数据结构主要是
数组加链表
。具体实现如下：

  1. 数组
    ：HashMap的核心是一个Entry数组（
    Entry<K,V>[] table
    ），这个数组的大小总是2的幂。每个数组元素是一个单一的Entry节点，或者是一个链表的头节点。

  1. 链表
    ：当两个或更多的键经过哈希运算后映射到数组的同一个索引上时，就会形成链表。Entry节点包含了键值对以及指向下一个Entry的引用，以此来解决哈希冲突。

Java 8及之后版本

从Java 8开始，HashMap的底层结构除了
数组加链表
之外，还引入了
红黑树
，以优化在链表过长时的查找性能。结构变为
数组加链表加红黑树
：

  1. 数组
    ：同样是一个Entry数组（Java 8中称为Node），大小仍然是2的幂，用于快速定位。
  2. 链表
    ：在哈希冲突时，键值对仍会以链表形式链接在一起。但与Java 7不同的是，Java 8对链表的处理增加了转换为红黑树的条件。
  3. 红黑树
    ：当一个桶中的链表长度超过8且HashMap的容量大于64时（不大于64会先对数组进行扩容
    resize()
    ），链表会被转换成红黑树。这种转换提高了在大量哈希冲突情况下的查找效率，因为红黑树的查找时间复杂度为O(log n)，相较于链表的O(n)有显著提升。

2.数据插入

在JDK1.7的时候，采用的是头插法

在JDK1.8改成了尾插法，这是因为
头插法在多线程环境下扩容时可能会产生循环链表问题

线程不安全

无论是JDK1.7还是1.8都是线程不安全的
，下图是1.8中的put方法

tab是就是HashMap的数组table，第一个if判断时做了赋值。框起来的部分表示如果没有hash冲突就直接在数组上插入元素，但是如果两个线程hash一样且都进入到了这个if下，线程1先执行的插入数据，线程2会覆盖1插入的数据。

那么什么是循环链表问题呢？这就不得不介绍一下HashMap的扩容机制了。

3.扩容机制

首先讲几个HashMap的属性

  • table：数组，存放链表或红黑树的
    头节点
  • Node：节点，属性有hash、key、value、next（下一个节点）
  • size：元素个数，即节点node个数，非数组长度
  • Capacity：当前数组长度
  • loadFactor：加载因子，默认为0.75f，简称loadFactor
  • threshold：扩容门槛，值为capacity*loadFactor，size达到这个门槛就扩容

当size大于threshold时，就会进行扩容
resize()
。

扩容分为两步

  1. 创建一个新的数组，长度为原数组的两倍
  2. 遍历所有Node节点，重新计算index值（Java8首先会重新计算hash值），放到新数组里，存在hash冲突的就放到链表或红黑树

为什么要重新计算index值，直接把张三这条链表复制到新的数组中不行吗？

答案是不行的，因为index规则是根据数组长度来的，如图

所以index 的计算公式是这样的：

  • index = HashCode(key) & (Length - 1)

4.循环链表问题

循环链表问题理解起来比较麻烦，如果理解不了就知道JDK1.7HashMap扩容的时候有这么回事就行。但是可能是我自己太笨了万一大家一看就懂了呢

我们来看一下Java1.7扩容的源码

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);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    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方法，作用是重新计算index值然后将旧数组中的数据迁移到新数组

循环链表的产生：

原因：

假设我们有两个Thread都在执行resize方法，Thread1第一步刚执行完第23行
Entry<K,V> next = e.next;
就卡住了，这时Thread2执行完了resize方法。

过程：

  1. Thread1第一次执行完Entry<K,V> next = e.next后，e=张三，next=李四，也就是说第二步执行李四的插入
  2. Thread2执行完resize后，李四的next变成了张三
  3. 此时又回到Thread1，第二次执行Entry<K,V> next = e.next后，e=李四，next=张三，也就是说又要执行张三的插入，循环链表产生！

由此我们知道了循环链表产生的关键在于头部插入元素A时，元素A的next元素B的next是元素A本身，所以Java8采用了尾插法，避免了循环链表。

求赞！求关注！！以后会更新更多有用的内容！！！꒰⑅•ᴗ•⑅꒱

保佑大家代码永无bug ╰(
´︶`
)╯

标签: none

添加新评论