乐趣区

关于java:HashMap源码解析

jiezi

我的所有原创 Android 常识体系, 已打包整顿到 GitHub. 致力打造一系列适宜初中高级工程师可能看得懂的优质文章, 欢送 star~

1. 存储构造

1.1 JDK 1.7

外部是以数组的模式存储了 Entry 对象, 而每个 Entry 对象外面有 key 和 value 用来存值. 它外面蕴含了 key、value、next、hash 四个字段, 其中 next 字段是用来援用下一个 Entry 的(雷同的 hash 值会被放入同一个链表中). 数组中的每个地位都是一条单链表(也能够称之为桶), 数组中的元素的表头. 解决抵触的形式是拉链法, 同一条单链表中的 Entry 的 hash 值是雷同的.

transient Entry<K,V>[] table;

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
}

1.2 JDK 1.8

存储构造也是数组, 只不过将 Entry 换了个名字叫 Node.1.7 中 hash 值雷同的是放单链表中,1.8 也是, 当这个单链表的长度超过 8 时, 会转换成红黑树, 减少查找效率.

2. 基本概念

2.1 负载因子和阈值

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap 的默认大小是 16, 默认负载因子是 0.75, 意思是当存的元素个数超过 16*0.75 时就要对数组扩容, 这里的阈值就是16*0.75=12. 负载因子就是用来管制什么时候进行扩容的.

阈值 = 以后数组长度 * 负载因子

每次扩容之后都得从新计算阈值. 默认的数组长度是 16, 默认的负载因子是 0.75 这些都是有考究的. 在元素个数达到数组的 75% 时进行扩容是一个比拟折中的临界点, 如果定高了的话 hash 抵触就很重大, 桶就会很深, 查找起来比较慢, 定低了又节约空间. 个别状况下, 还是不会去定制这个负载因子.

ps: 到底是 阀值 还是 阈值, 傻傻分不清,,,, 知乎上有个对于这个问题的探讨 –「阀值」是否为「阈值」的误笔？

2.2 拉链法工作原理

每次新存入一个新的键值对时, 首先计算 Entry 的 hashCode, 用 hashCode% 数组长度失去所在桶下标, 而后在桶内顺次查找是否已存在该元素, 存在则更新, 不存在则插入到桶的头部.

3. 源码剖析

3.1 JDK 1.7

有了下面的根底概念, 上面开始看源码学习

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    // 默认初始容量, 必须是 2 的幂   这里的值是 16
    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;
    // 默认的空数组
    static final Entry<?,?>[] EMPTY_TABLE = {};
    // 用来盛放实在数据的数组
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    // 以后 HashMap 的实在键值对数量
    transient int size;
    // 阈值 = 数组长度 * 负载因子
    int threshold;
    // 负载因子
    final float loadFactor;
    // 标识对该 HashMap 进行构造批改的次数, 构造批改是指增删改或其余批改其内部结构 (例如 rehash) 的次数.
    // 用于迭代器疾速失败.
    transient int modCount;
    
    public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    
    public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    // 能够同时制订数组大小和负载因子
    public HashMap(int initialCapacity, float loadFactor) {
        ...// 省略局部逻辑判断
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        ...
        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        ...
    }
    
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
    }
    
}

3.1.1 put

下面是 HashMap 的一些根本属性, 都是绝对比拟重要的. 接着咱们来看一下增加元素 put 办法的实现, 以下是 JDK 1.7 的 put 代码

public V put(K key, V value) {//1. 数组为空 -> 初始化 (创立) 数组
    if (table == EMPTY_TABLE) {inflateTable(threshold);
    }
    //2. key 为 null, 独自解决
    if (key == null)
        return putForNullKey(value);
    //3. 计算 hash 值
    int hash = hash(key);
    //4. 计算该 hash 值该寄存在数组的哪个索引处
    int i = indexFor(hash, table.length);
    //5. 遍历链表(数组的每个元素都是单链表的表头)  查找链表中是否已存在雷同的 key  如果有, 则替换掉
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    //6. 增加元素到数组中
    addEntry(hash, key, value, i);
    return null;
}
3.1.1.1 inflateTable 数组初始化

