HashMap的存储以及源码分析

快来打我* 2023-10-11 13:59 2阅读 0赞

### HashMap的存储 ###

**HashMap的存储结构示意图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70]  
在JDK1.8以后，在执行HashMap的第一个put方法时会初始化一个长度为16的Node数组。而数组中又是保存了一个链表的地址，当某一个key经过hash算法得到其hashCode，再对数组的长度取模运算，就可以得到该键值对存放的下标位置。

public class HashMapTest {
        
    
        public static void main(String[] args) {
        
    
            String str1 = "Hello";
            String str2 = "world";
            String str3 = "Aa";
            String str4 = "BB";
    
            System.out.println(str1.hashCode());
            System.out.println(str2.hashCode());
            System.out.println(str3.hashCode());
            System.out.println(str4.hashCode());
            
        }
    
    }

以上字符串的hashCode：  
![在这里插入图片描述][20200622141303472.png]  
可以发现Aa和BB这两个字符串的hashCode值是相同的，当在存储Aa的时候，Aa的hashCode值2112对16取模结果为10，则Aa这个键值对就直接存在了下标数组下标10的链表中，因为此时在存Aa的时候，该下标是没有任何元素的，可以直接存储。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70 1]  
如果在继续存放BB的时候，则发现该位置已经有元素了，那么在存储的时候，首先将BB这个key的hashCode与该条链表上的元素的hashCode比较：1.如果发现与链表上的元素的hashCode值不相同，则直接插入。2.如果发现hashCode相同，则再调用equals()方法进行两者的比较，如果还是相同，则`只能说明这两个key是同一个key`，就将后插入的值，覆盖先插入的值，如果equals()方法发现不相同，则将BB这个key插入。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70 2]

### HashMap源码 ###

**无参构造方法**

public HashMap() {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

在JDK1.8以后，使用无参构造方法时并不会初始化容量，而是在put的时候会初始化容量。

**默认加载因子**

static final float DEFAULT_LOAD_FACTOR = 0.75f;

当 map的size > 数组容量 \* 默认加载因子时，此时就需要扩容。

*为什么默认加载因子为0.75，而不是像ArrayList那样什么时候满了什么时候再扩容？*

原因是由于不同的hash值取模以后可能会得到相同的值，那这样的话可能有的数组下标的链表就会很长，而有的数组下标的值可能就会为null，也就是说，虽然容量是16，但不能保证这16个数组下标都有值（例如下图），所以为了提高查找效率，当size为容量的0.75倍的时候就进行了扩容。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70 3]  
*既然是为了提高效率，为什么不把加载因子设为更小的值？*  
1） 会频繁进行扩容，给内存造成一定压力  
2）如果默认加载因子越小，则意味着内存空间浪费的可能越多

**put方法**

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }

可以看到put方法其实是调用的putVal方法  
再看一下这个hash方法

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

可以看到，hash方法返回的并不完全是key对象的hashCode值，在其内部也进行了一些异或运算。

**putVal方法**  
*当第一次添加元素的时候，先通过resize方法进行初始化，再根据`（n-1）& hash`判断要存储的下标位置有没有元素（`（n-1）& hash这个与运算得出这个要存储元素的下标位置`），如果`p = tab[i = (n - 1) & hash]) == null`这个下标位置为null，那说明没有元素，直接可以插入，否则进入else，判断p的hash值是否和存储的元素的hash一样`p.hash == hash`如果相同，且p这个节点的key和要存储的key相同，则进行了替换`e = p;`如果与p节点的hash不相同，则进入TreeNode红黑树判断，此处不考虑该情况，则进入else，进入else继续判断p.next的节点是否为null`(e = p.next) == null`如果为null，则新创建了一个元素插入，如果不为p.next不为null，说明该链表不止只有一个元素，则继续比较`((k = e.key) == key || (key != null && key.equals(k))))`，最后再将e赋给p，再继续p.next判断`p = e;`整个大概的逻辑就是：判断p的next下一个节点是否为null，为null就创建一个新的节点，并将这个节点赋值为p.next，如果不为e=p.next不为null，则将e的hash和e的key的equals方法的与新插入的key进行比较，如果相同了则替换该位置的value，如果不相同，则继续将e赋值为p，进行p.next。*

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //由于没有在构造器中初始化table，所以table为null，if成立，进入reseize方法，resize方式主要是构建了一个长度为16的数组
            if ((tab = table) == null || (n = tab.length) == 0)			//将初始化数组的长度赋给n
                n = (tab = resize()).length;
            //判断要插入的下标是不是null，如果为null，则说明还没有任何元素插入，则直接插入。
            if ((p = tab[i = (n - 1) & hash]) == null)
                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))))
                    e = p;
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        
                    for (int binCount = 0; ; ++binCount) {
        
                        if ((e = p.next) == null) {
        
                            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))))
                            break;
                        p = e;
                    }
                }
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

**resize方法部分**

final Node<K,V>[] resize() {
        
            Node<K,V>[] oldTab = table;
            //首次添加table为null，三元运算符成立，所以oldCap为0
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            //oldThr也为0，threshold初始默认为0
            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
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {
                       // zero initial threshold signifies using defaults
            	//首次执行，指定了新容量为16
                newCap = DEFAULT_INITIAL_CAPACITY;
                //临界值为 16 * 0.75 = 12
                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);
            }
            //将新的临界值赋给了this
            threshold = newThr;
            @SuppressWarnings({
        "rawtypes","unchecked"})
            //真正的构建了容量为16的数值
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
             //赋给this.table
            table = newTab;

**treeifyBin方法**  
该方法主要是判断是否将某链表转变为红黑树，从而提高查找效率。注意：当链表的长度大于8时不一定转为红黑树，只有当链表长度大于8，且整个数组的长度大于64的时候，才会将该链表的结构转为红黑树。

static final int MIN_TREEIFY_CAPACITY = 64;//最小转换红黑树容量

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();

可以看到以上代码的判断逻辑，如果table为null，或者table的length小于64的话，会进行扩容操作，而不是转换为红黑树。

**原因：如果数组的容量小于64的话，可能会由于hash算法的原因导致某条链表特别长，那么此时会先使用resize方法进行扩容，当长度超过64时，就可以转换为红黑树了**

final void treeifyBin(Node<K,V>[] tab, int hash) {
        
            int n, 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);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020062214075785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2,size_16,color_FFFFFF,t_70
[20200622141303472.png]: https://img-blog.csdnimg.cn/20200622141303472.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200622142034758.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200622143240338.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200622144556829.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzUwNjU2,size_16,color_FFFFFF,t_70