HashMap原理及冲突解决办法

Love The Way You Lie 2022-05-09 15:20 300阅读 0赞

class HashMap<K,V> extends AbstractMap<K,V>

*  HashMap  put()
 *  HashMap  get()

**1.put()**

HashMap put()方法源码如下：

public V put(K key, V value) {
    
            if (key == null)  
                return putForNullKey(value);  
            int hash = hash(key.hashCode());  
            int i = indexFor(hash, table.length);  
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
                Object k;  
                //判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。  
                //如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果不相同，这时就是产生了hash冲突。  
                //Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。  
                //系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），  
                //那系统必须循环到最后才能找到该元素。  
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                    V oldValue = e.value;  
                    e.value = value;  
                    return oldValue;  
                }  
            }  
            modCount++;  
            addEntry(hash, key, value, i);  
            return null;  
        }

hash值冲突是发生在put()时，从源码可以看出，hash值是通过hash(key.hashCode())来获取的，当put的元素越来越多时，难免或出现不同的key产生相同的hash值问题，也即是hash冲突，当拿到一个hash值，通过indexFor(hash, table.length)获取数组下标，先查询是否存在该hash值，若不存在，则直接以Entry<V,V>的方式存放在数组中，若存在，则再对比key是否相同,若hash值和key都相同，则替换value，若hash值相同，key不相同，则形成一个单链表，将hash值相同，key不同的元素以Entry<V,V>的方式存放在链表中，这样就解决了hash冲突，这种方法叫做**分离链表法**，与之类似的方法还有一种叫做 **开放定址法**，开放定址法师采用线性探测（从相同hash值开始，继续寻找下一个可用的槽位）hashMap是数组，长度虽然可以扩大，但用线性探测法去查询槽位查不到时怎么办？因此hashMap采用了分离链表法。

**2.get()**

**　　**

public V get(Object key) { 
        if (key == null) 
            return getForNullKey(); 
        int hash = hash(key.hashCode()); 
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {     
            Object k;             
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
                return e.value;  
        }
        return null; 
    }

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

当hashMap没出现hash冲突时，没有形成单向链表，get方法能够直接定位到元素，但是，出现冲突后，形成了单向链表，bucket里存放的不再是一个entry对象，而是一个entry对象链，系统只能顺序的遍历每个entry直到找到想要搜索的entry为止，这时，问题就来了，如果恰好要搜索的entry位于该entry链的最末端，那循环必须要进行到最后一步才能找到元素，此时涉及到一个**负载因子**的概念，hashMap默认的负载因子为0.75，这是考虑到**存储空间**和**查询时间**上成本的一个折中值，增大负载因子，可以减少hash表（就是那个entry数组）所占用的内空间，但会增加查询数据的时间开销，而查询是最频繁的操作（put()和get()都用到查询）；减小负载因子，会提高查询时间，但会增加hash表所占的内存空间。

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

**3.hashMap数组扩容**

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小\*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16\*0.75=12的时候，就把数组的大小扩展为 2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，扩容是需要进行数组复制的，复制数组是非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。