HashMap源码分析(jdk1.8)

简介: <p>HashMap源码前前后后看了好几次,也和同事分享过好几次,每次都有新的收获。</p> <p>分享也是一种提高!</p> <p>本文首写于个人云笔记(<a target="_blank" href="http://note.youdao.com/share/?id=07710dc47ce4a8812ddc0261cb659f2e&type=note">点击访问</a>),

HashMap源码前前后后看了好几次,也和同事分享过好几次,每次都有新的收获。

分享也是一种提高!

本文首写于个人云笔记(点击访问),经多次修改,短期内不会有重大修改了,现发于此,有任何问题欢迎交流指正。

    本文最初借鉴于http://www.cnblogs.com/hzmark/archive/2012/12/24/HashMap.html,其基于jdk1.6,自己分析jdk1.8后,发现有很大的不同,遂记录于此。

    Java最基本的数据结构有数组和链表。数组的特点是空间连续(大小固定)、寻址迅速,但是插入和删除时需要移动元素,所以查询快,增加删除慢链表恰好相反,可动态增加或减少空间以适应新增和删除元素,但查找时只能顺着一个个节点查找,所以增加删除快,查找慢。有没有一种结构综合了数组和链表的优点呢?当然有,那就是哈希表(虽说是综合优点,但实际上查找肯定没有数组快,插入删除没有链表快,一种折中的方式吧)。一般采用拉链法实现哈希表

        JDK1.6中HashMap采用的是位桶+链表的方式,即我们常说的散列链表的方式;JDK1.8中采用的是位桶+链表/红黑树的方式,也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候,这个链表就将转换成红黑树。


1、HashMap的定义

1.1 所属包:package java.util;

1.2 导入包:

import java.io.IOException;

import java.io.InvalidObjectException;

import java.io.Serializable;

import java.lang.reflect.ParameterizedType;

import java.lang.reflect.Type;

import java.util.function.BiConsumer;

import java.util.function.BiFunction;

import java.util.function.Consumer;

import java.util.function.Function;

1.3定义:

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, CloneableSerializable {}

2、HashMap的部分属性

    private static final long serialVersionUID = 362498820763181265L;

     //The default initial capacity - MUST be a power of two.

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //jdk1.6直接写16,这效率更快??

     // The maximum capacity,MUST be a power of two <= 1<<30.

    static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次方

    static final float DEFAULT_LOAD_FACTOR = 0.75f; //填充比,装载因子

    /**(jdk1.8新加

     * The bin count threshold for using a tree rather than list for a

     * bin.当add一个元素到某个位桶,其链表长度达到8时将链表转换为红黑树.

     * 2< value<=8 时to mesh with assumptions in  tree removal about conversion back to plain bins upon shrinkage.

     *链表转为binCount>=TREEIFY_THRESHOLD-1,-1 for 1st。

     */ //当某个桶中的键值对数量大于8个【9个起】,且桶数量大于等于64,则将底层实现从链表转为红黑树   

       // 如果桶中的键值对达到该阀值,则检测桶数量   

    static final int TREEIFY_THRESHOLD= 8; //jdk1.8新加

     /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
    * 仅用于 TreeNode的 final void split(HashMap<K,V> map, Node<K,V>[] tabint indexint bit) {
            if  (lc <= UNTREEIFY_THRESHOLD)  
                    //太小则转为链表   
                   tab[index] = loHead.untreeify(map); 
        }

     */

    static final int UNTREEIFY_THRESHOLD = 6; //jdk1.8新加

     /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     * 链表转树时,if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize(); // 即不转为树了

     */  //当桶数量到达64个的时候,才可能将链表转为红黑树

    static final int MIN_TREEIFY_CAPACITY = 64; //jdk1.8新加

    /* ---------------- Fields -------------- */

    // jdk1.6 为 transient Entry[] table;

    transient Node<K,V>[] table; //存储元素(位桶)的数组,length power of two

    transient Set<Map.Entry<K,V>> entrySet;

    transient int size; // key-value对,实际容量

    transient int modCount; //结构改变次数,fast-fail机制

    int threshold; // 新的扩容resize临界值,当实际大小(容量*填充比)大于临界值时,会进行2倍扩容

    final float loadFactor;

