【Java基础】——HashMap设计原理&实现分析

左手的ㄟ右手 2022-07-18 01:09 278阅读 0赞

HashMap在Java开发中有着非常重要的角色地位，每一个Java程序员都应该了解HashMap。

本文主要从源码角度来解析HashMap的设计思路，并且详细地阐述HashMap中的几个概念，并深入探讨HashMap的内部结构和实现细节，讨论HashMap的性能问题，并且在文中贯穿着一些关于HashMap常见问题的讨论。

> **读完本文，你会了解到：**   1. HashMap的设计思路和内部结构组成
> 
>       2. HashMap中的一些概念： 什么是阀值？为什么会有阀值？什么是加载因子？它们有什么作用？
> 
>       3. HashMap的性能问题以及使用事项
> 
>       4. HashMap的源码实现解析
> 
>       5. 为什么JDK建议我们重写Object.equals(Object obj)方法时，需要保证对象可以返回相同的hashcode值？  
> 
> 
>   
>

### 1. HashMap设计思路以及内部结构组成 ###

> HashMap设计思路 
> 
>      **Map<K,V>**是一种以**键值对**存储数据的容器，而**HashMap**则是借助了键值**Key**的**hashcode**值来组织存储，使得可以非常快速和高效地地根据键值key进行数据的存取。
> 
>      对于键值对**<Key,Value>**，**HashMap**内部会将其封装成一个对应的**Entry<Key,Value>**对象，即**Entry<Key,Value>**对象是键值对**<Key,Value>**的组织形式；  
> 
> 
>      对于每个对象而言，JVM都会为其生成一个**hashcode**值。**HashMap**在存储键值对**Entry<Key,Value>**的时候，会根据**Key**的**hashcode**值，以某种映射关系，决定应当将这对**键值对Entry<Key,Value>**存储在**HashMap**中的什么位置上；
> 
>      当通过**Key**值取数据的时候，然后根据**Key**值的**hashcode**，以及内部映射条件，直接定位到**Key**对应的**Value**值存放在什么位置，可以非常高效地将**Value**值取出。
> 
>        
>

> 为了实现上述的设计思路，在**HashMap**内部，采用了**数组+链表**的形式来组织键值对**Entry<Key,Value>**。  
> 
> 
> **HashMap**内部维护了一个**Entry\[\] table **数组，当我们使用** new HashMap()**创建一个**HashMap**时，**Entry\[\] table **的默认长度为16。**Entry\[\] table**的长度又被称为这个**HashMap**的**容量（capacity）**；
> 
> 对于**Entry\[\] table**的每一个元素而言，或为**null**，或为由若干个**Entry<Key,Value>**组成的链表。HashMap中**Entry<Key,Value>**的数目被称为**HashMap**的**大小(size)**;
> 
> **Entry\[\] table**中的某一个元素及其对应的**Entry<Key,Value>**又被称为**桶(bucket)**;     
> 
> 其结构如下图所示：  
>

> ![20141130134720355][]  
>

HashMap内部组织结构由上图所示，现在来看一下HashMap的基本工作流程：

### 2. 什么是阀值？为什么会有阀值？什么是加载因子？它们有什么作用？ ###

**HashMap**设计的初衷，是为了尽可能地迅速根据**Key**的**hashCode**值, 直接就可以定位到对应的**Entry<Key,Value>**对象，然后得到**Value**。

请读者考虑这样一个问题：

>       当我们使用** HashMap map = new HashMap()**语句时，我们会创建一个**HashMap**对象，它内部的** Entry\[\] table**的大小为** 16**，我们假定**Entry\[\] table**的大小会改变。现在，我们现在向它添加**160**对**Key**值完全不同的键值对**<Key,Value>**，那么，该**HashMap**内部有可能下面这种情况：即对于每一个桶中的由**Entry<Key,Value>**组成的链表的长度会非常地长！我们知道，**对于查找链表操作的时间复杂度是很高的，为O(n)**。这样的一个**HashMap**的性能会很低很低，如下图所示：

> ![20141128145931557][]

