【集合】HashMap

朱雀 2024-04-17 05:37 51阅读 0赞

# 0.前言 #

HashMap是以key/value的方式来储存数据的一种结构，key是唯一的，可以为null，整个类采用数组+链表+红黑树的方式来实现。在查找元素的时候计算key的值，定位到数组下标，所以它的复杂度为O(1)，但是他是非线程安全的，并且也不保证元素的顺序。  
每一个数组成为一个桶，这个桶里存放了一个链表的表头，元素就是存在这个链表中的。  
在查询的时候，计算key的哈希值，通过 **数组长度%key** 从而定位到查询的数组下标。然后在继续沿着数组中的链表来查询。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70]

# 1.属性 #

/** * 这个表示HashMap的默认容量为16，也就是tab数组的容量默认16个长度 */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /** * 这个表示最大容量 */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /** * 负载因子默认0.75，用来计算容量达到多少时进行扩容 */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /** * 当一个桶中链表的元素个数大于等于8，就把这个链表转化为树 */
        static final int TREEIFY_THRESHOLD = 8;
    
        /** * 当一个桶中链表的元素个数小于6，如果之前为树，就把他转化为链表，转化的目的时为了效率，链表查询复杂度为O(n)，树为O(log n) */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /** * 当数组长度大于64时就把这个数组tab也转化为树，这样做也是为了效率 */
        static final int MIN_TREEIFY_CAPACITY = 64;
        /** * 数组，又叫作桶（bucket） */
    	transient Node<K,V>[] table;
    
    	/** * 作为entrySet()的缓存 */
    	transient Set<Map.Entry<K,V>> entrySet;
    
    	/** * 元素的数量 */
    	transient int size;

# 2.构造方法HashMap(); #

![在这里插入图片描述][20190823021025227.png]  
构造方法，先初始化他的负载因子

# 3.添加方法 put(k,v) #

![在这里插入图片描述][20190823110959760.png]

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) { 
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;
        // 如果桶的数量为0，则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            // 调用resize()初始化
            n = (tab = resize()).length;
        // (n - 1) & hash 计算元素在哪个桶中
        // 如果这个桶中还没有元素，则把这个元素放在桶中的第一个位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 新建一个节点放在桶中
            tab[i] = newNode(hash, key, value, null);
        else { 
            // 如果桶中已经有元素存在了
            Node<K, V> e;
            K k;
            // 如果桶中第一个元素的key与待插入元素的key相同，保存到e中用于后续修改value值
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                // 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            else { 
                // 遍历这个桶对应的链表，binCount用于存储链表中元素的个数
                for (int binCount = 0; ; ++binCount) { 
                    // 如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表最后插入一个新节点
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null);
                        // 如果插入新节点后链表长度大于8，则判断是否需要树化，因为第一个元素没有加到binCount中，所以这里-1
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果待插入的key在链表中找到了，则退出循环
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果找到了对应key的元素
            if (e != null) {  // existing mapping for key
                // 记录下旧值
                V oldValue = e.value;
                // 判断是否需要替换旧值
                if (!onlyIfAbsent || oldValue == null)
                    // 替换旧值为新值
                    e.value = value;
                // 在节点被访问后做点什么事，在LinkedHashMap中用到
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 到这里了说明没有找到元素
        // 修改次数加1
        ++modCount;
        // 元素数量加1，判断是否需要扩容
        if (++size > threshold)
            // 扩容
            resize();
        // 在节点插入后做点什么事，在LinkedHashMap中用到
        afterNodeInsertion(evict);
        // 没找到元素返回null
        return null;
    }

# 4.获取元素get() #

![在这里插入图片描述][20190823111244219.png]

final Node<K, V> getNode(int hash, Object key) { 
        Node<K, V>[] tab;
        Node<K, V> first, e;
        int n;
        K k;
        // 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空
        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;
    }

# 5.扩容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) { 
            if (oldCap >= MAXIMUM_CAPACITY) { 
                // 如果旧容量达到了最大容量，则不再进行扩容
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两倍，扩容门槛也扩大为两倍
                newThr = oldThr << 1; // double threshold
        } else if (oldThr > 0) // initial capacity was placed in threshold
            // 使用非默认构造方法创建的map，第一次插入元素会走到这里
            // 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛
            newCap = oldThr;
        else {                // zero initial threshold signifies using defaults
            // 调用默认构造方法创建的map，第一次插入元素会走到这里
            // 如果旧容量旧扩容门槛都是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;
        // 如果旧数组不为空，则搬移元素
        if (oldTab != null) { 
            // 遍历旧数组
            for (int j = 0; j < oldCap; ++j) { 
                Node<K, V> e;
                // 如果桶中第一个元素不为空，赋值给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)
                        // 如果第一个元素是树节点，则把这颗树打散成两颗树插入到新桶中去
                        ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    else {  // preserve order
                        // 如果这个链表不止一个元素且不是一颗树
                        // 则分化成两个链表插入到新的桶中去
                        // 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中
                        // 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
                        // 也就是分化成了两个链表
                        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) == 0的元素放在低位链表中
                            // 比如，3 & 4 == 0
                            if ((e.hash & oldCap) == 0) { 
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else { 
                                // (e.hash & oldCap) != 0的元素放在高位链表中
                                // 比如，7 & 4 != 0
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 遍历完成分化成两个链表了
                        // 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）
                        if (loTail != null) { 
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）
                        if (hiTail != null) { 
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

当添加的元素 大于 负载因子\*数组长度 的时候就会自动进行扩容。扩容将会把容量扩充到原来的2的n次方倍，因为我们在定位一个桶的位置的时候使用(n-1)&数组长度 （相当于对数组长度取余）来定位元素的下标。当扩展为2的n次方倍的时候，原来的元素还在原来的位置上，这样查询功能也还有效。

待续…

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzY18xMjM0NTY_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/98c3dfd80a024a95a53207d43d3eb6f0.png
[20190823021025227.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/b0f5e804aee3455e883c5026f9bad5cb.png
[20190823110959760.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/8b887554d2cf40dc881a6284a1cc7f7c.png
[20190823111244219.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/4cf4c1354b30408d9c2b993d0776f19c.png