HashMap和HashSet(深入HashMap源码分析HashMap元素的存储)

朴灿烈づ我的快乐病毒、 2022-08-21 08:00 173阅读 0赞

前面我们通过继承一个HaseSet把一个Set集合扩展为一个Map。其实我们扩展的Map本质上是一个HashMap。  
HashMap和HashSet之间也有很多相似之处，HashSet采用Hash算法来决定集合元素的存储位置，这样可以保证快速的存，取集合元素。对于HashMap而已，系统仅将value作为key的附属物而已，系统采用Hash算法来决定key的存储位置，这样可以保证快速的存，取集合key，而value仅仅总是作为key的附属。

HashMap<String,Double> map = new HashMap<String,Double>();
    map.put("java",100);

对于如上的代码，当执行map.put(“java”,100);时。系统将调用”java”的hashCode()方法得到其hashCode()值。然后根据hashCode值系统来决定其存储位置。

HashMap类的put(K key,V value)方法源码:

/** 
             * The table, resized as necessary. Length MUST Always be a power of two. 
             */  
            transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;      //用来存储Entry  
    
            final float loadFactor;              //负载因子 当数组容量的占用比例超过负载因子时，数组就会扩容。  
    
            static class Entry<K,V> implements Map.Entry<K,V> {  
                final K key;                        //用来存储Key  
                V value;                            //用来存储Value  
                Entry<K,V> next;                  //用来指向:相同hashCode的Key,但是不同Key对象  
                int hash;                           //Key对象的hashCode值  
    
                /** 
                 * Creates new entry. 
                 */  
                Entry(int h, K k, V v, Entry<K,V> n) {  
                    value = v;  
                    next = n;  
                    key = k;  
                    hash = h;  
                }  
            }  
        }
    
        public V put(K key, V value) {  
                if (table == EMPTY_TABLE) {  
                    inflateTable(threshold);  
                } 
                //当key为null，调用putForNullKey来处理 
                if (key == null)  
                    return putForNullKey(value);  
                    //根据key的hashCode计算hash值
                int hash = hash(key);  
                //搜索制定hash值在对于table中的索引
                int i = indexFor(hash, table.length);
                //如果i处索引不为null。则通过循环不断遍历e元素的下一个元素  
                for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
                    Object k;  
                    //找到指定key与需要放入key相等(即两者hash值相同，equals返回true)
                    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                        V oldValue = e.value;  
                        e.value = value;  
                        e.recordAccess(this);  
                        return oldValue;  
                    }  
                }  
          //如果i索引处的entry为null。表明此次没有entry。直接插入在此次即可
                modCount++;  
          //添加key，value到索引i处
                addEntry(hash, key, value, i);  
                return null;  
            }

上面代码中用到了一个重要的内部接口Map.Entry,每个Map.Entry其实就是一个key-value。从HashMap的源码也可以看出，程序根本没有考虑过Map.Entry中value.而是仅仅考虑key而已，即根据key计算出Entry的存储位置。这也得出一个结论:**完全可以把Map集合中的value当成key的附属物而已，当系统确定了key的存储位置之后，value也就被确定了。**

从HashMap的put方法源代码也可以看出，**当程序试图将一个key-value对放入HashMap中时，首先根据key的hashCode()返回值决定该Entry的存储位置，如果两个key的hash值相同，那么它们的存储位置相同。如果这个两个key的equalus比较返回true。那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖。如果这两个equals返回false，那么这两个Entry会形成一个Entry链，并且新添加的Entry位于Entry链的头部。**

如果key的equals返回true，那么他们两个的hash值一定相同。即当两者的hashCode()相同时，系统再次调用equals来确定是覆盖还是形成Entry链。

上面程序还是调用了addEntry(hash,key,value,i);代码。其中addEntry是HashMap提供的一个包访问权限的方法，该方法仅用于添加一个key-value对。源码如下:

void addEntry(int hash, K key, V value, int bucketIndex) {  
             //获取指定bucketIndex处的Entry
            Entry<K,V> e = table[bucketIndex];
            //将新创建的Entry放入bucketIndex索引处，并让新Entry指向原来的Entry  
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
           //如果Map中的key-value对的数量超过了极限
           if(size++>=threshold){
           //扩充table对象的长度到2倍
            resize(2*table.length);
            }
        }

上述代码有一个非常优雅的设计，系统总是将新添加的Entry对象放在bucketIndex索引处。如果bucketIndex索引处已经有了一个Entry对象。这新添加的Entry指向该Entry(即产生一个Entry链)。如果bucketIndex处没有Entry对象，则说明上述代码e变量为null。即新放入的Entry对象指向null，即没有产生Entry链。