1.7

JDK 1.7采用数组 + 链表的数据结构，插入时使用头插法，多线程访问时可能出现死循环问题。

变量

// 默认初始容量为16，并且必须为2的n次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 数组的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 哈希表的加载因子，默认为0.75
final float loadFactor;

// 需要扩容的临界值，当哈希表的键值对等于threshold时，数组需要扩容
// 当 table EMPTY_TABLE，这个值为初始容量大小
int threshold;

// HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态  
static final Entry<?,?>[] EMPTY_TABLE = {};

// 用来存储数据的数组，默认为空数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

// 键值对的数量
transient int size;

构造函数

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, 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;
    threshold = initialCapacity;
    init(); // 这是个空方法
}

put操作

public V put(K key, V value) {
    // 如果table为空数组，则需要进行扩容
    if (table == EMPTY_TABLE) {
        // 此时的threshold为数组的容量大小
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value); // 存储key为null情况
    // 计算 Hash 值
    int hash = hash(key);
     // 使用 h & (length-1) 计算新增元素在数组的下标位置
    int i = indexFor(hash, table.length);
    // 遍历数组位置为i的链表
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 如果该 key 已被插入，则直接替换掉旧的value并返回旧值
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 运行到这里，说明这个key以前没有被插入过

    // 记录 HashMap 的数据结构发生了变化
    modCount++;
    // 在链表上新增节点
    addEntry(hash, key, value, i);
    return null;
}
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    // 计算出一个2的n次方的数，并且这个数需要大于等于toSize
    int capacity = roundUpToPowerOf2(toSize);
    // 计算扩容临界值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 实例化数组
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

addEntry

// 新增节点
// bucketIndex 为数组下标位置
// table[bucketIndex]则代表链表的 头指针
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 判断是否需要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 如果数量大于等于扩容的临界值并且链表不为空，则进行扩容
        // 新的数组长度为当前数组的两倍
        resize(2 * table.length);
        // 计算key的哈希值
        hash = (null != key) ? hash(key) : 0;
        // 计算新增元素应该保存在数组的哪个下标位置
        bucketIndex = indexFor(hash, table.length);
    }
    // 保存新增元素
    createEntry(hash, key, value, bucketIndex);
}

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];
    // 将旧数组复制到新数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 数组指向新数组
    table = newTable;
    // 重新计算扩容临界值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

transfer

将旧数组的数据复制到新数组中

void transfer(Entry[] newTable, boolean rehash) {
    // 新数组长度
    int newCapacity = newTable.length;
    // 遍历旧数组
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 计算元素 e 在新数组中的下标
            int i = indexFor(e.hash, newCapacity);
            // e.next 指向了链表头部
            e.next = newTable[i];
            // 链表头部指向 e
            newTable[i] = e;
            e = next;
        }
    }
}

createEntry

// 新增元素
// 使用的是头插法插入到链表头部
void createEntry(int hash, K key, V value, int bucketIndex) {
    // 获取链表的首部节点
    Entry<K,V> e = table[bucketIndex];
    // 链表头部指向新增元素
    // 将新增元素添加到链表头部
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    // 数量加1
    size++;
}

死循环原因

1.8

JDK 1.8采用数组 + 链表 + 红黑树的数据结构，插入时使用尾插法，不会出现死循环问题。

其中当链表的长度大于等于 8 时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表

变量

 // 初始容量为 16
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
 // 最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;
 // 负载因子默认值
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 // 桶上的链表长度大于等于8时，链表转化成红黑树
 static final int TREEIFY_THRESHOLD = 8;
 // 桶上的红黑树大小小于等于6时，红黑树转化成链表
 static final int UNTREEIFY_THRESHOLD = 6;
 // 当数组容量大于 64 时，链表才会转化成红黑树
 static final int MIN_TREEIFY_CAPACITY = 64;
 // 记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
 transient int modCount;
 // HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
 transient int size;
 // 存放数据的数组
 transient Node<K,V>[] table;
 // 扩容的门槛，有两种情况
 // 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方
 // 比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。
 // 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
 int threshold;
 // 链表的节点
 static class Node<K,V> implements Map.Entry<K,V> {
 // 红黑树的节点
 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

put操作

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;

    // 判断当 table 为 null 或者 tab 的长度为 0 时，即 table 尚未初始化，
    // 此时通过 resize() 方法得到初始化的 table
    n = (tab = resize()).length;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 此处通过（n - 1） & hash 计算出的值作为 tab 的下标 i，并令 p 表示 tab[i]，
    // 也就是该链表第一个节点的位置。并判断 p 是否为 null
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 当 p 为 null 时，表明 tab[i] 上没有任何元素，那么接下来就 new 第一个 Node 节点，
        // 调用 newNode 方法返回新节点赋值给 tab[i]
        tab[i] = newNode(hash, key, value, null);
    else {
        // 下面进入 p 不为 null 的情况，有三种情况：
        // p 为链表节点；
        // p 为红黑树节点；
        // p 是链表节点但长度为临界长度 TREEIFY_THRESHOLD，再插入任何元素就要变成红黑树了。

        HashMap.Node<K,V> e; K k;
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            // HashMap 中判断 key 相同的条件是 key 的 hash 相同，并且符合 equals 方法。
            // 这里判断了 p.key 是否和插入的 key 相等，如果相等，则将 p 的引用赋给 e
            e = p;
        else if (p instanceof HashMap.TreeNode)
            // 现在开始了第一种情况，p 是红黑树节点，那么肯定插入后仍然是红黑树节点，
            // 所以我们直接强制转型 p 后调用 TreeNode.putTreeVal 方法，返回的引用赋给 e
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 接下里就是 p 为链表节点的情形
            // 也就是上述说的另外两类情况：插入后还是链表 / 插入后转红黑树。
            // 另外，上行转型代码也说明了 TreeNode 是 Node 的一个子类

            // 开始遍历链表
            for (int binCount = 0; ; ++binCount) {
                // 我们需要一个计数器来计算当前链表的元素个数，并遍历链表，binCount 就是这个计数器
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 插入成功后，要判断是否需要转换为红黑树
                    // 因为插入后链表长度加 1，而 binCount 并不包含新节点
                    // 所以判断时要将临界阈值减 1
                    // TREEIFY_THRESHOLD 的大小为 8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 当新长度满足转换条件时，调用 treeifyBin 方法，将该链表转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // 链表遍历过程中，发现有元素和新增的元素相等，结束循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e不等于null，说明e的key与新增元素的key相等
        // 直接修改e的value为新增元素的value就可以了
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 记录 HashMap 的数据结构发生了变化
    ++modCount;

    // 如果 HashMap 的实际大小大于扩容的门槛，开始扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

线程不安全原因

多个线程同时进行put操作，并且这两个key刚好发生了碰撞，那么这两个元素会被添加到同一个位置。以JDK1.7为例，多个线程将会同时执行下面这行代码，这样就会导致有些数据被覆盖调了。

// 将新增元素添加到链表头部
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

本作品采用《CC 协议》，转载必须注明作者和本文链接