Node 内部类

        是HashMap内部类(jdk1.6就是Entry),继承自 Map.Entry这个内部接口,它就是存储一对映射关系的最小单元,也就是说key,value实际存储在Node中。与1.6相比,修改了 hashCode()equals()方法【直接调用Object的hashCode、equals方法,而不是copy代码过来】,去掉了toString()、recordAccess(HashMap<K,V> m)【the value in an entry is overwritten时调用】、recordRemoval(HashMap<K,V> m)【remove entry时调用】方法。【键值对】

static class Node<K,V>implements Map.Entry<K,V> {
        final int hash; //结点的哈希值,不可变
        final K key;
        V value;
        Node<K,V> next; //指向下一个节点
 
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
      // 由直接实现 变为 调用Object的HashCode,实际是一样的
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        } //按位异或^不同为真,数a两次异或同一个数b(a=a^b^b)仍然为原值a。
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            returnoldValue;
        }  // 优化逻辑
        public final boolean equals(Object o) {//改为调用Object的equals
            if (o == this) //内存地址(1.8新增)
                return true;
            if (o instanceof Map.Entry) {//1.6中!(instanceof)返回false
                Map.Entry<?,?> e = (Map.Entry<?,?>)o; //新加<?,?>泛型
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
/*  jdk 1.6 Entry 的equals方法
public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        } */


// 新增的红黑树,继承LinkedHashMap .Entry<K,V>

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; //true表示红节点,false表示黑节点
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        /**
         * Returns root of tree containing this node.获取红黑树的根
         */
        final TreeNode<K,V> root() { 
           for (TreeNode<K,V> r=this, p;;){//p定义,int a=1,b;不能直接输出b(未初始化)
                if ((p = r.parent) == null)  //若改为类似并查集的路径压缩(结构改变)
                    return r;
                r = p;
            }
        }
        /**
         * Ensures that the given root is the first node of its bin.
         */ //确保root是桶中的第一个元素,将root移到桶中的第一个【平衡思想】
        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {}
        /**
         * Finds the node starting at root p with the given hash and key.
         * The kc argument caches comparableClassFor(key) upon first use
         * comparing keys.
         *///查找hash为h,key为k的节点  
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) { // 详见get相关
              TreeNode<K,V> p = this;   ……   }
        /**
         * Calls find for root node.
         */ //获取树节点,通过根节点查找 
        final TreeNode<K,V> getTreeNode(int h, Object k) { // 详见get相关
            return ((parent != null) ? root() : this).find(h, k, null);
        }
        /**
         * Tie-breaking utility for ordering insertions when equal
         * hashCodes and non-comparable. We don't require a total
         * order, just a consistent insertion rule to maintain
         * equivalence across rebalancings. Tie-breaking further than
         * necessary simplifies testing a bit.
         */ //比较2个对象的大小 
        static int tieBreakOrder(Object a, Object b) {}
        /**
         * Forms tree of the nodes linked from this node.
         * @return root of tree
         */ //将链表转为二叉树
        finalvoid treeify(Node<K,V>[] tab) {} //根节点设置为黑色 
        /**
         * Returns a list of non-TreeNodes replacing those linked from
         * this node.
         */ //将二叉树转为链表 
        final Node<K,V> untreeify(HashMap<K,V> map) {}
        /**
         * Tree version of putVal.
         */ //添加一个键值对 
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       inth, K k, V v) {}
        /**
         * Removes the given node, that must be present before this call.
         * This is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. So instead we swap the tree
         * linkages. If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {}
        /**
         * Splits nodes in a tree bin into lower and upper tree bins,
         * or untreeifies if now too small. Called only from resize;
         * see above discussion about split bits and indices.
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */ //将结点太多的桶分割  
        finalvoid split(HashMap<K,V> map, Node<K,V>[] tab, intindex, intbit) {}
        /* --------------------------------------------------*/
        // Red-black tree methods, all adapted from CLR
        //左旋转
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {}
        //右旋转
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {}
         //保证插入后平衡,共5种插入情况
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {}
         //删除后调整平衡 ,共6种删除情况
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {}
        /**
         * Recursive invariant check
         */ //检测是否符合红黑树 
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {}
}

static final int hash(Object key) { // 计算key的hash值hash(key)

        int h;

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

    }

n = tab.length

table的下标【bucket的index】:(n - 1) & hash


由上可知:
        key是有可能是null的,并且会在0桶位位置。
        hashCode的计算也进行了改进,取得key的hashcode后,高16位与低16位异或运算重新计算hash值。