> 现在再来分析一下这个问题，当前的**HashMap**能够实现：
> 
>      1. 根据**Key**的**hashCode**，可以直接定位到存储这个**Entry<Key,Value>**的桶所在的位置，**这个时间的复杂度为O(1)；**
> 
>      2. 在桶中查找对应的**Entry<Key,Value>**对象节点，需要遍历这个桶的**Entry<Key,Value>**链表，**时间复杂度为O(n);**
> 
>    那么，现在，我们应该尽可能地将第2个问题的时间复杂度**o(n)**降到最低，读者现在是不是有想法了：我们应该要求桶中的链表的长度越短越好！桶中链表的长度越短，所消耗的查找时间就越低，最好就是一个桶中就一个**Entry<Key,Value>**对象节点就好了！
> 
>      这样一来，桶中的**Entry<Key,Value>**对象节点要求尽可能第少，这就要求，**HashMap**中的桶的数量要多了。
> 
>      我们知道，**HashMap**的桶数目，即**Entry\[\] table**数组的长度，由于数组是内存中连续的存储单元，它的空间代价是很大的，但是它的随机存取的速度是Java集合中最快的。我们增大桶的数量，而减少**Entry<Key,Value>**链表的长度，来提高从**HashMap**中读取数据的速度。这是典型的拿空间换时间的策略。
> 
>       但是我们不能刚开始就给**HashMap**分配过多的桶(即Entry\[\] table 数组起始不能太大)，这是因为数组是连续的内存空间，它的创建代价很大，况且我们不能确定给**HashMap**分配这么大的空间，它实际到底能够用多少，为了解决这一个问题，**HashMap**采用了根据实际的情况，动态地分配桶的数量。  
> 
> 
>      
> 
> **HashMap**的权衡策略
> 
>    要动态分配桶的数量，这就要求要有一个权衡的策略了，**HashMap**的权衡策略是这样的：
> 
>             *** 如果***
> 
>                          **HashMap**的大小**>** **HashMap**的容量(即Entry\[\] table的大小)**\***加载因子(经验值0.75)  
> 
> 
>                ***则***
> 
>                          **HashMap**中的Entry\[\] table 的容量扩充为当前的一倍；
> 
>                         然后重新将以前桶中的Entry<Key,Value>链表重新分配到各个桶中
> 
>   
> 
> 
> 上述的  **HashMap的容量(即Entry\[\] table的大小) \* 加载因子(经验值0.75)**就是所谓的**阀值**(**threshold**)：

![20141128155624016][]

**     最后，请读者看一个实例：**

默认创建的*HashMap map =new HashMap();**map*的容量是** 16**，那么，当我们往* map*中添加第几个完全不同的键值对**<Key,Value>**时，**HashMap**的容量会扩充呢？

呵呵，很简单的计算：由于默认的加载因子是**0.75** ，那么，此时*map*的阀值是 **16\*0.75 = 12**，即添加第**13** 个键值对**<Key,Value>**的时候，*map*的容量会扩充一倍。

这时候读者可能会有疑问：本来**Entry\[\] table**的容量是**16**，当放入**12**个键值对**<Key,Value>**后，不是至少还剩下**4个Entry\[\] table **元素没有被使用到吗？这不是浪费了宝贵的空间了吗？！   确实如此，但是为了尽可能第减少桶中的Entry<Key,Value>链表的长度，以提高HashMap的存取性能，确定的这个经验值。如果读者你对存取效率要求的不是太高，想省点空间的话，你可以new HashMap(int initialCapacity, float loadFactor)构造方法将这个因子设置得大一些也无妨。

### 2. HashMap的算法实现解析    ###

HashMap的算法实现最重要的两个是put() 和get() 两个方法，下面我将分析这两个方法：

> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain]
> 
> 1.  **public** V put(K key, V value);  
> 2.  **public** V get(Object key);

另外，HashMap支持Key值为null 的情况，我也将详细地讨论这个问题。

####     1. 向HashMap中存储一对键值对**<Key,Value>**流程---put()方法实现：    ####

> **put()方法-向HashMap存储键值对<Key,Value>**
> 
> a.  获取这个Key的hashcode值，根据此值确定应该将这一对键值对存放在哪一个桶中，即确定要存放桶的索引；
> 
> b.  遍历所在桶中的Entry<Key,Value>链表，查找其中是否已经有了以Key值为Key存储的Entry<Key,Value>对象，
> 
> c1. 若已存在，定位到对应的Entry<Key,Value>,其中的Value值更新为新的Value值；返回旧值；
> 
> c2. 若不存在，则根据键值对<Key,Value> 创建一个新的Entry<Key,Value>对象，然后添加到这个桶的Entry<Key,Value>链表的头部。  
> 
> 
> d.  当前的HashMap的大小(即Entry<key,Value>节点的数目)是否超过了阀值，若超过了阀值(threshold)，则增大HashMap的容量(即Entry\[\] table 的大小)，并且重新组织内部各个Entry<Key,Value>排列。
> 
> 详细流程如下列的代码所示：

> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  /\*\* 
> 2.   \* 将<Key,Value>键值对存到HashMap中，如果Key在HashMap中已经存在，那么最终返回被替换掉的Value值。 
> 3.   \* Key 和Value允许为空 
> 4.   \*/  
> 5.  **public** V put(K key, V value) \{  
> 6.        
> 7.      //1.如果key为null，那么将此value放置到table\[0\],即第一个桶中  
> 8.      **if** (key == **null**)  
> 9.          **return** putForNullKey(value);  
> 10.     //2.重新计算hashcode值，  
> 11.     **int** hash = hash(key.hashCode());  
> 12.     //3.计算当前hashcode值应当被分配到哪一个桶中，获取桶的索引  
> 13.     **int** i = indexFor(hash, table.length);  
> 14.     //4.循环遍历该桶中的Entry列表  
> 15.     **for** (Entry<K,V> e = table\[i\]; e != **null**; e = e.next) \{  
> 16.         Object k;  
> 17.         //5. 查找Entry<Key,Value>链表中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,  
> 18.         //已经存在,则将Value值覆盖到对应的Entry<Key,Value>对象节点上  
> 19.         **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{ //请读者注意这个判定条件，非常重要！！！  
> 20.             V oldValue = e.value;  
> 21.             e.value = value;  
> 22.             e.recordAccess(**this**);  
> 23.             **return** oldValue;  
> 24.         \}  
> 25.     \}  
> 26.     modCount++;  
> 27.     //6不存在，则根据键值对<Key,Value> 创建一个新的Entry<Key,Value>对象，然后添加到这个桶的Entry<Key,Value>链表的头部。  
> 28.     addEntry(hash, key, value, i);  
> 29.     **return** **null**;  
> 30. \}  
> 31.   
> 32. /\*\* 
> 33.  \* Key 为null,则将Entry<null,Value>放置到第一桶table\[0\]中 
> 34.  \*/  
> 35. **private** V putForNullKey(V value) \{  
> 36.     **for** (Entry<K,V> e = table\[0\]; e != **null**; e = e.next) \{  
> 37.         **if** (e.key == **null**) \{  
> 38.             V oldValue = e.value;  
> 39.             e.value = value;  
> 40.             e.recordAccess(**this**);  
> 41.             **return** oldValue;  
> 42.         \}  
> 43.     \}  
> 44.     modCount++;  
> 45.     addEntry(0, **null**, value, 0);  
> 46.     **return** **null**;  
> 47. \}  
> 
>   
> 
> 
> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  /\*\* 
> 2.   \* 根据特定的hashcode 重新计算hash值， 
> 3.   \* 由于JVM生成的的hashcode的低字节(lower bits)冲突概率大，（JDK只是这么一说，至于为什么我也不清楚） 
> 4.   \* 为了提高性能，HashMap对Key的hashcode再加工，取Key的hashcode的高字节参与运算 
> 5.   \*/  
> 6.  **static** **int** hash(**int** h) \{  
> 7.      // This function ensures that hashCodes that differ only by  
> 8.      // constant multiples at each bit position have a bounded  
> 9.      // number of collisions (approximately 8 at default load factor).  
> 10.     h ^= (h >>> 20) ^ (h >>> 12);  
> 11.     **return** h ^ (h >>> 7) ^ (h >>> 4);  
> 12. \}  
> 13.   
> 14. /\*\* 
> 15.  \* 返回此hashcode应当分配到的桶的索引 
> 16.  \*/  
> 17. **static** **int** indexFor(**int** h, **int** length) \{  
> 18.     **return** h & (length-1);  
> 19. \}

