2021-01-17：java中，HashMap底层数据结构是什么？

福哥答案2020-01-07：

1.7 数组+链表

重要字段：

//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂，至于为什么这么做，后面会有详细分析。

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//实际存储的key-value键值对的个数

transient int size;

//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到

int threshold;

//负载因子，代表了table的填充度有多少，默认是0.75

final float loadFactor;

//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException

transient int modCount;

static class Entry<K,V> implements Map.Entry<K,V> {

    final K key;

    V value;

    Entry<K,V> next;

    int hash;

}

1.8 数组+链表+红黑树

重要字段：

//HashMap的主干数组，可以看到就是一个Node数组，初始值为空数组{}，主干数组的长度一定是2的次幂，至于为什么这么做，后面会有详细分析。

transient Node<K,V>[] table;

//实际存储的key-value键值对的个数

transient int size;

//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到

int threshold;

//负载因子，代表了table的填充度有多少，默认是0.75

final float loadFactor;

//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException

transient int modCount;

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

TreeNode<K,V> parent;  // red-black tree links

TreeNode<K,V> left;

TreeNode<K,V> right;

TreeNode<K,V> prev;    // needed to unlink next upon deletion

boolean red;

}

1.7和1.8区别：

①节点类不一样，1.7的是Entry<K,V>，1.8的是Node<K,V>。

②table数组的数据类型不一样。

③1.7的没有TreeNode，1.8的有TreeNode。

评论