精华内容
参与话题
问答
  • HashMap源码阅读

    2017-08-11 22:05:12
    HashMap源码阅读

        面试中会经常被问到HashMap的实现,而且日常工作中也会经常使用的HashMap,HashMap的重要性便不言而喻了。下面我挑自己感觉重要的地方开始看起,顺序也按我理解的顺序开始读起。

        一、从HashMap中定义的属性看起。从源码中我们可以看到HashMap中数组初始大小默认为16,大小为2的n次方,每次扩容也是扩大为原来的2倍,这在计算位置时可以非常巧妙地使用位运算。负载因子默认为0.75,也就是当map中元素数目达到数组大小*0.75时将进行扩容。

    /**
         * 默认初始容量为16.
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * 最大容量2^30
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /**
         * An empty table instance to share when the table is not inflated.
         */
        static final Entry<?,?>[] EMPTY_TABLE = {};
    
        /**
         * 对应数组部分,初始容量为16,大小是2的n次方。transient 修饰变量表示在序列化时不被序列化。
         */
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
        /**
         * The number of key-value mappings contained in this map.
         */
        transient int size;
    
        /**
         * 进行扩容的阈值 (capacity * load factor).
         * @serial
         */
        int threshold;
    
        /**
         * The load factor for the hash table.
         */
        final float loadFactor;
    
        /**
         * The number of times this HashMap has been structurally modified
         * Structural modifications are those that change the number of mappings in
         * the HashMap or otherwise modify its internal structure (e.g.,
         * rehash).  This field is used to make iterators on Collection-views of
         * the HashMap fail-fast.  (See ConcurrentModificationException).
         */
        transient int modCount;
    
        /**
         * The default threshold of map capacity above which alternative hashing is
         * used for String keys. Alternative hashing reduces the incidence of
         * collisions due to weak hash code calculation for String keys.
         */
        static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
        二、HashMap的put(K key,V value)。

     public V put(K key, V value) {
    	if (table == EMPTY_TABLE) {
    		inflateTable(threshold);
    	}
    	//允许key为空
    	if (key == null)
    		return putForNullKey(value);
    	//根据hashcode值计算hash值
    	int hash = hash(key);
    	//根据hash值计算在数组中的位置
    	int i = indexFor(hash, table.length);
    	//顺着链进行查找
    	for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    		Object k;
    		//key是同一个对象或是equals值相同
    		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    			V oldValue = e.value;
    			e.value = value;
    			e.recordAccess(this);
    			return oldValue;
    		}
    	}
    	//记录修改结构的次数
    	modCount++;
    	//在头部添加元素
    	addEntry(hash, key, value, i);
    	return null;
    }

        可以发现在HashMap中键值跟value都可以为null:

    private V putForNullKey(V value) {
    	for (Entry<K,V> e = table[0]; e != null; e = e.next) {
    		if (e.key == null) {
    			V oldValue = e.value;
    			e.value = value;
    			e.recordAccess(this);
    			return oldValue;
    		}
    	}
    	modCount++;
    	addEntry(0, null, value, 0);
    	return null;
    }
         以位运算来取代求模运算:

    static int indexFor(int h, int length) {
    	// 因长度都为2的n次方,此处求余运算可以转换为按位与运算
    	return h & (length-1);
    }

        三、HashMap的get(key)。

    public V get(Object key) {
    	//key为null的情况
    	if (key == null)
    		return getForNullKey();
    	Entry<K,V> entry = getEntry(key);
    	//有对应实体则返回value值,否则返回null
    	return null == entry ? null : entry.getValue();
    }
    private V getForNullKey() {
    	//一个元素都没有时返回null
    	if (size == 0) {
    		return null;
    	}
    	//返回key值为null的value
    	for (Entry<K,V> e = table[0]; e != null; e = e.next) {
    		if (e.key == null)
    			return e.value;
    	}
    	return null;
    }
    final Entry<K,V> getEntry(Object key) {
    	//一个元素都没有时返回null
    	if (size == 0) {
    		return null;
    	}
    	//利用key的hashcode值计算hash值
    	int hash = (key == null) ? 0 : hash(key);
    	//在找到的链上从前往后找
    	for (Entry<K,V> e = table[indexFor(hash, table.length)];
    		 e != null;
    		 e = e.next) {
    		Object k;
    		//关键点:因不同的对象也可能对应相同的hash值,所以不仅要hash值相同,equals方法对应值也要相同。
    		//对于普通对象来说,equals相同实际上是比较的引用值,对应String类型来说,equals比较的是内容。
    		if (e.hash == hash &&
    			((k = e.key) == key || (key != null && key.equals(k))))
    			return e;
    	}
    	return null;
    }

        附一篇感觉不错的文章:http://www.importnew.com/7099.html,从这篇文章中我们可以学到我们最好使用Stirng,Integer等这类不变的wrapper类作key值这样才能找到我们所需的对象,当然我们也可以重写类的hashcode跟equals方法来实现。

        四、HashMap的扩容

    void addEntry(int hash, K key, V value, int bucketIndex) {
    	//在添加实体时要先看是否达到了负载因子对应的threshold,当达到时就要进行扩容,容量变为原来的2倍。
    	if ((size >= threshold) && (null != table[bucketIndex])) {
    		resize(2 * table.length);
    		hash = (null != key) ? hash(key) : 0;
    		bucketIndex = indexFor(hash, table.length);
    	}
    
    	createEntry(hash, key, value, bucketIndex);
    }

    void resize(int newCapacity) {
    	Entry[] oldTable = table;
    	int oldCapacity = oldTable.length;
    	if (oldCapacity == MAXIMUM_CAPACITY) {
    		threshold = Integer.MAX_VALUE;
    		return;
    	}
    
    	Entry[] newTable = new Entry[newCapacity];
    	transfer(newTable, initHashSeedAsNeeded(newCapacity));
    	table = newTable;
    	threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    void transfer(Entry[] newTable, boolean rehash) {
    	int newCapacity = newTable.length;
    	//遍历桶
    	for (Entry<K,V> e : table) {
    		//顺着链挨个复制,将每个Entry接到新桶的最前面
    		while(null != e) {
    			Entry<K,V> next = e.next;
    			if (rehash) {
    				e.hash = null == e.key ? 0 : hash(e.key);
    			}
    			//需要重新计算位置
    			int i = indexFor(e.hash, newCapacity);
    			e.next = newTable[i];
    			newTable[i] = e;
    			e = next;
    		}
    	}
    }

        五、HashMap并发安全问题。

        友情链接:http://www.cnblogs.com/andy-zhou/p/5402984.html

        1、两个线程同时在一个链上插入Entry时会丢失元素。

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        //两个线程同时创建节点时会丢失一个
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }     

        2、多线程并发,在rehash时可能出现环。

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;//-->假设线程1被在这阻塞
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                //悲剧发生处,如另一个线程已经反转了顺序,在这再重新反转,会出现环
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }



        六、解决HashMap并发安全问题。

        1、使用HashTable替代HashMap

        2、使用ConcurrentHashMap替代HashMap,其利用了分段锁的原理,只对相应段进行加锁,效率比HashTable要高。

        3、使用Collections.synchronizedMap将HashMap包装起来。








    展开全文
  • HashMap 源码阅读

    2019-01-06 04:26:00
    目录 HashMap 源码阅读 Map 接口 数据结构 initialCapacity 和 loadFactor hash() 方法 resize() 查找 getNode() 方法 遍历 ...

    HashMap 源码阅读

    之前读过一些类的源码,近来发现都忘了,再读一遍整理记录一下。这次读的是 JDK 11 的代码,贴上来的源码会去掉大部分的注释, 也会加上一些自己的理解。

    20181231181859.png

    Map 接口

    这里提一下 Map 接口与1.8相比 Map接口又新增了几个方法:
    20190101212411.png

    • 这些方法都是包私有的static方法;
    • of()方法分别返回包含 0 - 9 个键值对的不可修改的Map;
    • ofEntries()方法返回包含从给定的entries总提取出来的键值对的不可修改的* Map(不会包含给定的entries);
    • entry()方法返回包含键值对的不可修改的 Entry,不允许 null 作为 key 或 value;
    • copyOf()返回一个不可修改的,包含给定 Map 的 entries 的 Map ,调用了ofEntries()方法.

    数据结构

    HashMap 是如何存储键值对的呢?

    HashMap 有一个属性 table:

    transient Node<K,V>[] table;

    table 是一个 Node 的数组, 在首次使用和需要 resize 时进行初始化; 这个数组的长度始终是2的幂, 初始化时是0, 因此能够使用位运算来代替模运算.

    HashMap的实现是装箱的(binned, bucketed), 一个 bucket 是 table 数组中的一个元素, 而 bucket 中的元素称为 bin .

    来看一下 Node , 很显然是一个单向链表:

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        
        ...
    }

    当然, 我们都知道 bucket 的结构是会在链表和红黑树之间相互转换的:

    // 转换成红黑树
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    
    // 转换成链表结构
    if (lc <= UNTREEIFY_THRESHOLD)
        tab[index] = loHead.untreeify(map);

    注意在 treeifyBin() 方法中:

    // table 为 null 或者 capacity 小于 MIN_TREEIFY_CAPACITY 会执行 resize() 而不是转换成树结构
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();

    TreeNode 的结构和 TreeMap 相似, 并且实现了 tree 版本的一些方法:

    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;
    
        ...
    }

    initialCapacity 和 loadFactor

    先看一下 HashMap 的4个构造器,可以发现3个重要的 int :threshold,initialCapacity 和 loadFactor ,其中 threshold 和 loadFactor 是 HashMap 的私有属性。

    HashMap 的 javadoc 中有相关的解释:

    • capacity,HashMap 的哈希表中桶的数量;
    • initial capacity ,哈希表创建时桶的数量;
    • load factor ,在 capacity 自动增加(resize())之前,哈希表允许的填满程度;
    • threshold,下一次执行resize()时 size 的值 (capacity * load factor), 如果表没有初始化, 存放的是表的长度, 为0时表的长度将会是 DEFAULT_INITIAL_CAPACITY

    注意: 构造器中的 initialCapacity 参数并不是 table 的实际长度, 而是期望达到的值, 实际值一般会大于等于给定的值. initialCapacity 会经过tableSizeFor() 方法, 得到一个不大于 MAXIMUM_CAPACITY 的足够大的2的幂, 来作为table的实际长度:

    static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    loadFactor 的默认值是 0.75f :

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    initialCapacity 的默认值是16:

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    capacity 的最大值是1073741824:

    static final int MAXIMUM_CAPACITY = 1 << 30;

    在 new 一个 HasMap 时,应该根据 mapping 数量尽量给出 initialCapacity , 减少表容量自增的次数 . putMapEntries() 方法给出了一种计算 initialCapacity 的方法:

    float ft = ((float)s / loadFactor) + 1.0F;
    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
             (int)ft : MAXIMUM_CAPACITY);
    if (t > threshold)
        threshold = tableSizeFor(t);

    这段代码里的 t 就是 capacity .

    hash() 方法

    hash() 是 HashMap 用来计算 key 的 hash 值的方法, 这个方法并不是直接返回 key 的 hashCode() 方法的返回值, 而是将 hashCode 的高位移到低位后 再与原值异或.

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    因为 HashMap 用 hash & (table.length-1)代替了 模运算 , 如果直接使用 hashCode() 的返回值的话, 只有hash code的低位(如果 table.length 是2的n次方, 只有最低的 n - 1 位)会参加运算, 高位即使发生变化也会产生碰撞. 而 hash() 方法把 hashCode 的高位与低位异或, 相当于高位也参加了运算, 能够减少碰撞.

    举个例子:
    假设 table.length - 1 的 值为 0000 0111, 有两个hash code : 0001 0101 和 0000 0101. 这两个hash code 分别与 table.length - 1 做与运算之后的结果是一样的: 0000 0101; 将这两个hash code 的高位和低位异或之后分别得到: 0001 0100、 0000 0101, 此时再分别与 table.length - 1 做与运算的结果是 0000 0100 和 0000 0101, 不再碰撞了.

    resize()

    resize() 方法负责初始化或扩容 table. 如果 table 为 null 初始化 table 为 一个长度为 threshold 或 DEFAULT_INITIAL_CAPACITY的表; 否则将 table 的长度加倍, 旧 table 中的元素要么呆在原来的 index 要么以2的幂为偏移量在新 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) {
                // 旧 table 的容量已经达到最大, 不扩容, 返回旧表
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 将旧容量加倍作为新表容量, 如果新表容量没达到容量最大值, 并且旧容量大于等于默认容量, threshold 加倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 旧的threshold 不为 0 , 旧 threshold 作为新表的容量
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 旧 threshold 为 0 , 用 DEFAULT_INITIAL_CAPACITY 作为新容量, 用默认值计算新 threshold
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 之前没有计算过新 threshold , 计算 threshold
            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;
        if (oldTab != null) {
        // 将旧表中的元素移动到新表
            for (int j = 0; j < oldCap; ++j) {
                // 遍历旧表
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // 帮助 GC
                    oldTab[j] = null;
                    if (e.next == null)
                        // 这个桶里只有一个元素, 此处用位运算代替了模运算
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 如果这个 bucket 的结构是树, 将这个 bucket 中的元素分为高低两部分((e.hash & bit) == 0 就分在低的部分, bit 是 oldCap), 低的部分留在原位, 高的部分放到 newTab[j + oldCap]; 如果某一部分的元素个数小于 UNTREEIFY_THRESHOLD 将这一部分转换成链表形式, 否则就形成新的树结构
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 将普通结构的 bucket 中的元素分为高低两部分, 低的部分留在原位, 高的部分放到 newTab[j + oldCap]
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        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) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    举个例子解释一下高低两部分的划分:

    • 扩容前 table.length 是 0000 1000 记为 oldCap , table.length - 1 是 0000 0111 记为 oldN;
    • 扩容后 table.length 是 0001 0000 记为 newCap, table.length - 1 为 0000 1111 记为 newN;
    • 有两个Node, hash ( hash() 方法得到的值)分别为 0000 1101 和 0000 0101 记为 n1 和 n2;

    在扩容前, n1 和 n2 显然是在一个 bucket 里的, 但在扩容后 n1 & newN 和 n2 & newN 的值分别是 0000 1101 和 0000 0101, 这是需要划分成两部分, 并且把属于高部分的 bin 移动到新的 bucket 里的原因.

    扩容后, hash 中只会有最低的4位参加 index 的计算, 因此可以用第4位来判断属于高部分还是低部分, 也就可以用 (hash & oldCap) == 0 来作为属于低部分的依据了.

    查找

    查找方法只有 get()getOrDefault() 两个, 都是调用了 getNode()方法:

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    @Override
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

    getNode() 方法

    final Node<K,V> getNode(int hash, Object key) {
        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) {
            // table 已经被初始化且 table 的长度不为 0 且 对应的 bucket 里有 bin
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 第一个节点的 key 和 给定的 key 相同
                return first;
            if ((e = first.next) != null) {
                // bucket 中还有下一个 bin
                if (first instanceof TreeNode)
                    // 是树结构的 bucket, 调用树版本的 getNode 方法
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    // 在普通的链表中查找 key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    遍历

    可以通过entrySet()keySet()values()分别获得 EntrySetKeySet()Values对象, 他们的迭代器都是HashIterator的子类.

    fast-fail 和 modCount

    HashMap 不是线程安全的, 并且实现了 fast-fail 机制. 当一个迭代器被创建的时候(或者迭代器自身的 remove() 方法被调用), 会记录当前的 modCount 作为期待中的 modCount, 并在操作中先检查当前 modCount 是不是和旧的 modCount 相同, 不同则会抛出ConcurrentModificationException.

    任何结构修改(新增或删除节点)都会改变 modCount 的值.

    新增和更新

    1.8 之前有4个方法和构造器能够往 HashMap 中添加键值对: 以一个Map为参数的构造器、put()putAll()putIfAbsent(),

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }
    
    @Override
    public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, true);
    }

    他们分别调用了putMapEntries()putVal(). 这两个方法中有一个参数 evict , 仅当初始化时(构造器中)为 false.

    putVal() 方法

    来看一下putVal() 方法:

    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 未被初始化或者长度为 0 时, 执行 resize()
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 对应的 bucket 里没有元素, 新建一个普通 Node 放到这个位置
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 第一个节点的 key 和 给定的 key 相同
                e = p;
            else if (p instanceof TreeNode)
                // 树结构, 调用树版本的 putVal, 如果树结构中存在 key, 将会返回相应的 TreeNode, 否则返回 null
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 在链表中没有找到 key, 新建一个节点放到链表末尾
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 当前桶转换成树结构
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // key 相同 break
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                // key 在 map 中存在
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // 覆盖旧值
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // key 之前在 map 中不存在, 发生了结构变化, modCount 增加 1
        ++modCount;
        if (++size > threshold)
            // 扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    HashMap 提供了三个回调方法:

    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

    putMapEntries() 方法

    putMapEntries()方法就简单多了

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                // table 还没有初始化, 计算出 threshold
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                // s 超过了 threshold, 扩容
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                // 调用 putVal() 方法, 将键值对放进 map
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

    删除

    删除元素有三个方法, 还有 EntrySet 和 KeySet 的 remove 和 clear 方法:

    public V 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;
    }
    
    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;
        }
    }

    removeNode() 方法

    removeNode() 方法有5个参数, 说明一下其中两个:

    • matchValue 为 true 时, 只在 value 符合的情况下删除;
    • movable 为 false 时, 删除时不移动其他节点, 只给树版本的删除使用.
    final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            // table 已经被初始化且 table 的长度不为 0 且 对应的 bucket 里有 bin
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 第一个的 key 和给定的 key 相同
                node = p;
            else if ((e = p.next) != null) {
                // bucket 中有不止一个 bin
                if (p instanceof TreeNode)
                    // 树结构, 调用树版本的 getNode
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 在普通的 bucket 中查找 node
                    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)))) {
                // 找到了 node , 并且符合删除条件
                if (node instanceof TreeNode)
                    // 树结构, 调用树版本的 removeNode , 如果节点过少, 会转换成链表结构
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    // node 是链表的第一个元素
                    tab[index] = node.next;
                else
                    // 不是第一个元素
                    p.next = node.next;
                // 结构变化 modCount + 1
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

    总结

    • HashMap 是一个基于哈希表的装箱了的 Map 的实现; 它的数据结构是一个桶的数组, 桶的结构可能是单向链表或者红黑树, 大部分是链表.
    • table 的容量是2的幂, 因此可以用更高效的位运算替代模运算.
    • HashMap 使用的 hash 值, 并不是 key 的 hashCode()方法所返回的值, 详细还是看上面吧.
    • 一个普通桶中的 bin 的数量超过 TREEIFY_THRESHOLD, 并且 table 的容量大于 MIN_TREEIFY_CAPACITY, 这个桶会被转换成树结构; 如果 bin 数量大于TREEIFY_THRESHOLD , 但 table 容量小于 MIN_TREEIFY_CAPACITY, 会进行扩容.
    • 每次扩容新 table 的容量是老 table 的 2 倍.
    • 扩容时, 会将原来下标为 index 的桶里的 bin 分为高低两个部分, 高的部分放到 newTab[index + oldCap] 上, 低的部分放在原位; 如果某部分的 bin 的个数小于 UNTREEIFY_THRESHOLD 树结构将会转换成链表结构.
    • ... ... (不想写了, 以后再改吧)

    转载于:https://www.cnblogs.com/FJH1994/p/10227048.html

    展开全文
  • hashmap源码阅读

    2018-02-20 10:01:34
    接下来会从以下几个方面介绍 HashMap 源码相关知识: 1、HashMap 存储结构 2、HashMap 各常量、成员变量作用 3、HashMap 几种构造方法 4、HashMap put 及其相关方法 5、HashMap get 及其相关方法 6、HashMap ...

      接下来会从以下几个方面介绍 HashMap 源码相关知识:

      1、HashMap 存储结构

      2、HashMap 各常量、成员变量作用

      3、HashMap 几种构造方法

      4、HashMap put 及其相关方法

      5、HashMap get 及其相关方法

      6、HashMap remove 及其相关方法(暂未理解透彻)

      7、HashMap 扩容方法 resize()

      介绍方法时会包含方法实现相关细节。

      先来看一下 HashMap 的继承图:

      

      HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ,允许多条记录的值为 null 。HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap 方法使 HashMap 具有线程安全的能力,或者使用ConcurrentHashMap 。  

      

      一、HashMap 存储结构

      HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下图所示:

      

      源码中具体实现如下:  

    复制代码
     1  // Node<K,V> 类用来实现数组及链表的数据结构
     2   static class Node<K,V> implements Map.Entry<K,V> {
     3         final int hash; //保存节点的 hash 值
     4         final K key; //保存节点的 key 值
     5         V value; //保存节点的 value 值
     6         Node<K,V> next; //指向链表结构下的当前节点的 next 节点,红黑树 TreeNode 节点中也有用到
     7 
     8         Node(int hash, K key, V value, Node<K,V> next) {
     9             this.hash = hash;
    10             this.key = key;
    11             this.value = value;
    12             this.next = next;
    13         }
    14 
    15         public final K getKey()        { }
    16         public final V getValue()      {  }
    17         public final String toString() { }
    18 
    19         public final int hashCode() {           
    20         }
    21 
    22         public final V setValue(V newValue) {          
    23         }
    24 
    25         public final boolean equals(Object o) {            
    26         }
    27     }
    28     
    29     public class LinkedHashMap<K,V> {
    30           static class Entry<K,V> extends HashMap.Node<K,V> {
    31                 Entry<K,V> before, after;
    32                 Entry(int hash, K key, V value, Node<K,V> next) {
    33                     super(hash, key, value, next);
    34                 }    
    35             }
    36     }    
    37     
    38  // TreeNode<K,V> 继承 LinkedHashMap.Entry<K,V>,用来实现红黑树相关的存储结构
    39     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    40         TreeNode<K,V> parent;  // 存储当前节点的父节点
    41         TreeNode<K,V> left; //存储当前节点的左孩子
    42         TreeNode<K,V> right; //存储当前节点的右孩子
    43         TreeNode<K,V> prev;    // 存储当前节点的前一个节点
    44         boolean red; // 存储当前节点的颜色(红、黑)
    45         TreeNode(int hash, K key, V val, Node<K,V> next) {
    46             super(hash, key, val, next);
    47         }
    48        
    49         final TreeNode<K,V> root() {        
    50         }
    51       
    52         static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {           
    53         }
    54       
    55         final TreeNode<K,V> find(int h, Object k, Class<?> kc) {            
    56         }
    57      
    58         final void treeify(Node<K,V>[] tab) {          
    59         }
    60      
    61         final Node<K,V> untreeify(HashMap<K,V> map) {           
    62         }
    63        
    64         final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
    65                                        int h, K k, V v) {           
    66         }
    67         
    68         final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
    69                                   boolean movable) {          
    70         }
    71 
    72         final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {          
    73         }
    74 
    75         /* ------------------------------------------------------------ */
    76         // Red-black tree methods, all adapted from CLR
    77         // 红黑树相关操作
    78         static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
    79                                               TreeNode<K,V> p) {       
    80         }
    81 
    82         static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
    83                                                TreeNode<K,V> p) {         
    84         }
    85 
    86         static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
    87                                                     TreeNode<K,V> x) {        
    88         }
    89 
    90         static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
    91                                                    TreeNode<K,V> x) {           
    92         }       
    93 
    94         static <K,V> boolean checkInvariants(TreeNode<K,V> t) {          
    95         }
    96 
    97     }
    复制代码

     

      二、HashMap 各常量、成员变量作用  

    复制代码
     1  //创建 HashMap 时未指定初始容量情况下的默认容量   
     2     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
     3 
     4  //HashMap 的最大容量
     5     static final int MAXIMUM_CAPACITY = 1 << 30;
     6 
     7     //HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时,进行 resize() 操作
     8     static final float DEFAULT_LOAD_FACTOR = 0.75f;
     9 
    10     //用来确定何时将解决 hash 冲突的链表转变为红黑树
    11     static final int TREEIFY_THRESHOLD = 8;
    12 
    13     // 用来确定何时将解决 hash 冲突的红黑树转变为链表
    14     static final int UNTREEIFY_THRESHOLD = 6;
    15  
    16     /* 当需要将解决 hash 冲突的链表转变为红黑树时,需要判断下此时数组容量,若是由于数组容量太小(小于 MIN_TREEIFY_CAPACITY )导致的 hash 冲突太多,则不进行链表转变为红黑树操作,转为利用 resize() 函数对 hashMap 扩容 */
    17     static final int MIN_TREEIFY_CAPACITY = 64;
    复制代码

      

    复制代码
     1 //保存Node<K,V>节点的数组
     2  transient Node<K,V>[] table;
     3 
     4 //由 hashMap 中 Node<K,V> 节点构成的 set
     5 transient Set<Map.Entry<K,V>> entrySet;
     6 
     7 //记录 hashMap 当前存储的元素的数量
     8 transient int size;
     9 
    10 //记录 hashMap 发生结构性变化的次数(注意 value 的覆盖不属于结构性变化)
    11 transient int modCount;
    12 
    13 //threshold的值应等于 table.length * loadFactor, size 超过这个值时进行 resize()扩容
    14 int threshold;
    15 
    16 //记录 hashMap 装载因子
    17 final float loadFactor;
    复制代码

     

      三、HashMap 几种构造方法  

    复制代码
     1 //构造方法1,指定初始容量及装载因子
     2 public HashMap(int initialCapacity, float loadFactor) {
     3         if (initialCapacity < 0)
     4             throw new IllegalArgumentException("Illegal initial capacity: " +
     5                                                initialCapacity);
     6         if (initialCapacity > MAXIMUM_CAPACITY)
     7             initialCapacity = MAXIMUM_CAPACITY;
     8         if (loadFactor <= 0 || Float.isNaN(loadFactor))
     9             throw new IllegalArgumentException("Illegal load factor: " +
    10                                                loadFactor);
    11         this.loadFactor = loadFactor;
    12      /* tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂,若指定初始容量为9,则实际 hashMap 容量为16*/
    13      //注意此种方法创建的 hashMap 初始容量的值存在 threshold 中
    14         this.threshold = tableSizeFor(initialCapacity);
    15 }
    16 //tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂
    17 static final int tableSizeFor(int cap) {
    18         int n = cap - 1;
    19         n |= n >>> 1;// >>> 代表无符号右移
    20         n |= n >>> 2;
    21         n |= n >>> 4;
    22         n |= n >>> 8;
    23         n |= n >>> 16;
    24         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    25 }
    26 //构造方法2,仅指定初始容量,装载因子的值采用默认的 0.75
    27 public HashMap(int initialCapacity) {
    28         this(initialCapacity, DEFAULT_LOAD_FACTOR);
    29 }
    30 //构造方法3,所有参数均采用默认值
    31 public HashMap() {
    32         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    33 }
    复制代码

     

      四、HashMap put 及其相关方法

      这部分我觉得是 hashMap 中比较重要的代码,介绍如下:  

    复制代码
     1  //指定节点 key,value,向 hashMap 中插入节点
     2  public V put(K key, V value) {
     3      //注意待插入节点 hash 值的计算,调用了 hash(key) 函数
     4   //实际调用 putVal()进行节点的插入
     5         return putVal(hash(key), key, value, false, true);
     6     }
     7  static final int hash(Object key) {
     8         int h;
     9   /*key 的 hash 值的计算是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销*/
    10         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    11     }
    12 
    13  public void putAll(Map<? extends K, ? extends V> m) {
    14         putMapEntries(m, true);
    15     }
    16  
    17  /*把Map<? extends K, ? extends V> m 中的元素插入到 hashMap 中,若 evict 为 false,代表是在创建 hashMap 时调用了这个函数,例如利用上述构造函数3创建 hashMap;若 evict 为true,代表是在创建 hashMap 后才调用这个函数,例如上述的 putAll 函数。*/
    18 
    19  final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    20         int s = m.size();
    21         if (s > 0) {
    22             /*如果是在创建 hashMap 时调用的这个函数则 table 一定为空*/
    23             if (table == null) { 
    24       //根据待插入的map 的 size 计算要创建的 hashMap 的容量。
    25                 float ft = ((float)s / loadFactor) + 1.0F;
    26                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
    27                          (int)ft : MAXIMUM_CAPACITY);
    28       //把要创建的 hashMap 的容量存在 threshold 中
    29                 if (t > threshold)
    30                     threshold = tableSizeFor(t);
    31             }
    32     //判断待插入的 map 的 size,若 size 大于 threshold,则先进行 resize()
    33             else if (s > threshold)
    34                 resize();
    35             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
    36                 K key = e.getKey();
    37                 V value = e.getValue();
    38                 //实际也是调用 putVal 函数进行元素的插入
    39                 putVal(hash(key), key, value, false, evict);
    40             }
    41         }
    42     }
    43  
    44     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    45                    boolean evict) {
    46         Node<K,V>[] tab; Node<K,V> p; int n, i;
    47         if ((tab = table) == null || (n = tab.length) == 0)
    48             n = (tab = resize()).length;
    49    /*根据 hash 值确定节点在数组中的插入位置,若此位置没有元素则进行插入,注意确定插入位置所用的计算方法为 (n - 1) & hash,由于 n 一定是2的幂次,这个操作相当于
    50  hash % n */
    51         if ((p = tab[i = (n - 1) & hash]) == null)
    52             tab[i] = newNode(hash, key, value, null);
    53         else {//说明待插入位置存在元素
    54             Node<K,V> e; K k;
    55         //比较原来元素与待插入元素的 hash 值和 key 值
    56             if (p.hash == hash &&
    57                 ((k = p.key) == key || (key != null && key.equals(k))))
    58                 e = p;
    59         //若原来元素是红黑树节点,调用红黑树的插入方法:putTreeVal
    60             else if (p instanceof TreeNode)
    61                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    62             else {//证明原来的元素是链表的头结点,从此节点开始向后寻找合适插入位置
    63                 for (int binCount = 0; ; ++binCount) {
    64                     if ((e = p.next) == null) {
    65        //找到插入位置后,新建节点插入
    66                         p.next = newNode(hash, key, value, null);
    67        //若链表上节点超过TREEIFY_THRESHOLD - 1,将链表变为红黑树
    68                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    69                             treeifyBin(tab, hash);
    70                         break;
    71                     }
    72                     if (e.hash == hash &&
    73                         ((k = e.key) == key || (key != null && key.equals(k))))
    74                         break;
    75                     p = e;
    76                 }
    77             }//end else
    78             if (e != null) { // 待插入元素在 hashMap 中已存在
    79                 V oldValue = e.value;
    80                 if (!onlyIfAbsent || oldValue == null)
    81                     e.value = value;
    82                 afterNodeAccess(e);
    83                 return oldValue;
    84             }
    85         }//end else
    86         ++modCount;
    87         if (++size > threshold)
    88             resize();
    89         afterNodeInsertion(evict);
    90         return null;
    91     }//end putval
    复制代码

      

    复制代码
     1        /*读懂这个函数要注意理解 hash 冲突发生的几种情况
     2          1、两节点 key 值相同(hash值一定相同),导致冲突
     3          2、两节点 key 值不同,由于 hash 函数的局限性导致hash 值相同,冲突
     4       3、两节点 key 值不同,hash 值不同,但 hash 值对数组长度取模后相同,冲突
     5       */
     6         final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
     7                                        int h, K k, V v) {
     8             Class<?> kc = null;
     9             boolean searched = false;
    10             TreeNode<K,V> root = (parent != null) ? root() : this;
    11         //从根节点开始查找合适的插入位置(与二叉搜索树查找过程相同)
    12             for (TreeNode<K,V> p = root;;) {
    13                 int dir, ph; K pk;
    14                 if ((ph = p.hash) > h)
    15                     dir = -1; // dir小于0,接下来查找当前节点左孩子
    16                 else if (ph < h)
    17                     dir = 1; // dir大于0,接下来查找当前节点右孩子
    18                 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
    19             //进入这个else if 代表 hash 值相同,key 相同
    20                     return p;
    21           /*要进入下面这个else if,代表有以下几个含义:
    22                   1、当前节点与待插入节点 key 不同, hash 值相同
    23             2、k是不可比较的,即k并未实现 comparable<K> 接口
                  (若 k 实现了comparable<K> 接口,comparableClassFor(k)返回的是k的 class,而不是 null)
    24   或者 compareComparables(kc, k, pk) 返回值为 0
                  (pk 为空 或者 按照 k.compareTo(pk) 返回值为0,
                  返回值为0可能是由于 k的compareTo 方法实现不当引起的,compareTo 判定相等,而上个 else if 中 equals 判定不等)
    */ 25 else if ((kc == null && 26 (kc = comparableClassFor(k)) == null) || 27 (dir = compareComparables(kc, k, pk)) == 0) { 28 //在以当前节点为根的整个树上搜索是否存在待插入节点(只会搜索一次) 29 if (!searched) { 30 TreeNode<K,V> q, ch; 31 searched = true; 32 if (((ch = p.left) != null && 33 (q = ch.find(h, k, kc)) != null) || 34 ((ch = p.right) != null && 35 (q = ch.find(h, k, kc)) != null)) 36                  //若树中存在待插入节点,直接返回 37 return q; 38 } 39              // 既然k是不可比较的,那我自己指定一个比较方式 40 dir = tieBreakOrder(k, pk); 41 }//end else if 42 43 TreeNode<K,V> xp = p; 44 if ((p = (dir <= 0) ? p.left : p.right) == null) { 45             //找到了待插入的位置,xp 为待插入节点的父节点 46             //注意TreeNode节点中既存在树状关系,也存在链式关系,并且是双端链表 47 Node<K,V> xpn = xp.next; 48 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); 49 if (dir <= 0) 50 xp.left = x; 51 else 52 xp.right = x; 53 xp.next = x; 54 x.parent = x.prev = xp; 55 if (xpn != null) 56 ((TreeNode<K,V>)xpn).prev = x; 57             //插入节点后进行二叉树的平衡操作 58 moveRootToFront(tab, balanceInsertion(root, x)); 59 return null; 60 } 61 }//end for 62 }//end putTreeVal   63    64      static int tieBreakOrder(Object a, Object b) { 65 int d; 66 //System.identityHashCode()实际是利用对象 a,b 的内存地址进行比较 67 if (a == null || b == null || 68 (d = a.getClass().getName(). 69 compareTo(b.getClass().getName())) == 0) 70 d = (System.identityHashCode(a) <= System.identityHashCode(b) ? 71 -1 : 1); 72 return d; 73 }
    复制代码

      
      五、HashMap get 及其相关方法
      

    复制代码
     1   public V get(Object key) {
     2         Node<K,V> e;
     3   //实际上是根据输入节点的 hash 值和 key 值利用getNode 方法进行查找
     4         return (e = getNode(hash(key), key)) == null ? null : e.value;
     5     }
     6  
     7  final Node<K,V> getNode(int hash, Object key) {
     8         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
     9         if ((tab = table) != null && (n = tab.length) > 0 &&
    10             (first = tab[(n - 1) & hash]) != null) {
    11             if (first.hash == hash && // always check first node
    12                 ((k = first.key) == key || (key != null && key.equals(k))))
    13                 return first;
    14             if ((e = first.next) != null) {
    15                 if (first instanceof TreeNode)
    16             //若定位到的节点是 TreeNode 节点,则在树中进行查找
    17                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    18                 do {//否则在链表中进行查找
    19                     if (e.hash == hash &&
    20                         ((k = e.key) == key || (key != null && key.equals(k))))
    21                         return e;
    22                 } while ((e = e.next) != null);
    23             }
    24         }
    25         return null;
    26     }
    复制代码

      

    复制代码
     1         final TreeNode<K,V> getTreeNode(int h, Object k) {
     2         //从根节点开始,调用 find 方法进行查找
     3             return ((parent != null) ? root() : this).find(h, k, null);
     4         }
     5  
     6         final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
     7             TreeNode<K,V> p = this;
     8             do {
     9                 int ph, dir; K pk;
    10                 TreeNode<K,V> pl = p.left, pr = p.right, q;
    11          //首先进行hash 值的比较,若不同令当前节点变为它的左孩子或者右孩子
    12                 if ((ph = p.hash) > h)
    13                     p = pl;
    14                 else if (ph < h)
    15                     p = pr;
    16          //hash 值相同,进行 key 值的比较 
    17                 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
    18                     return p;
    19                 else if (pl == null)
    20                     p = pr;
    21                 else if (pr == null)
    22                     p = pl;
    23          //执行到这儿,意味着hash 值相同,key 值不同 
    24            //若k 是可比较的并且k.compareTo(pk) 返回结果不为0可进入下面elseif   
    25                 else if ((kc != null ||
    26                           (kc = comparableClassFor(k)) != null) &&
    27                          (dir = compareComparables(kc, k, pk)) != 0)
    28                     p = (dir < 0) ? pl : pr;
    29                 /*若 k 是不可比较的 或者 k.compareTo(pk) 返回结果为0则在整棵树中进行查找,先找右子树,右子树没有再找左子树*/
    30                 else if ((q = pr.find(h, k, kc)) != null)
    31                     return q;
    32                 else
    33                     p = pl;
    34             } while (p != null);
    35             return null;
    36         }    
    复制代码

        

      七、HashMap 扩容方法 resize()

      resize() 方法中比较重要的是链表和红黑树的 rehash 操作,先来说下 rehash 的实现原理:

      我们在扩容的时候,一般是把长度扩为原来2倍,所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

      

      元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

      

      因此,我们在扩充HashMap的时候,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:

      

      这个算法很巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的槽中了。

      具体源码介绍:

    复制代码
     final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
      /*
            1、resize()函数在size > threshold时被调用。
                oldCap大于 0 代表原来的 table 表非空, oldCap 为原表的大小,
                oldThr(threshold) 为 oldCap × load_factor
         */
            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
            }
        /*
            2、resize()函数在table为空被调用。
            oldCap 小于等于 0 且 oldThr 大于0,代表用户创建了一个 HashMap,但是使用的构造函数为
            HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
            或 HashMap(Map<? extends K, ? extends V> m),导致 oldTab 为 null,oldCap 为0,
            oldThr 为用户指定的 HashMap的初始容量。
          */
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
         /*
                3、resize()函数在table为空被调用。
                oldCap 小于等于 0 且 oldThr 等于0,用户调用 HashMap()构造函数创建的 HashMap,所有值均采用默认值,
              oldTab(Table)表为空,oldCap为0,oldThr等于0,
          */
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;        
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            if (oldTab != null) {
           //把 oldTab 中的节点 reHash 到 newTab 中去
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                //若节点是单个节点,直接在 newTab 中进行重定位
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                //若节点是 TreeNode 节点,要进行 红黑树的 rehash 操作
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //若是链表,进行链表的 rehash 操作
                        else { // preserve order
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do {
                                  next = e.next;
                      //根据算法 e.hash & oldCap 判断节点位置 rehash 后是否发生改变
                                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) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                    // rehash 后节点新的位置一定为原来基础上加上 oldCap
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }        
    复制代码

      

    复制代码
     1      //这个函数的功能是对红黑树进行 rehash 操作
     2     final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
     3             TreeNode<K,V> b = this;
     4             // Relink into lo and hi lists, preserving order
     5             TreeNode<K,V> loHead = null, loTail = null;
     6             TreeNode<K,V> hiHead = null, hiTail = null;
     7             int lc = 0, hc = 0;
     8          //由于 TreeNode 节点之间存在双端链表的关系,可以利用链表关系进行 rehash
     9             for (TreeNode<K,V> e = b, next; e != null; e = next) {
    10                 next = (TreeNode<K,V>)e.next;
    11                 e.next = null;
    12                 if ((e.hash & bit) == 0) {
    13                     if ((e.prev = loTail) == null)
    14                         loHead = e;
    15                     else
    16                         loTail.next = e;
    17                     loTail = e;
    18                     ++lc;
    19                 }
    20                 else {
    21                     if ((e.prev = hiTail) == null)
    22                         hiHead = e;
    23                     else
    24                         hiTail.next = e;
    25                     hiTail = e;
    26                     ++hc;
    27                 }
    28             }
    29             
    30             //rehash 操作之后注意对根据链表长度进行 untreeify 或 treeify 操作
    31             if (loHead != null) {
    32                 if (lc <= UNTREEIFY_THRESHOLD)
    33                     tab[index] = loHead.untreeify(map);
    34                 else {
    35                     tab[index] = loHead;
    36                     if (hiHead != null) // (else is already treeified)
    37                         loHead.treeify(tab);
    38                 }
    39             }
    40             if (hiHead != null) {
    41                 if (hc <= UNTREEIFY_THRESHOLD)
    42                     tab[index + bit] = hiHead.untreeify(map);
    43                 else {
    44                     tab[index + bit] = hiHead;
    45                     if (loHead != null)
    46                         hiHead.treeify(tab);
    47                 }
    48             }//end if
    49         }//end split
    50         
    复制代码

     

      关于 HashMap 源码阅读的相关知识就先介绍到这里,有一些地方我还没有理解透彻(例如红黑树的插入节点之后的平衡操作,删除节点操作),后期会继续补充。


    展开全文
  • Hashmap源码阅读

    2019-09-13 23:26:07
    首先理解HashMap的成员变量作用 HashMap的成员变量分为两个部分,第一部分是static finale修饰的成员变量,和 transient修饰的瞬时变量: //无参构造默认初始化大小 static final int DEFAULT_INITIAL_...
    首先理解HashMap的成员变量作用

    HashMap的成员变量分为两个部分,第一部分是static finale修饰的成员变量,和 transient修饰的瞬时变量:

    	//无参构造默认初始化大小
    	 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        //最大容量,也就是数组最大长度
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        //默认触发resize的加载因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        //链表最大长度,jdk8新特性,链表超过8会转化为红黑树
        static final int TREEIFY_THRESHOLD = 8;
    
        //当树的长度低于这个值时恢复为链表
        static final int UNTREEIFY_THRESHOLD = 6;
    
        //树形化最低容量要求,当table长度低于该值时且链表长度超过阈值触发resize
        static final int MIN_TREEIFY_CAPACITY = 64;
    
    
    HashMap的hash计算原理和为什么需要初始化为2的幂次方

    1.如何使用hash判断key在数组中的位置,主要是以下两个方法

     static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            //将key进行hash后再与hash值无符号右移16位进行异或运算   1、
        }
    
     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)
                ```````
            if ((p = tab[i = (n - 1) & hash]) == null)    //这里使用了数组长度减一和hash进行与位运算 2、
                 ```````
            else {
              ```````
              }
    }
    

    方法1的作用:hashcode值二进制右移16位,把高位特征添加进hash值中,可以是key分布更均匀
    方法2的作用:数组长度一般都是2的幂次方,2^n-1的二进制位上都是1,进行与位运算的结果则是都带有hash的特征,保证了key的均匀分布。

    2.HashMap保证构造时自定义的初始容量为2的幂次方是通过下面这个方法:

    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);
        }
     static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    

    tableSizeFor这个方法会将初始化的值自动转换为大于初始值的第一个2的幂次方。对阈值的计算出现在resize方法里面。介绍resize时再做说明。

    resize()方法

    HashMap触发resize的三种情况:

    • 第一次put操作调用resize初始化
    • 当节点Node数量大于threshold时触发resize
    • 当链表超度超过默认链表长度限制8,且容量小于最小树形化值时,触发resize
     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) {   //	 1.1、判断是否为初始化,>0表示oldTab已经初始化
                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    //	否则扩容一倍
            }
            else if (oldThr > 0) // 	 1.2、如果是自定义初始化容量
                newCap = oldThr;
            else {               // 	 1.3、如果都不是则按默认大小进行初始化
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);		
            }
            threshold = newThr;  	//2、计算出新的阈值
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            if (oldTab != null) {		//3、如果旧表不为空,需要经旧表中的节点复制到新表中
                for (int j = 0; j < oldCap; ++j) {			//循环遍历旧表
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;		// 注意这里将旧表的对应桶制空,以便GC
                        if (e.next == null)				//4.1、桶里只有一个值,直接hash后到新表中
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)		//4.2、如果是红黑树,切分为lower和upper两部分重新对应新表
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order	//4.3、如果是链表,将链表分成两部分,高位
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            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) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead; //4.3、如果是链表,将链表分成两部分,高位的位置正好位于原位置加上扩容之前的容量大小。
                            }
                        }
                    }
                }
            }
            return newTab;
        }
    
    put(Object key)

    put方法最后调用了putVal方法,这里有两个值需要说明下:

    • onlyIfAbsent,源码的注释中解释为,当改值为true时,不会修改原来的value
    • evict,当改值为false时,table处于创建模式,这个值和LinkedHashMap有关,这里不作深究
     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)   //1.1判断是否需要初始化
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)			//1.2put的桶里是否是没有节点
                tab[i] = newNode(hash, key, value, null);
            else {		//1.3put的桶里是否是有节点
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))		//如果key已经存在,且第一个就是
                    e = p;
                else if (p instanceof TreeNode)		//在红黑树中进行put操作
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {		//循环遍历链表,进行put
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // 超过链表最大长度,树形化
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&		
                            ((k = e.key) == key || (key != null && key.equals(k)))) 	//遍历链表
                            break;
                        p = e;
                    }
                }
                if (e != null) { // 替换value,并把旧value返回
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;  //这个值比较有意思,记录HashMap结构修改的次数,源码注释中解释为迭代时用来抛出并发修改异常
            if (++size > threshold)  //size记录了新增节点操作的次数,大于阈值时触发resize。
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    

    put方法可以总结为以下几种情况:

    • 第一次put,触发初始化resize
    • 第n次put,在空槽里put
    • 第n次put,在有值的槽里put
      • put新值且不超过树形化大小
      • 在树里put新值或者旧值
      • 在链表中put 新值或者旧值,put新值时可能会触发初始化
    • 记录总节点 次数,判断是否需要扩容
    get(object key)

    get操作会先把key进行hash计算,再与数字长度与位运算确定槽的位置,再通过比较key的内容获得值。从这里也可以看出,key为对象类型时,为什么需要重写hashCode和equals方法。

    final Node<K,V> getNode(int hash, Object key) {
            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) {
                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 {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }
    
    HashMap的不安全性

    hashmap在多线程下是不安全的,下面是两个例子
    1.在put操作时,线程A和线程B同时put一个hash值一致的key,假设对应槽里没有node,线程A判断没有节点时,时间片交给了B,B也判断没node。最终线程A,B都在槽位的第一个node中放数据,A把B覆盖,或者反之。在get时就可能会出现明明put了这个key,但是没有值的情况
    2.Hashmap在put操作时会用一个变量size记录put次数,而size++这个操作是非原子性的,所以也可能存在put次数超过扩容阈值时,并没有触发扩容。

    多线程环境下可以使用线程安全的HashTable 和ConcurrentHashMap,HashTable方法都使用了 Synchronize修饰,高并发场景下效率会比较低。

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 1,360
精华内容 544
关键字:

hashmap源码阅读