首先由key值通过hash(key)获取hash值h,再通过 hash &(length-1)得到所在数组位置。一般对于哈希表的散列常用的方法有直接定址法,除留余数法等,既要便于计算,又能减少冲突。
        在Hashtable中就是通过除留余数法散列分布的,具体如下:  int index = (hash & 0x7FFFFFFF) % tab.length; 
但是取模中的除法运算效率很低,HashMap则通过hash &(length-1)替代取模,得到所在数组位置,这样效率会高很多。

3、HashMap的4种构造方法

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
       this.loadFactor = loadFactor;
       this.threshold=tableSizeFor(initialCapacity);
    }
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; //all default即16;0.75
    }
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
public HashMap(Map<? extends K, ? extends V> m) { // 参数本就是Map
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
        putMapEntries(m, false); // 仅putAll时传参为true
    }

putMapEntries
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) {// pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY); // 取较小值
                if (t > threshold) // t 大于扩容临界值
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict); //HashMap核心方法,后讲
            }
        }
    }


tableSizeFor:

// 经程序测试:结果为>=cap的最小2的自然数幂(64-》64;65-》128)

static final int tableSizeFor(int cap) { //计算下次需要调整大小的扩容resize临界值

        int n = cap - 1;

        n |= n >>> 1; // >>>“类似于”除以2,高位补0;|=(有1为1)

        n |= n >>> 2; // int--4byte--32bit,共32位

        n |= n >>> 4; 

        n |= n >>> 8;

        n |= n >>> 16; // 至此后每位均为1,00001111

        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

    }

证明:

n=96=0110 0000(暂已8位为例,事实上32位)

n>>>1使1位为0,若n首位为1,则结果为1,若为0,则忽略;确保首位有值时结果为1;至此首位完毕

0110 0000 |=0011 0000》0111 0000》112

n>>>2使新的n前2位为0,0111 0000|=0011 1100》0111 1100》124

1+2+4+8+16=31

   01100000

1  00110000

=  01110000 确保1、2位为1,所以接下来移2位

2  00011100 

=  01111100 确保3、4位为1(此时1-4位均为1),所以接下来移4位

4  00000111(1)

=  01111111 以此类推

    计算新的扩容临界值,不再是JDK1.6的while循环来保证哈希表的容量一直是2的整数倍数,用移位操作取代了1.6的while循环移位(不断乘2)。HashMap的构造函数中,都直接或间接的调用了tableSizeFor函数。
    在1.6中,int capacity = 1;  while (capacity < initialCapacity)  capacity <<= 1。
    其返回值是>=cap的最小2的自然数。(大于等于1tableSizeFor(-111)=1)
性能优化:
       length2的整数幂保证了length - 1 最后一位(二进制表示)为1,从而保证了索引位置index即  hash & length -1)的最后一位同时有为0和为1的可能性,保证了散列的均匀性。反过来讲,若length为奇数,length-1最后一位为0,这样与h按位与【同1为1】 的最后一位肯定为0,即索引位置肯定是偶数,这样数组的奇数位置全部没有放置元素,浪费了大量空间。

简而言之:length为2的幂保证了按位与最后一位的有效性,使哈希表散列更均匀


