HashMap的源码学习(jdk8)

╰半橙微兮° 2024-03-22 11:05 24阅读 0赞

> hashmap的源码学习了，做个笔记

#### hashmap中的一些属性 ####

transient Node<K, V>[] table; // 数组,存放的为Node<K,V>
    	
    	int threshold; // 扩容的阈值,当前数组长度*扩容因子
    	final float loadFactor; // 扩容因子
    
    	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的大小 16
    
        static final int MAXIMUM_CAPACITY = 1 << 30; // 数组的最大空间
        /**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认的负载因子大小
    
        static final int TREEIFY_THRESHOLD = 8; // 树化,链表需要达到阈值
    
        static final int UNTREEIFY_THRESHOLD = 6; // 退化为链表的阈值
    
        static final int MIN_TREEIFY_CAPACITY = 64; // 树化,数组需要达到的阈值

### hashmap中的链表Node<K,V> ###

// 由代码可知此链表为单向的链表
    	static class Node<K, V> implements Map.Entry<K, V> {
        
            final int hash; // 根据hash(key)计算出来的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;
            }
    
            public final int hashCode() {
        
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
        
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {
        
                if (o == this) {
        
                    return true;
                }
                if (o instanceof Map.Entry) {
        
                    Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                    if (Objects.equals(key, e.getKey()) &&
                            Objects.equals(value, e.getValue())) {
        
                        return true;
                    }
                }
                return false;
            }
        }

### put()方法 ###

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }
    	final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        
            Node<K, V>[] tab;
            Node<K, V> p;
            int n, i;
    
            // eg1: table=null
            /** 如果是空的table，那么默认初始化一个长度为16的Node数组*/
            if ((tab = table) == null || (n = tab.length) == 0) {
        
                // eg1: resize返回(Node<K, V>[]) new Node[16]，所以：tab=(Node<K, V>[]) new Node[16]， n=16
                n = (tab = resize()).length;
            }
    
            /** 如果计算后的下标i，在tab数组中没有数据，那么则新增Node节点*/
            if ((p = tab[i = (n - 1) & hash]) == null) {
        
                // eg1: tab[0] = newNode(0, 0, "a0", null)
                // eg2: tab[1] = newNode(1, 1, "a1", null)
                tab[i] = newNode(hash, key, value, null);
            } else {
         /** 如果计算后的下标i，在tab数组中已存在数据，则执行以下逻辑 */
                Node<K, V> e;
                K k;
                // 判断key是否相等
                if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
         /** 如果与已存在的Node是相同的key值*/
                    e = p;
                }
              
                // 判断是树还是链表
                else if (p instanceof TreeNode) {
         /** 如果与已存在的Node是相同的key值，并且是树节点*/
                    e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                } else {
         /** 如果与已存在的Node是相同的key值，并且是普通节点，则循环遍历链式Node，并对比hash和key，如果都不相同，则将新的Node拼装到链表的末尾。如果相同，则进行更新。*/
                    for (int binCount = 0; ; ++binCount) {
        
                        
                        /** 获得p节点的后置节点，赋值给e。直到遍历到横向链表的最后一个节点，即：该节点的next后置指针为null */
                        if ((e = p.next) == null) {
        
                            // eg3: p.next = newNode(16, 16, "a16", null);
                            // eg4-loop2: p.next == newNode(32, 32, "a32", null);
                            // eg6: p.next == newNode(128, 128, "a128", null);
                            p.next = newNode(hash, key, value, null);
    
                            // eg3: binCount == 0
                            // eg4-loop2: binCount == 1
                            /** 是否要树化 ,binCount从0开始，横向链表中第2个node对应binCount=0，如果Node链表大于8个Node，那么试图变为红黑树 */
                            if (binCount >= TREEIFY_THRESHOLD - 1) {
        
                                // eg6: tab={newNode(0, 0, "a0", ［指向后面1个链表中的7个node］), newNode(1, 1, "a1", null)}, hash=128
                                treeifyBin(tab, hash); // 树化
                            }
                         
                            break;
                        }
                        // eg4-loop1: e.hash==16 hash==32 所以返回false
                        /** 更新操作,针对链表中的每个节点，都来判断一下，是否待插入的key与已存在的链表节点相同，如果相同，则跳出循环，并在后续的操作中，将该节点内容更新为最新的插入值 */
                        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
        
                            break;
                        }
                        
                        p = e;
                    }
                }
    
                // 更新的操作
                /** 如果存在相同的key值*/
                if (e != null) {
        
                   
                    V oldValue = e.value;
                    // onlyIfAbsent=false,HashMap初始化的参数,判断是否是不能修改,默认是false
                    if (!onlyIfAbsent || oldValue == null) {
        
                        
                        /** 则将新的value值进行更新*/
                        e.value = value;
                    }
                    afterNodeAccess(e); /** doing nothing */
                    //  返回oldValue
                    return oldValue;
                }
            }
    
            ++modCount; // 好像是并发用的
    
            // eg4: size=8, threshold=12
            if (++size > threshold) {
        
                resize();
            }
            afterNodeInsertion(evict); /** doing nothing */
            return null;
        }