简简单单几句代码波及的货色缺特地多, 咱们一一来解读一下. 首先是初始化数组 inflateTable 办法, 传入的是阈值.

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

//Integer.highestOneBit
public static int highestOneBit(int var0) {
    // 求掩码
    var0 |= var0 >> 1;
    var0 |= var0 >> 2;
    var0 |= var0 >> 4;
    var0 |= var0 >> 8;
    var0 |= var0 >> 16; 
    
    //>>>：无符号右移。无论是负数还是正数，高位统统补 0.  这里减了之后只剩下最高位为 1
    return var0 - (var0 >>> 1);
}

roundUpToPowerOf2 办法是为了求一个比 number 大一点的 2 的幂次方的数, 这里的代码看起来有点迷. 它最初会求出数组应该初始化的长度, 它能够主动将传入的容量转换为 2 的 n 次方.

Integer.highestOneBit 是取传入的这个数的二进制模式最右边的最高一位且高位前面全副补零, 最初返回 int 类型的后果. 比方传入的是 7(0111), 则最初失去的是 4(0100). 它这里先将 number-1, 而后再左移一位, 比方 number 是 9, 则 number- 1 等于 8(1000), 左移一位等于 10000 就是 16. 这样最初它就将传入的容量转换为了 2 的 n 次方.

计算好了容量之后, 计算阈值, 而后初始化数组.

3.1.1.2 putForNullKey 增加 null key

用了一个专门的办法用来操作 key 为 null 的状况

/**
 * Offloaded version of put for null keys
 */
private V putForNullKey(V value) {for (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

将元素寄存到了数组的第一个地位. 第一个地位也是一个桶, 这桶外面只有一个元素的 key 能够是 null, 其余元素都是被 hash 算法调配到这里来的.

3.1.1.3 计算 hash 值
/**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

获取到了 key 的 hashCode 之后, 又进行了一些骚操作, 这里的 hash 算法设计得很神, 这里的 hash 算法设计得好的话, 则会大大减少 hash 抵触.

3.1.1.4 indexFor 计算元素在数组中的索引
 /**
 * Returns index for hash code h.
 */
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);
}

用 hash 值按位与数组长度 -1, 相当于 h % length.& 运算比 % 效率高, 所以这里是 & 运算来进行. 为什么h & (length-1) = h % length ? 这其实与 length 无关,length 下面说过, 必须是 2 的幂. 咱们简略举个例子,h=2,length=8.

h & (length-1)
= 00000010 & 00000111
= 00000010

下面的最初后果是 2 , 2 % 8 的确是等于 2, 验证结束.

3.1.1.5 addEntry 增加元素到数组中

增加元素的时候可能之前这个地位是空桶, 也可能之前这里的桶曾经有元素存在了(hash 抵触了).

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {//1. 键值对数量超过阈值 && 该索引处数组不为空(阐明这里之前曾经存在元素)
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容 -> 原来的 2 倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    //2. 创立 Entry 节点
    createEntry(hash, key, value, bucketIndex);
}