来看一下上面调用的resize()方法,这也是HashMap中一个非常重要的方法。
与1.6相比,将舍去transfer(Entry[] newTable),直接写到resize中并优化copy逻辑,并舍去static方法indexFor(hash, table.length),将其直接写到resize中。
Node<K,V>[] resize() 
// Initializes or doubles table size,两倍扩容并初始化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) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab; //到达极限,无法扩容
            }
            else if((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold阀值
       }
      // oldCap=0 ,oldThr>0,threshold(新的扩容resize临界值)
       else if (oldThr > 0) 
           newCap = oldThr; //新容量=旧阀值(扩容临界值)
       else {     // oldCap=0 ,oldThr=0,调用默认值来初始化
         newCap = DEFAULT_INITIAL_CAPACITY;
         newThr=(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr== 0) { //新阀值为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; 
         // table初始化,bucket copy到新bucket,分链表和红黑树
        if (oldTab != null) { // 不为空则挨个copy,影响效率!!!
            for (int j = 0; j < oldCap; ++j) {
               Node<K,V> e;
               if ((e = oldTab[j]) != null) { //先赋值再判断
                  oldTab[j] = null; //置null,主动GC
                  //如果该桶只有一个元素,重新计算桶位,则直接赋到新的桶里面
                  if (e.next == null) 
                //1.6的indexFor,计算key;tableSizeFor性能优化
                    newTab[e.hash &(newCap - 1)]= e; //hash&(length-1)
                  else if (e instanceof TreeNode) // 红黑树
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                  else { //链表,preserve order保持顺序
                        //一个桶中有多个元素,遍历将它们移到新的bucket或原bucket
                        Node<K,V> loHead = null,loTail = null;//lo原bucket的链表指针
                        Node<K,V> hiHead = null, hiTail = null;//hi新bucket的链表指针
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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) { //原bucket位置的尾指针不为空(即还有node)
                            loTail.next = null; //链表最后得有个null
                            newTab[j] = loHead;//链表头指针放在新桶的相同下标(j)处
                        }
                        if (hiTail != null) {  //放在桶 j+oldCap
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;//j+oldCap见下
                        }
                    }
                }
            }
        }
        return newTab;
    }

这里详细解释一下 resize】时【链表】的变化
元素位置在【原位置】或【原位置+oldCap】
①、由前面的知识可知, table的下标【bucket的index】由( n  - 1) &  hash计算
(n为table的length,hash即hash(key)计算方式为(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16));
、假设我们length从16resize到32(以下仅写出8位,实际32位), hash(key)是不变的。
n-1:     0000 1111-----》0001 1111【高位全0,&不影响】
hash1:    0000 0101-----》0000 0101
index1:  0000 0101-----》0000 0101【index不变
hash2:    0001 0101-----》0001 0101
index2:  0000 0101-----》0001 0101【新index=5+16即原index+oldCap

、新bucket下标:(2n - 1) & hash(key), 由于是&操作,同1为1;hash(key)不变;2n-1在原来n-1的基础上仅最高位0变1;
、so,HashMap在Resize时,只需看(新) n-1最高位对应的hash(key)位是0还是1即可,0则位置不变,1则位置变为原位置+oldCap
、如何确认(新)n-1最高位对应的hash(key)位是0还是1呢?源码给出了很巧妙的方式(e.hash & oldCap):e即Node,由put和Node构造函数相关源码可知,e.hash即为hash(key);oldCap为0001 0000(仅最高位为1);
相&为0说明e.hash最高位为0,否则为1.

总结:
1、无需重新计算Hash,节省了时间;
2、由于所计算的hash(key)位是1是0可以认为是随机的,所以将一个冲突长链表又“均分”成了两个链表,减少碰撞。

4、HashMap的方法实现

1)put相关

public put(K key, V value) {

        return putVal(hash(key), keyvaluefalsetrue);

    }

// 检测指定的key对应的value是否为null,如果为null,则用新value代替原来的null

@Override

    public V putIfAbsent(K key, V value) {

        return putVal(hash(key), keyvaluetruetrue);

    }

核心方法: putVal ( hash , key , value , onlyIfAbsent , evict )
* @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;
        if ((tab = table) == null || (n = tab.length) == 0)//table空||length为0
            n = (tab = resize()).length; // 分配空间,初始化
        if ((p = tab[i = (n - 1) & hash]) == null)//hash所在位置(第i个桶)为null,直接put
            tab[i] = newNode(hash, key, value, null);
        else {//tab[i]有元素,则需要遍历结点后再添加 
            Node<K,V> e; K k;
            // hash、key均等,说明待插入元素和第一个元素相等,直接更新
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode) //红黑树冲突插入
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else{ // 链表
                for (int binCount = 0; ; ++binCount){ //死循环,直到break
                    if ((e = p.next) == null) { //表尾仍没有key相同节点,新建节点
                        p.next = newNode(hash, key, value, null);
//若链表数量大于阀值8【9个】,则调用treeifyBin方法,仅当tab.length大于64才将链表改为红黑树
                  // 如果tab.length<64或table=null,则重构一下链表
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash); //binCount>=9则链表转树
                        break; // 退出循环
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;  // hash、key均相等,说明此时的节点==待插入节点,更新
                    p = e; //更新p指向下一个节点
               }
            }
            //当前节点e = p.next不为null,即链表中原本存在了相同key,则返回oldValue
            if (e != null) {// existing mapping for key
                V oldValue = e.value;
               //onlyIfAbsent值为false,参数主要决定当该键已经存在时,是否执行替换
                if (!onlyIfAbsent || oldValue == null) 
                    e.value = value;
                afterNodeAccess(e); //调用linkedHashMap,move node to last
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold) //++size后再检测是否到了阀值
            resize();
        afterNodeInsertion(evict);//调用linkedHashMap,true则possibly remove eldest
        return null; // 原hashMap中不存在相同key的键值对,则在插入键值对后,返回null。
    }