> **当HashMap的大小大于阀值时，HashMap容量的扩充算法** 当当前的HashMap的大小大于阀值时，HashMap会对此HashMap的容量进行扩充，即对内部的Entry\[\] table 数组进行扩充。  
> HashMap对容量（Entry\[\] table数组长度） 有两点要求：  
> 
> 
> > *1. 容量的大小应当是 2的N次幂；  
> > 2. 当容量大小超过阀值时，容量扩充为当前的一倍；*  
> > 
> 
> 这里第2点很重要,如果当前的HashMap的容量为16，需要扩充时，容量就要变成16\*2 = 32,接着就是32\*2=64、64\*2=128、128\*2=256.........可以看出，容量扩充的大小是呈指数级的级别递增的。
> 
>     这里容量扩充的操作可以分为以下几个步骤：
> 
>     *   1. 申请一个新的、大小为当前容量两倍的数组；*
> 
> *     2.  将旧数组的Entry\[\] table中的链表重新计算hash值，然后重新均匀地放置到新的扩充数组中；*
> 
> *     3.  释放旧的数组；*
> 
> 由上述的容量扩充的步骤来看，一次容量扩充的代价非常大，所以在容量扩充时，扩充的比例为当前的一倍，这样做是尽量减少容量扩充的次数。
> 
> **为了提高HashMap的性能：**
> 
>               * 1.在使用HashMap的过程中，你比较明确它要容纳多少Entry<Key,Value>，你应该在创建HashMap的时候直接指定它的容量；*
> 
> *               2. 如果你确定HashMap的使用的过程中，大小会非常大，那么你应该控制好 加载因子的大小，尽量将它设置得大些。避免Entry\[\] table过大，而利用率觉很低。*
> 
> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  /\*\* 
> 2.   \* Rehashes the contents of this map into a new array with a 
> 3.   \* larger capacity.  This method is called automatically when the 
> 4.   \* number of keys in this map reaches its threshold. 
> 5.   \* 
> 6.   \* If current capacity is MAXIMUM\_CAPACITY, this method does not 
> 7.   \* resize the map, but sets threshold to Integer.MAX\_VALUE. 
> 8.   \* This has the effect of preventing future calls. 
> 9.   \* 
> 10.  \* @param newCapacity the new capacity, MUST be a power of two; 
> 11.  \*        must be greater than current capacity unless current 
> 12.  \*        capacity is MAXIMUM\_CAPACITY (in which case value 
> 13.  \*        is irrelevant). 
> 14.  \*/  
> 15. **void** resize(**int** newCapacity) \{  
> 16.     Entry\[\] oldTable = table;  
> 17.     **int** oldCapacity = oldTable.length;  
> 18.     **if** (oldCapacity == MAXIMUM\_CAPACITY) \{  
> 19.         threshold = Integer.MAX\_VALUE;  
> 20.         **return**;  
> 21.     \}  
> 22.   
> 23.     Entry\[\] newTable = **new** Entry\[newCapacity\];  
> 24.     transfer(newTable);  
> 25.     table = newTable;  
> 26.     threshold = (**int**)(newCapacity \* loadFactor);  
> 27. \}  
> 28.   
> 29. /\*\* 
> 30.  \* Transfers all entries from current table to newTable. 
> 31.  \*/  
> 32. **void** transfer(Entry\[\] newTable) \{  
> 33.     Entry\[\] src = table;  
> 34.     **int** newCapacity = newTable.length;  
> 35.     **for** (**int** j = 0; j < src.length; j++) \{  
> 36.         Entry<K,V> e = src\[j\];  
> 37.         **if** (e != **null**) \{  
> 38.             src\[j\] = **null**;  
> 39.             **do** \{  
> 40.                 Entry<K,V> next = e.next;  
> 41.                 **int** i = indexFor(e.hash, newCapacity);  
> 42.                 e.next = newTable\[i\];  
> 43.                 newTable\[i\] = e;  
> 44.                 e = next;  
> 45.             \} **while** (e != **null**);  
> 46.         \}  
> 47.     \}  
> 48. \}  
> 
>   
> 
> 
>   
>

