本文基于jdk1.9,且只分析了put()的实现

initialCapacity 初始化容量
loadFactor 负载因子

HashMap底层基于数组+链表数组+红黑树实现


put(K key, V value)

Object key;
Object value;
static final int hash(Object key) {
    int hash;
    if(key == null){
        hash = 0;
    }else{
        int h = key.hashCode();
        hash = h^(h>>>16);
    }
}
 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) {
    Node<K,V>[] tab; 
    Node<K,V> p;
    int i;
    tab = table;
    int n = tab.length; //HashMap的长度/大小
    i = (n-1) & hash;//计算所在的数组的下标index
    p = tab[i]; //+++保存所在位置的已经存在的Node数据+++
    if ((tab == null || n == 0){
        tab = resize();//调整Node大小,扩容每次增加一倍
        n = tab.length;
    }
    if ((p == null){//如果要插入的位置Node为null,则在此处直接增加Node
        tab[i] = newNode(hash, key, value, null);//<=new Node<>(hash, key, value, next);
    }
    else {//
        Node<K,V> e; //【代表了?】
        K k = p.key;
        if (p.hash == hash && ((k == key || (key != null && key.equals(k)))){//【?】
            e = p;
        }
        else if (p instanceof TreeNode)//【使用treeNode保存了,详细代码后面再看】
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {//在index位置循环链表,在链表的最后插入新数据
                e = p.next;
                if (e == null) {//++ 最后一个Node
                    p.next = newNode(hash, key, value, null);//将新Node插入到此处链表的最后
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st   TREEIFY_THRESHOLD = 8 
                        treeifyBin(tab, hash);//链表长度大于8则转为红黑树TreeNode
                    break;
                }
                k = e.key;
                if (e.hash == hash && (k == key || (key != null && key.equals(k))))//【?】
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)//如果onlyIfAbsent为true,则不更新此处的值;
                e.value = value;
            afterNodeAccess(e);//Node访问之后执行的操作,更新链表,把最近访问的放到最后
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();//调整大小
    afterNodeInsertion(evict);//节点插入之后执行的操作
    return null;
}

标签: Java, hashmap

添加新评论