/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 // MIN_TREEIFY_CAPACITY=64.
// tab.length 为2的幂,表示容量,不是size。
 */ //当桶中链表的数量>=9的时候,底层则改为红黑树实现 
    final void treeifyBin(Node<K,V>[] tab, inthash) {
        intn, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
// For treeifyBin
   TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }
// 链节点替换为树

put(K key, V value)的逻辑:
  1. 判断键值对数组tab[]是否为空或为null,是则resize(); 
  2. 根据键值key的hashCode()计算hash值得到当前Node的索引i,如果tab[i]==null【没碰撞】,直接新建节点添加,否则【碰撞】转入3 
  3. 判断当前数组中处理hash冲突的方式为红黑树还是链表(check第一个节点类型即可),分别处理。【①是红黑树则按红黑树逻辑插入;②是链表,则遍历链表,看是否有key相同的节点;③有则更新value值,没有则新建节点,此时若链表数量大于阀值8【9个】,则调用treeifyBin方法(此方法先判断table是否为null或tab.length小于64,是则执行resize操作,否则才将链表改为红黑树)。】
  4. 如果size+1> threshold则resize。

public void putAll(Map<? extends K, ? extends V> m) {

        putMapEntries(mtrue); // 详见构造方法,仅putAll参数为true

    }

Note:
        p utAll可以合并map,如果key重复,则用新值替换就值(相见Study代码)。

2)Remove、clear

publicV remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ? null:e.value;
    }
@Override
    public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }
/**
     * Implements Map.remove and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
                       仅HashIterator的remove方法为false
     * @return the node, or null if none
     */
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; intn, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node); // 空方法??
                return node;
            }
        }
        return null;
    }
// for循环,挨个置为null,GC
public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

Tip:
A、 HashMap貌似不存在类似于ArrayList的trimToSize()压缩空间的方法。
B、HashMap map= new HashMap(); Hashmap map=null;有什么区别?
都实例化了map;
前者创建对象、分配地址,将该地址的引用赋值给对象
后者只是创建对象,地址为空(null),并且在赋值对象之前,进行任何操作都将报 NullPointerException。

3)迭代方式、迭代时如何正确Remove
        hashmap有自己的迭代器,
① 定义  abstract  class  HashIterator  {};
其remove方式实现如下:
final void remove() 
public final void remove() {
         Node<K,V> p = current;
         if (p == null)
                thrownew IllegalStateException();
         if (modCount != expectedModCount)
                thrownew ConcurrentModificationException();
         current = null;
         K key = p.key;
         removeNode(hash(key), key, null, false, false);
         expectedModCount = modCount; //同步expectedModCount和modCount的值
   }

② 定义迭代器  EntryIterator KeyIterator KeyIterator 

final class EntryIterator extendsHashIterator
        implementsIterator<Map.Entry<K,V>> {
        publicfinal Map.Entry<K,V> next() { return nextNode(); }
  }

③  final  class  EntrySet  extends  AbstractSet<Map.Entry<K,V>> {…… EntryIterator…… }
KeySet、 Values类似。
迭代 具体实现:
for (Entry<Object, Object> entry : map.entrySet()) {
            System.out.println(entry.getKey());
            // entry.remove(); // error
}
// jdk1.8 lambda迭代,key、value缺一不可
map.forEach((key, value) -> System.out.println(key + "==" + value));
Remove正确调用方式:
Iterator<Entry<Object, Object>> it = map.entrySet().iterator();
while (it.hasNext()) {
     Entry<Object, Object> entry = it.next();
     Integer key = (Integer) entry.getKey();
     if (key % 2 == 0) {
          System.out.println("Delete key:" + key);
          it.remove();
          System.out.println("The key " + +key + " was deleted");
     }
}

发散:

