Java HashMap

Java 8 之前的 HashMap

在 Java 7 及之前的版本中，HashMap 的底层实现是数组和链表：

生成缩略图出错：无法将缩略图保存到目标地点

HashMap 采用 Entry 数组来存储 key-value 对，每一个键值对组成了一个 Entry 实体，Entry 类实际上是一个单向的链表结构，它具有 next 指针，可以连接下一个 Entry 实体，以此来解决 Hash 冲突的问题，因为 HashMap 是按照 key 的 hash 值来计算 Entry 在 HashMap 中存储的位置的，如果 hash 值相同，而 key 内容不相等，那么就用链表来解决这种 hash 冲突

Java 8 提供的 HashMap

Java 8 的 HashMap 数据结构发生了较大的变化，之前的 HashMap 使用数组+链表实现，新的 HashMap 里，虽然依然使用 table 数组，但是数据类型发生了变换：

Java 8 里的 HashMap 使用的是数组+链表+红黑树实现

生成缩略图出错：无法将缩略图保存到目标地点

在添加链表结点后，如果链表深度达到或超过建树阈值（TREEIFY_THRESHOLD-1），那么会把整个链表重构为树：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    static final int TREEIFY_THRESHOLD = 8;
……
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        ……
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
        ……
……
}

注意，TREEIFY_THRESHOLD 是一个常量，值固定为 8。也就是说，当链表长度达到 7 的时候，会转化为红黑树结构。

注意

只有在两个对象 hashcode() 值相等和 .equals() 为 true 时，两个对象才能互相覆盖