HashMap原理与实现

快来打我* 2022-05-12 14:36 228阅读 0赞

HashMap是基于哈希表的 Map 接口的实现，以key-value的形式存在。系统会根据hash算法来来计算key-value的存储位置，可以通过key快速地存、取value。

HashMap提供了三个构造函数：
        HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
        HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
        HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。

在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

HashMap是一种支持快速存取的数据结构，要了解它的性能必须要了解它的数据结构。

在Java中最常用的两种结构是数组和模拟指针(引用)，几乎所有的数据结构都可以利用这两种来组合实现，HashMap也是如此。实际上HashMap是一个“链表散列”，HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度。如下是它数据结构：

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

#### 存储实现（put） ####

首先判断key是否为null，若为null，则直接调用putForNullKey方法。若不为空则先计算key的hash值，然后根据hash值搜索在table数组中的索引位置:

1.  如果table数组在该位置处有元素，则比较key是否相同：  
    相同则覆盖原来的value（HashMap中没有相同的key）  
    不相同则将该元素保存在链头（最先保存的元素放在链尾）
2.  若table在该处没有元素，则直接保存。

hash方法，该方法为一个纯粹的数学计算，就是计算h的hash值。

static int hash(int h) {
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
    }

我们知道对于HashMap的table而言，数据分布需要均匀（最好每项都只有一个元素，这样就可以直接找到），不能太紧也不能太松，太紧会导致查询速度慢，太松则浪费空间。计算hash值后，怎么才能保证table元素分布均与呢？我们会想到取模，但是由于取模的消耗较大，HashMap是这样处理的：调用indexFor方法。

static int indexFor(int h, int length) {
            return h & (length-1);
        }

HashMap的底层数组长度总是2的n次方，在构造函数中存在：capacity <<= 1;这样做总是能够保证HashMap的底层数组长度为2的n次方。当length为2的n次方时，h&(length - 1)就相当于对length取模，而且速度比直接取模快得多，这是HashMap在速度上的一个优化。至于为什么是2的n次方下面解释。

我们回到indexFor方法，该方法仅有一条语句：h&(length - 1)，这句话除了上面的取模运算外还有一个非常重要的责任：均匀分布table数据和充分利用空间。

#### 读取实现：get(key) ####

相对于HashMap的存而言，取就显得比较简单了。通过key的hash值找到在table数组中的索引处的Entry，然后返回该key对应的value即可。

#### 扩容问题 ####

随着HashMap中元素的数量越来越多，发90生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响HashMap的速度，为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度\*加载因子。但是扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

#### 冲突 ####

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时，系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。源码如下:

判断当前索引位置是否存在相同hashcode和相同key的元素

1.  如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。
2.  如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同:  
    如果key不相同，这时就是产生了hash冲突。Hash冲突后，那么HashMap的单个桶bucket里存储的不是一个 Entry，而是一个 Entry 链。 系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止。如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中）， 那系统必须循环到最后才能找到该元素。
    
        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;  
                 //
                 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;  
         }

[70]: /images/20220504/788d6046d34f46eeaa1c7b3cca3a52ad.png