1、如果是遍历过程中增加或修改数据呢?
    增加或修改数据只能通过Mapput方法实现,在遍历过程中修改数据可以,但如果增加新key就会在下次循环时抛异常,因为在添加新keymodCount也会自增。

2、有些集合类也有同样的遍历问题,如ArrayList通过Iterator方式可正确遍历完成remove操作,直接调用listremove方法就会抛异常。

3jdk为什么允许通过iterator进行remove操作
        HashMap
keySetremove方法都可以通过传递key参数删除任意的元素,而iterator只能删除当前元素(current)【movable为false,一旦删除的元素是iterator对象中next所正在引用的,如果没有通过modCount expectedModCount的比较实现快速失败抛出异常,下次循环该元素将成为current指向,此时iterator就遍历了一个已移除的过期数据。ConcurrentModificationException是RuntimeException,不要在客户端捕获它。如果发生此异常,说明程序代码的编写有问题,应该仔细检查代码而不是在catch中忽略它。

    Iterator自身的remove()方法会自动同步expectedModCount和modCount的值(见上源码)。确保遍历可靠的原则是只在一个线程中使用这个集合,或者在多线程中对遍历代码进行同步。

4)get、contains相关

public V get(Object key) { // 返回value或null
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
// 指定key不存在则返回 defaultValue
@Override
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }
public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }
// 存在指定(1或多个)value即返回true
public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (inti = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        returnfalse;
    }
get相关的核心方法:

final Node<K,V> getNode(int hash, Object key) { // 返回Node or null
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { //(n-1)&hash位置不为null
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode) //遍历红黑树,得到节点值
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do { //遍历链表,得到节点值,通过hash和equals(key)确认所查找元素。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
// Calls find for root node.
final TreeNode<K,V> getTreeNode(int h, Object k) { // k即key
     return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
*/ // getTreeNode核心方法
final TreeNode<K,V> find(int h, Object k, Class<?> kc) { // k即key,kc为null
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h) // ph存当前节点hash
                    p = pl;
                elseif (ph < h) // 所查hash比当前节点hash大
                    p = pr; // 查右子树
                elseif ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p; // hash、key均相同,【找到了!】返回当前节点
                elseif (pl == null) // hash等,key不等,且当前节点的左节点null
                    p = pr; // 查右子树
                elseif (pr == null)
                    p = pl;
               // get->getTreeNode传递的kc为null。||逻辑或,短路运算,有真即可
               // false || (false && ??)
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr; 
                else if ((q = pr.find(h, k, kc)) != null)
                    return q; //通过右节点查找???
                else
                    p = pl;
            } while (p != null);
            return null;
        }
看一下hashMap中的comparableClassFor的解释及部分代码:
// Returns x's Class if it is of the form "class C implements  Comparable<C>", else null.
// x实现Comparable接口则返回x的类型,否则返回null。
static Class<?> comparableClassFor(Object x) {
        if (xinstanceof Comparable) {
           ……
            if ((c = x.getClass()) == String.class) // bypass checks
                returnc;
            if ((ts = c.getGenericInterfaces()) != null) {
                ……
                }
            }
        }
        returnnull;
    }
//Returns k.compareTo(x) if x matches kc (k's screened comparable class), else 0// 暂未理解透彻
    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) { // x即pk
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x)); // 待查k与当前k(x)比较
    }


V get(Object key):
        1、(n - 1) & hash计算bucket的index;【hash= hash(key)如下
        1、判断第一个节点hash、key是否相等,是则返回first【always check first node】;
        2、若(e = first.next) != null
         若first为红黑树,getTreeNode返回根节点,并调用其find方法,根据hash值判断进入左(右)子树,逐层查找;
         若为链表,遍历链表,得到节点值,通过hash和equals(key)确认所查找元素。
    3、没有该元素,返回null。

static final int hash(Object key) {
        inth;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
Tip:
get、containsKey都可以用来判断map中是否存在该元素吗?
    当get()方法的返回值为null时,可能有两种情况,一种是在集合中没有该键对象,另一种是该键对象没有值本就为null。因此,在Map集合中不应该利用get()方法来判断是否存在某个元素,而应该利用containsKey()方法来判断。

5)replace相关
// 将指定key对应的value替换成新value。如果key不存在,返回null。
@Override
    publicV replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }
// 仅当指定key的value为oldValue时,用newValue替换oldValue
@Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            returntrue;
        }
        returnfalse;
    }