// 创立新的节点  
void createEntry(int hash, K key, V value, int bucketIndex) {//table[bucketIndex] 是放到新插入节点的前面,, 所以这里是头插法
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

键值对超过阈值就会扩容

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<K,V> e : table) {
        // 元素非空 则转移
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 依据该节点 hash 值计算一下该节点该放到新数组的哪个索引处
            int i = indexFor(e.hash, newCapacity);
            // 将桶内元素一一转移到新的数组的新的索引处
            // 留神: 这里桶内程序会倒过去.
            // 比方桶内是 1 ->2->3   转移数据之后就是 3 ->2->1
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

扩容之后就波及到数据的迁徙, 迁徙的时候须要从新计算节点在新数组中的地位, 迁徙实现还得更新一下阈值.

JDK 1.7 中的 put 操作就是这些啦, 货色还挺多的. 最外围的也就是 put 局部的代码,get 的话比较简单这里就不做剖析了.

3.2 JDK 1.8

基本上思路是差不多的, 也是用数组 + 链表 (or 红黑树) 来装数据.

transient Node<K,V>[] table;

// 链表长度超过 8 且数组长度大于 64, 则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;

// 在 1.8 中节点改名字了.. 改成了 Node
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

来看看它的 put 办法是怎么实现的

3.2.1 put

1.8 的 put 办法略微比 1.7 的看起来简单些, 然而不必怕, 咱们一句一句的剖析

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

/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;

    //1. table 为空表时, 创立数组 初始化.  resize 既是初始化也是扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //2. 依据 hash 和数组长度求出元素应该在数组中的索引地位, 如果此处为空则将节点放到这里
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //3. 该索引处曾经有节点存在且 hash 值和 key 都相等(须要替换 value), 则记录下该索引处的节点援用
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //4. 如果该索引处是红黑树, 则将节点插入到树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //5. 该索引处是链表
        else {
            //5.1 顺次遍历链表
            for (int binCount = 0; ; ++binCount) {
                //5.2 找到链表尾部, 将节点插入到尾部
                if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                    // 如果链表长度超过 8, 则转换成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //5.3 找到 key 相等的了, 则完结 for 循环, 已在链表中找到须要替换 value 的节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //6. 替换原来的值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //7. 超过阈值, 则扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

正文写得比拟具体, 这里与 1.7 的区别还是挺大的.

  • Java7 中将节点插入链表是头插法, 而 Java8 是尾插法
  • Java8 中链表超过 8 且数组长度大于 64 则会将链表树化
  • Java7 将 key 为 null 的独自解决,Java8 没有独自解决(尽管它们的 hash 都是 0, 都是放数组第 0 处)

3.2.1.1 resize 扩容

首先来关注外围代码, 扩容.

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
    // 老数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    // 新数组长度  新阈值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 老数组长度大于 MAXIMUM_CAPACITY, 则将阈值设置成 Integer.MAX_VALUE  不扩容了..
        // 个别状况下, 不会走到这个逻辑分支外面去
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //1. 扩容: 将数组长度 *2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值也是 *2
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //2. 初始化数组
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        //3. 遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {oldTab[j] = null;
                //3.1 该索引处 桶内只有一个元素, 依据该节点的 hash 和新数组长度求出该节点在新数组中的地位, 而后搁置到新数组中
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //3.2 该索引处为红黑树  独自解决
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //3.3 该索引处为单链表(链表长度小于 8)
                else { // preserve order
                    // 不必移动地位的链表,hash 值 & 老数组长度为 0,loHead 为头部,loTail 为尾部
                    Node<K,V> loHead = null, loTail = null;
                    // 须要移动地位的链表,hash 值 & 老数组长度为 1,hiHead 为头部,hiTail 为尾部
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //hash 值 & 老数组长度
                        // 其实就是求最高位是 0 还是 1, 是 0 则放弃原地位不动; 是 1 则须要挪动到 j + oldCap 处
                        // 每条链表都被扩散成 2 条, 更扩散
                        if ((e.hash & oldCap) == 0) {if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 这些元素还是在老索引处
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 这些元素挪动到了 老索引地位 +oldCap  处
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize 的货色比拟杂, 即蕴含了初始化数组, 也蕴含了扩容的逻辑. 初始化数组比较简单, 咱间接看一下扩容局部逻辑. 首先是遍历原数组, 此时原数组的每个索引处可能存在 3 种状况

  1. 该索引处桶内只有一个元素 -> 依据该节点的 hash 和新数组长度求出该节点在新数组中的地位, 而后搁置到新数组中
  2. 该索引处为红黑树 -> 独自解决
  3. 该索引处链表长度大于 1, 小于 8

第 3 种状况比较复杂, 这里独自剖析一下.

剖析前咱们来看个货色, 假如数组长度 n =16, 那么依据 put 局部的代码, 存入数组时索引是(16 - 1) & hash, 这里有 2 个元素 key1 和 key2, 它们的 hash 值别离为 5 和 21. 上面是它们的计算过程

key1:
00001111 & 00000101 = 5

key2:
00001111 & 00010101 = 5

当数组扩容,n=32

key1:
00011111 & 00000101 = 00101 = 5

key2:
00011111 & 00010101 = 10101 = 5 + 16 = 21

扩容后 n - 1 比以前多了 1 个 1, 这样会导致按位与的时候 key2 的地位变成了原地位 +16 的地位. 因为咱们应用的是 2 次幂的扩大, 所以元素的地位要么在原地位, 要么在原地位 + 2 次幂的地位.

有了下面的剖析之后, 再回到咱们 3.3 处的逻辑

if ((e.hash & oldCap) == 0) {if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
} else {if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}

e.hash & oldCap: 用元素 hash 值与上老数组长度, 假如之前数组长度是 16, 那么这里就是按位与 10000, 而平时 put 的时候算索引是按位与(n-1) 也就是1111. 扩容之后, 在 put 的时候就得按位与11111. 因而它这里只是想看看 hash 值新增的那个 bit 是 1 还是 0. 如果是 0 则保留老地位, 是 1 的话则在老地位的根底上加老数组长度才是新的地位.

为什么要这么干? 次要是计算简略, 不须要像 JDK 1.7 那样还须要从新计算 hash. 还有就是让元素更扩散. 原本原来是一条链上的, 当初在 2 条链上 (不同的数组索引处) 了, 查找更快了.

须要留神的一个小点就是, 这里是尾插法且还是原来的程序, 而 JDK 1.7 是头插法且程序与想来相同.

扩容的内容大略就是这些, 略微有点多.

4. 相干知识点

4.1 HashMap 1.7 和 1.8 区别

  1. JDK1.7 用的是头插法,JDK1.8 及置换是尾插法. 且 1.7 插入时候程序是与原来相同的, 而 1.8 则还是原来的程序
  2. JDK1.7 是数组 + 链表,JDK1.8 是数组 + 链表 + 红黑树
  3. JDK1.7 在插入数据之前进行扩容,JDK1.8 是插入数据之后才扩容
  4. JDK1.7 是 Entry 来示意节点, 而 JDK1.8 是 Node
  5. JDK1.7 扩容和后存储地位是用 hash & (length-1) 计算来的, 而 JDK1.8 只须要判断 hash 值新增参加运算的位是 0 还是 1 就能疾速计算出扩容后该放在原地位, 还是须要放在 原地位 + 扩容的大小值 .
  6. 计算 hash 值的时候,JDK1.7 用了 9 次扰动解决, 而 JDK1.8 是 2 次

ps: 红黑树查找元素, 须要 O（logn）的开销

4.2 Hashtable 与 HashMap 的区别

  1. Hashtable 不反对 null 键和值
  2. Hashtable 应用 synchronized 来进行同步(有性能开销)
  3. Hashtable 的迭代器是 fail-fast 迭代器
  4. Hashtable 默认容量为 11 且不要求底层数组的容量肯定要是 2 的整数次幂, 而 HashMap 则是 16, 必须是 2 的整数次幂.

HashMap 是绝大部分利用键值对存取场景的首选. 多线程环境下, 举荐应用 ConcurrentHashMap.

参考

  1. 图解 HashMap(一)
  2. 图解 HashMap(二)
  3. Java 容器
  4. openjdk 汇合源码
退出移动版