> **为什么JDK建议我们重写Object.equals(Object obj)方法时，需要保证对象可以返回相同的hashcode值？**  
> 
> 
> Java程序员都看过JDK的API文档，该文档关于Object.equals(Object obj)方法，有这样的描述：
> 
>  *  “注意：当此方法被重写时，通常有必要重写hashCode 方法，以维护hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。”*
> 
> 读者虽然知道这个协定，但是不一定真正知道为什么会有这一个要求，现在，就来看看原因吧。
> 
> 请读者再注意看一下上述的额put()方法实现，当遍历某个桶中的Entry<Key,Value>链表来查找Entry实例的过程中所使用的判断条件：
> 
> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  **for** (Entry<K,V> e = table\[i\]; e != **null**; e = e.next) \{  
> 2.              Object k;  
> 3.              //5. 查找Entry<Key,Value>链表中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,  
> 4.              //已经存在,则将Value值覆盖到对应的Entry<Key,Value>对象节点上  
> 5.              **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{  
> 6.                  V oldValue = e.value;  
> 7.                  e.value = value;  
> 8.                  e.recordAccess(**this**);  
> 9.                  **return** oldValue;  
> 10.             \}  
> 11.         \}  
> 
> 对于给定的Key,Value，判断该Key是否与Entry链表中有某一个Entry对象的Key值相等使用的是(k==e.key)==key) || key.equals(k)，另外还有一个判断条件：即Key经过hash函数转换后的hash值和当前Entry对象的hash属性值相等（该hash属性值和Entry内的Key经过hash方法转换后的hash值相等）。
> 
> *    *上述的情况我们可以总结为；HashMap在确定Key是否在HashMap中存在的要求有两个：
> 
> *           1. Key值是否相等；*
> 
> *      2. hashcode是否相等；*
> 
> *      所以我们在定义类时，如果重写了equals()方法，但是hashcode却没有保证相等，就会导致当使用该类实例作为Key值放入HashMap中，会出现HashMap“工作异常”的问题，会出现你不希望的情况。下面让我们通过一个例子来看看这个“工作异常”情况：*
> 
> 例子： 定义一个简单Employee类，重写equals方法，而没有重写hashCode()方法。然后使用该类创建两个实例，放置到一个HashMap中：
> 
> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  **package** com.louis.hashlearning;  
> 2.    
> 3.  /\*\* 
> 4.   \* 简单Employee Bean，重写equals方法,未重写hashCode()方法 
> 5.   \* @author louluan 
> 6.   \*/  
> 7.  **public** **class** Employee \{  
> 8.        
> 9.      **private** String employeeCode;  
> 10.     **private** String name;  
> 11.       
> 12.     **public** Employee(String employeeCode, String name) \{  
> 13.         **this**.employeeCode = employeeCode;  
> 14.         **this**.name = name;  
> 15.     \}  
> 16.       
> 17.     **public** String getEmployeeCode() \{  
> 18.         **return** employeeCode;  
> 19.     \}  
> 20.     **public** String getName() \{  
> 21.         **return** name;  
> 22.     \}  
> 23.       
> 24.     @Override  
> 25.     **public** **boolean** equals(Object o)  
> 26.     \{  
> 27.         **if**(o **instanceof** Employee)  
> 28.         \{  
> 29.             Employee e = (Employee)o;  
> 30.             **if**(**this**.employeeCode.equals(e.getEmployeeCode()) && name.equals(e.getName()))  
> 31.             \{  
> 32.                 **return** **true**;  
> 33.             \}  
> 34.         \}  
> 35.         **return** **false**;  
> 36.     \}  
> 37. \}  
> 
> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  **package** com.louis.hashlearning;  
> 2.  **import** java.util.HashMap;  
> 3.    
> 4.  **public** **class** Test \{  
> 5.        
> 6.      **public** **static** **void** main(String\[\] args) \{  
> 7.          Employee em1= **new** Employee("123","louis");  
> 8.          Employee em2= **new** Employee("123","louis");  
> 9.          **boolean** equals= em1.equals(em2);  
> 10.         System.out.println("em1 equals em2 ? " +equals);  
> 11.           
> 12.         HashMap map = **new** HashMap();  
> 13.         map.put(em1, "test1");  
> 14.         map.put(em2, "test2");  
> 15.         System.out.println("map size:"\+map.size());  
> 16.     \}  
> 17.   
> 18. \}  
> 
>  输出结果：  
> ![20141129201608134][]  
>   
> 
> 
>    结果分析：
> 
>         上述的例子中，我们使用了new Employee("123","louis"); 语句创建了两个完全一样的对象em1,em2，对我们来说，它们就是相同的对象，然后，我们将这两个我们认为相等的对象作为Key值放入HashMap中，我们想要的结果是：HashMap中的Entry<Key,Value>键值对数目应该就一个，并且Entry对象的Value值应该是由"test1" 替换成"test2",但是实际的结果是：HashMap的大小为2，即HashMap中有两个Entry<Key,Value>键值对！！！
> 
>         原因现在读者清晰了：因为em1和em2对象的hashCode()继承自Object，它们返回两个不同的值，即em1 和em2的hashcode值不相同。
> 
> 从上面的这个例子可以看出：
> 
>          *我们重写Object.equals(Object obj)方法时，需要保证对象可以返回相同的hashcode。否则，HashMap工作的时候会有不可控的异常情况出现。*  
>

