JDK8

主结构为Node<K,V>数组。数组下标为(size()-1)&hash。注意TreeNode为Node子类。所以数组中实际存储的可能为Node,也可能为TreeNode红黑树结构。

Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
}

当冲突小于阈值时,数组中存储Node链表。

当大于阈值时,数组中存储的是TreeNode。存储时有将Node转换为TreeNode的操作过程。

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;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

网上有人说是将自动HashMap转换为TreeMap是严重错误,实际是Node转为TreeNode。

Entry<K,V> extends HashMap.Node<K,V>;

TreeNode 继承 LinkedHashMap.Entry 继承 Node

 

resize() to double currentCapacity

default init capacity 16

default loadFactor 0.75

threshHold=loadFactor*capacity

 

One thought on “Java 8 HashMap数据结构

Leave a reply

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> 

required

+ thirteen = twenty two