// function? lambda,详见study代码
//计算结果作为key-value对的value值
@Override
    publicvoidreplaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        Node<K,V>[] tab;
        if (function == null)
            thrownewNullPointerException();
        if (size > 0 && (tab = table) != null) {
            intmc = modCount;
            for (inti = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    e.value = function.apply(e.key, e.value);
                }
            }
            if (modCount != mc)
                thrownew ConcurrentModificationException();
        }
    }
map.replaceAll((key, value) -> {// 其他用法???
            if ((int) key > 6) {
                value = 99;
            }
            returnvalue; // value改变,返回value
      });
// 将所有key>6的value置为99

6)其他函数

toString(): 返回格式如{null=1, 2=8, 3=7, 9=8}或{ }。

int size()return size。
boolean isEmpty()return size == 0。
equals() :继承于AbstractMap、Object等。

3个afterNode……空方法,仅内部使用:

// Callbacks to allow LinkedHashMap post-actions

void afterNodeAccess(Node<K,V> p) { }

void afterNodeInsertion(booleanevict) { }

void afterNodeRemoval(Node<K,V> p) { }


小结:
1、多了1300行代码(共2380), static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> 。get性能O(n)-->O(lgN)
2、尽量直接调用系统函数
    Node<K,V>中调用Object的hashCode和Equals
3、 减少不必要的内部函数调用
    resize中的transfer(Entry[] newTable)【逻辑优化】和indexFor(hash, table.length)
4、储存方式
    位桶存储;若产生hash碰撞,位桶中按链表存储;若链表达到阀值,链表转换为红黑树。
5、赋值巧妙
if ((p = tab[i = (n - 1) & hash]) == null)判断赋值两不误。
6、通过bool或instance实现代码复用
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

put、get的红黑树部分有待再次阅读分析。


部分源码注释翻译:

  1. 基于map接口;
  2. key、value允许空(仅允许一个key为null);
  3. 和HashTable类似,除了非同步和允许null;
  4. 无序,顺序可能变;
  5. get、put效率O(1),迭代器与number of buckets、size相关(所以initial很重要);如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低);
  6. capacity:buckets的大小,table被create时便实实在在的存在;
  7. number of entries达到load factor*capacity便rehashed,approximately(大约)2倍buchets;
  8.  load factor (.75)是个时间和空间的折衷,higher-->减少空间开销,增加查询开销(包括get、put);
  9. 非同步,若结构改变(add、delete,不包括修改value),必须在外部同步;考虑synchronizedMap,Map m = Collections.synchronizedMap(new HashMap(...))
  10. 迭代时remove报异常ConcurrentModificationException,不能写一个依赖他正确性的程序;
  11. 链表转红黑树后,若树变短,会恢复为链表。


有任何问题,欢迎指正探讨。
本文作者:云海(花名)

相关文章:

基于jdk1.8的HashMap源码学习笔记:http://www.cnblogs.com/ToBeAProgrammer/p/4787761.html

目录
相关文章
|
1月前
|
存储 安全 Java
【JDK 源码分析】ConcurrentHashMap 底层结构
【1月更文挑战第27天】【JDK 源码分析】ConcurrentHashMap 底层结构
|
1月前
|
Java
【JDK 源码分析】HashMap 操作方法
【1月更文挑战第27天】【JDK 源码分析】HashMap Put 元素 初始化
|
1月前
|
Java
Integer类【JDK源码分析】
Integer类【JDK源码分析】
26 0
|
1月前
|
存储 网络协议 Java
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)(二)
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)
43 0
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)(二)
|
7月前
源码分析系列教程(12) - 手写Map框架(基于JDK1.7)
源码分析系列教程(12) - 手写Map框架(基于JDK1.7)
24 0
|
10月前
|
Java API 索引
LinkedList类【JDK源码分析】
LinkedList类【JDK源码分析】
39 0
|
10月前
|
算法 搜索推荐 Java
Arrays类【JDK源码分析】
Arrays类【JDK源码分析】
35 0
|
10月前
|
安全 Java API
AbstractStringBuilder类【JDK源码分析】
AbstractStringBuilder类【JDK源码分析】
72 0
|
10月前
|
安全 Java API
StringBuilder类【JDK源码分析】
StringBuilder类【JDK源码分析】
66 0
|
10月前
|
存储 算法 Java
String类【JDK源码分析】
String类【JDK源码分析】
43 0