#### get()方法 ####

public V get(Object key) {
        
            Node<K, V> e;
            // getNode(hash(key),key)得到对应的Node节点,在e.value获得值
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
        // 这个操作我认为就是两点,一个是链表遍历查找,一个红黑树遍历查找
    	final Node<K, V> getNode(int hash, Object key) {
        
            Node<K, V>[] tab;
            Node<K, V> first;
            Node<K, V> e;
            int n;
            K k;
            /**利用hash&(n-1)计算出数组下标 ,table存在元素 并且根据hash寻址后的下标位置也有元素存在 */
            if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        
                /** hash值相同，并且key值也相同。真幸运，第一个元素就是待寻找的元素！！！ */
                if (first.hash == hash &&  ((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;
        }

> 总结一下,put()方法直接调用putVal(hash(key,key,value,false.true))方法，  
> hash（key）这个方法是计算一个hash值出来，主要的是它的函数扰动，也就是 (h = key.hashCode()) ^ (h >>> 16)，用key的hashcode（）和自己的高16位做异或运算，这样的好处是，使用这个值分布的更加分散，减少哈希冲突的出现。  
> 在putVal方法中：  
> 判断tab是不是null，长度是否为0，如果是那就扩容成初始大小16.  
> 计算出这个key应该放入的数组下标，计算方法是：用hash（key）与数组大小减一做与运算，这样可以保证计算出来的值在数组大小之内（之所以不采用模运算，是因为‘与运算‘的效率是要高于模运算的）。  
> 下标计算出来之后，判断下标处，是否已经有值，如果没有，便直接生成一个Node对象，放在这个位置。  
> 这个位置有值，需要比较一下，key是否是相等的，如果是则做更新操作。  
> 如果key的值不相等，那这可能就是那就要开始遍历,一种是遍历链表,一种是遍历红黑树。  
> 遍历链表的话，就是比较key是否和链表上的key相等，如果没有相等的key，则尾插法，插入到链表中，如果有相等的key，将会和上面的走一样的更新操作。  
> 遍历红黑树的话，就比较麻烦了，从根节点开始遍历，查找是否有和key相等的存在，存在便是更新操作，不存在则是将数据添加到红黑树的节点上，再做树的自旋操作，让树保持红黑树的特性。最好还要保证root节点放在数组中。  
> get()方法,主要是先通过调用hash()方法计算出hash值,确定key在数组中的下标,之后进行key的比较,如果下标位置的key相同,则直接返回这个Node节点,得到value值.  
> 若是不相等,下一步则是遍历链表或者遍历红黑树（first instanceof TreeNode判断是红黑树还是链表）,找到对应的Node节点,并返回。

本人对HashMap的源码理解有限，如有错误还望大家不吝赐教。