####      2.   get() 方法的实现： ####

根据特定的Key值从HashMap中取Value的结果就比较简单了：

> get()方法-根据Key从HashMap中取Value
> 
> a.  获取这个Key的hashcode值，根据此hashcode值决定应该从哪一个桶中查找；
> 
> b.  遍历所在桶中的Entry<Key,Value>链表，查找其中是否已经有了以Key值为Key存储的Entry<Key,Value>对象，
> 
> c1. 若已存在，定位到对应的Entry<Key,Value>,返回value
> 
> c2. 若不存在，返回null；  
> 
> 
> 具体算法如下：
> 
> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  /\*\* 
> 2.   \* Returns the value to which the specified key is mapped, 
> 3.   \* or \{@code null\} if this map contains no mapping for the key. 
> 4.   \*  返回key对应的Value值，如果HashMap中没有，则返回null； 
> 5.   \*  支持Key为null情况 
> 6.   \* <p>More formally, if this map contains a mapping from a key 
> 7.   \* \{@code k\} to a value \{@code v\} such that \{@code (key==null ? k==null : 
> 8.   \* key.equals(k))\}, then this method returns \{@code v\}; otherwise 
> 9.   \* it returns \{@code null\}.  (There can be at most one such mapping.) 
> 10.  \* 
> 11.  \* <p>A return value of \{@code null\} does not <i>necessarily</i> 
> 12.  \* indicate that the map contains no mapping for the key; it's also 
> 13.  \* possible that the map explicitly maps the key to \{@code null\}. 
> 14.  \* The \{@link \#containsKey containsKey\} operation may be used to 
> 15.  \* distinguish these two cases. 
> 16.  \* 
> 17.  \* @see \#put(Object, Object) 
> 18.  \*/  
> 19. **public** V get(Object key) \{  
> 20.     **if** (key == **null**)  
> 21.         **return** getForNullKey();  
> 22.     **int** hash = hash(key.hashCode());  
> 23.     //遍历列表  
> 24.     **for** (Entry<K,V> e = table\[indexFor(hash, table.length)\];  
> 25.          e != **null**;  
> 26.          e = e.next) \{  
> 27.         Object k;  
> 28.         **if** (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
> 29.             **return** e.value;  
> 30.     \}  
> 31.     **return** **null**;  
> 32. \}  
> 
>   
>

####       3.HashMap对Key为null情况的支持 ####

HashMap允许Key以null的形式存取，Hashmap会将Key为null组成的Entry<null,Value>放置到table\[0\],即第一个桶中，在put()和get()操作时，会先对Key 为null的值特殊处理：

> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  /\*\* 
> 2.   \* Offloaded version of get() to look up null keys.  Null keys map 
> 3.   \* to index 0.  This null case is split out into separate methods 
> 4.   \* for the sake of performance in the two most commonly used 
> 5.   \* operations (get and put), but incorporated with conditionals in 
> 6.   \* others. 
> 7.   \* get 操作 
> 8.   \*/  
> 9.  **private** V getForNullKey() \{  
> 10.     **for** (Entry<K,V> e = table\[0\]; e != **null**; e = e.next) \{  
> 11.         **if** (e.key == **null**)  
> 12.             **return** e.value;  
> 13.     \}  
> 14.     **return** **null**;  
> 15. \}  
> 
>   
> 
> 
> **\[java\]**  [view plain][]   [copy][view plain]
> 
>   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> 
> 1.  /\*\* 
> 2.   \* Key 为null,则将Entry<null,Value>放置到第一桶table\[0\]中 
> 3.   \*/  
> 4.  **private** V putForNullKey(V value) \{  
> 5.      **for** (Entry<K,V> e = table\[0\]; e != **null**; e = e.next) \{  
> 6.          **if** (e.key == **null**) \{  
> 7.              V oldValue = e.value;  
> 8.              e.value = value;  
> 9.              e.recordAccess(**this**);  
> 10.             **return** oldValue;  
> 11.         \}  
> 12.     \}  
> 13.     modCount++;  
> 14.     addEntry(0, **null**, value, 0);  
> 15.     **return** **null**;  
> 16. \}  
> 
>   
>

####      4. 键值对Entry<Key,Value>的移除----remove(key)方法的实现 ####

> 根据key值移除键值对的操作也比较简单，内部关键的流程分为两个：
> 
> > *1. 根据Key的hashcode 值和Key定位到Entry<key,Value> 对象在HashMap中的位置；*
> > 
> > *2. 由于Entry<Key,Value>是一个链表元素，之后便是链表删除节点的操作了；*
> 
> > **\[java\]**  [view plain][]   [copy][view plain]
> > 
> >   [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]
> > 
> > 1.  /\*\* 
> > 2.   \* Removes the mapping for the specified key from this map if present. 
> > 3.   \* 
> > 4.   \* @param  key key whose mapping is to be removed from the map 
> > 5.   \* @return the previous value associated with <tt>key</tt>, or 
> > 6.   \*         <tt>null</tt> if there was no mapping for <tt>key</tt>. 
> > 7.   \*         (A <tt>null</tt> return can also indicate that the map 
> > 8.   \*         previously associated <tt>null</tt> with <tt>key</tt>.) 
> > 9.   \*/  
> > 10. **public** V remove(Object key) \{  
> > 11.     Entry<K,V> e = removeEntryForKey(key);  
> > 12.     **return** (e == **null** ? **null** : e.value);  
> > 13. \}  
> > 14.   
> > 15. /\*\* 
> > 16.  \* Removes and returns the entry associated with the specified key 
> > 17.  \* in the HashMap.  Returns null if the HashMap contains no mapping 
> > 18.  \* for this key. 
> > 19.  \*/  
> > 20. **final** Entry<K,V> removeEntryForKey(Object key) \{  
> > 21.     **int** hash = (key == **null**) ? 0 : hash(key.hashCode());  
> > 22.     **int** i = indexFor(hash, table.length);  
> > 23.     Entry<K,V> prev = table\[i\];  
> > 24.     Entry<K,V> e = prev;  
> > 25.   
> > 26.     **while** (e != **null**) \{  
> > 27.         Entry<K,V> next = e.next;  
> > 28.         Object k;  
> > 29.         **if** (e.hash == hash &&  
> > 30.             ((k = e.key) == key || (key != **null** && key.equals(k)))) \{  
> > 31.             modCount++;  
> > 32.             size--;  
> > 33.             **if** (prev == e)  
> > 34.                 table\[i\] = next;  
> > 35.             **else**  
> > 36.                 prev.next = next;  
> > 37.             e.recordRemoval(**this**);  
> > 38.             **return** e;  
> > 39.         \}  
> > 40.         prev = e;  
> > 41.         e = next;  
> > 42.     \}  
> > 43.   
> > 44.     **return** e;  
> > 45. \}  
> > 
> >   
> >

### 4. HashMap的特点总结： ###

1. HashMap是线程不安全的，如果想使用线程安全的,可以使用Hashtable；它提供的功能和Hashmap基本一致。HashMap实际上是一个Hashtable的轻量级实现；同时，也可以使用Collections工具类，进行线程同步控制；

2. 允许以Key为null的形式存储<null,Value>键值对；

3. HashMap的查找效率非常高，因为它使用Hash表对进行查找，可直接定位到Key值所在的桶中；

4. 使用HashMap时，要注意HashMap容量和加载因子的关系，这将直接影响到HashMap的性能问题。加载因子过小，会提高HashMap的查找效率，但同时也消耗了大量的内存空间，加载因子过大，节省了空间，但是会导致HashMap的查找效率降低。

[20141130134720355]: /images/20220717/952968d804c7446b97e0429957254947.png
[20141128145931557]: /images/20220717/7aa2f35c2fe04dfba2d9e99c3d397bbb.png
[20141128155624016]: /images/20220717/4c394a65fb7a4c49a19e464c4d01c999.png
[view plain]: http://blog.csdn.net/luanlouis/article/details/41576373?utm_source=tuicool&utm_medium=referral#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/537209
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/537209/fork
[20141129201608134]: /images/20220717/22042cf0a38841dea4b21fa6b74ccda7.png