HashMap实现原理

比眉伴天荒 2022-12-19 01:27 162阅读 0赞

### 文章目录 ###

*  一、什么是哈希表
 *   *  哈希冲突
     *  哈希冲突如何解决呢？
     *  HashMap采用哪种方法解决冲突的呢？
 *  二、对比：Hashtable、HashMap、TreeMap
 *  三、HashMap概念和底层结构
 *  四、HashMap的工作原理
 *   *  HashMap具体的存取过程：
 *  五、重写equals方法和hashCode方法
 *   *  1、如何重写equals方法和hashCode方法
     *   *  1 实现高质量的equals方法的诀窍包括
         *  2、实现hashCode方法的通用约定
     *  2、为啥HashMap中 “重写equals时也要同时覆盖hashcode”

# 一、什么是哈希表 #

> 哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而HashMap的实现原理也常常出现在各类的面试题中，重要性可见一斑。

在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能

**数组**：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

**线性链表**：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

**哈希表**：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的

我们知道，数据结构的物理存储结构只有两种：`顺序存储结构`和`链式存储结构`（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，`哈希表的主干就是数组`。

比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。  
`存储位置 = f(关键字)`  
其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1Y2hhaGFlcmthbmc_size_16_color_FFFFFF_t_70_pic_center]  
查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

## 哈希冲突 ##

然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

## 哈希冲突如何解决呢？ ##

a. 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。  
b. 开放定址法：即发生冲突时，去寻找下一个空的哈希地址。只要哈希表足够大，总能找到空的哈希地址。  
c. 再哈希法：即发生冲突时，由其他的函数再计算一次哈希值。  
d. 建立公共溢出区：将哈希表分为基本表和溢出表，发生冲突时，将冲突的元素放入溢出表。

## HashMap采用哪种方法解决冲突的呢？ ##

HashMap 就是使用链地址法来解决冲突的（jdk8中采用平衡树来替代链表存储冲突的元素，但hash() 方法原理相同）。当两个对象的hashcode相同时，它们的bucket位置相同，碰撞就会发生。此时，可以将 put 进来的 K- V 对象插入到链表的尾部。对于储存在同一个bucket位置的链表对象，可通过键对象的equals()方法用来找到键值对。

# 二、对比：Hashtable、HashMap、TreeMap #

Hashtable 是早期Java类库提供的一个哈希表实现，本身是同步的，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用。

HashMap与 HashTable主要区别在于 HashMap 不是同步的，支持 null 键和值等。通常情况下，HashMap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选。

TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get、put、remove 之类操作都是 O（log(n)）的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。

# 三、HashMap概念和底层结构 #

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。HashMap储存的是键值对，HashMap很快。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap 内部结构：可以看作是数组和链表结合组成的复合结构，数组被分为一个个桶（bucket），每个桶存储有一个或多个Entry对象，每个Entry对象包含三部分key（键）、value（值），next(指向下一个Entry），通过哈希值决定了Entry对象在这个数组的寻址；哈希值相同的Entry对象（键值对），则以链表形式存储。如果链表大小超过树形转换的阈值（TREEIFY\_THRESHOLD= 8），链表就会被改造为树形结构。

hashMap的结构示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1Y2hhaGFlcmthbmc_size_16_color_FFFFFF_t_70_pic_center 1]  
查询时间复杂度：HashMap的本质可以认为是一个数组，数组的每个索引被称为桶，每个桶里放着一个单链表，一个节点连着一个节点。很明显通过下标来检索数组元素时间复杂度为O(1)，而且遍历链表的时间复杂度是O(n)，所以在链表长度尽可能短的前提下，HashMap的查询复杂度接近O(1)

# 四、HashMap的工作原理 #

HashMap的工作原理 ：HashMap是基于散列法（又称哈希法）的原理，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。HashMap是在bucket中储存键对象和值对象，作为Map.Entry。并不是仅仅只在bucket中存储值。

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

其他几个重要字段

//实际存储的key-value键值对的个数
    transient int size;
    //阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
    int threshold;
    //负载因子，代表了table的填充度有多少，默认是0.75
    final float loadFactor;
    //用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
    transient int modCount;

HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值  
initialCapacity默认为16，loadFactory默认为0.75

## HashMap具体的存取过程： ##

**put存值的方法**，过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1Y2hhaGFlcmthbmc_size_16_color_FFFFFF_t_70_pic_center 2]  
①.判断键值对数组table\[i\]是否为空或为null，否则执行resize()进行扩容；  
②.根据键值key计算hash值得到插入的数组索引i，如果table\[i\]==null，直接新建节点添加，转向⑥，如果table\[i\]不为空，转向③；  
③.判断table\[i\]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；  
④.判断table\[i\] 是否为treeNode，即table\[i\] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；  
⑤.遍历table\[i\]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；  
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

**get取值的方法**，过程如下:  
①.指定key 通过hash函数得到key的hash值  
int hash=key.hashCode();  
②.调用内部方法 getNode()，得到桶号(一般为hash值对桶数求模)  
int index =hash%Entry\[\].length;  
jdk1.6版本后使用位运算替代模运算，int index=hash&( Entry\[\].length - 1）;  
③.比较桶的内部元素是否与key相等，若都不相等，则没有找到。相等，则取出相等记录的value。  
④.如果得到 key 所在的桶的头结点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。getTreeNode 方法使通过调用树形节点的 find()方法进行查找。由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。  
⑤.如果对比节点的哈希值和要查找的哈希值相等，就会判断 key 是否相等，相等就直接返回；不相等就从子树中递归查找。

**如何重新调整HashMap的大小**  
“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”  
HashMap的扩容阈值（threshold = capacity\* loadFactor 容量范围是16~2的30次方），就是通过它和size进行比较来判断是否需要扩容。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，将会创建原来HashMap大小的两倍的bucket数组（jdk1.6，但不超过最大容量），来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

# 五、重写equals方法和hashCode方法 #

关于HashMap的源码分析就介绍到这儿了，最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”

## 1、如何重写equals方法和hashCode方法 ##

### 1 实现高质量的equals方法的诀窍包括 ###

*  使用==操作符检查“参数是否为这个对象的引用”；
 *  使用instanceof操作符检查“参数是否为正确的类型”；
 *  对于类中的关键属性，检查参数传入对象的属性是否与之相匹配；
 *  编写完equals方法后，问自己它是否满足对称性、传递性、一致性；
 *  重写equals时总是要重写hashCode；
 *  不要将equals方法参数中的Object对象替换为其他的类型，在重写时不要忘掉@Override注解。

public boolean equals(Object otherObject){       
               if(this == otherObject) { //测试两个对象是否是同一个对象，是的话返回true
                   return true;   
               } 
               if(otherObject == null) {   //测试检测的对象是否为空，是就返回false
                   return false;       
               }
               if(getClass() != otherObject.getClass()) {  //测试两个对象所属的类是否相同，否则返回false
                   return false; 
               }       
               A other=(A)otherObject; //对otherObject进行类型转换以便和类A的对象进行比较
               return Object.equals(类A对象的属性A，other的属性A）&&类A对象的属性B==other的属性B……;
        }

public class TestEquals {
    
        public static void main(String[] args) {
            Person2 p1 = new Person2("aa", 13);
            Person2 p2 = new Person2("aa", 13);
            Person2 p3 = new Person2("bb", 13);
            System.out.println(p1.equals(p2)); // true
            System.out.println(p1.equals(p3)); // false
        }
    
    }
    
    class Person2 {
        private String name;
        private int age;
     
        public Person2(String name, int age) {
            this.name = name;
            this.age = age;
        }
     
        public String getName() {
            return name;
        }
     
        public void setName(String name) {
            this.name = name;
        }
     
        public int getAge() {
            return age;
        }
     
        public void setAge(int age) {
            this.age = age;
        }
     
        public boolean equals(Object another) {
     
            //先判断是不是自己,提高运行效率
            if (this == another)
                return true;
     
            //再判断是不是Person类,提高代码的健壮性
            if (another instanceof Person2) {
     
                //向下转型,父类无法调用子类的成员和方法
                Person2 anotherPerson = (Person2) another;
     
                //最后判断类的所有属性是否相等，其中String类型和Object类型可以用相应的equals()来判断
                if ((this.getName().equals(anotherPerson.getName())) && (this.getAge() == anotherPerson.getAge()))
                    return true;
            } else {
                return false;
            }
     
            return false;
        }
    }

### 2、实现hashCode方法的通用约定 ###

生成一个 int 类型的变量 result，并且初始化一个值，比如17  
对类中每一个重要字段，也就是影响对象的值的字段，也就是 equals 方法里有比较的字段，进行以下操作：a. 计算这个字段的值 filedHashValue = filed.hashCode(); b. 执行 result = 31 \* result + filedHashValue;

@Override
        public int hashCode() {
            int result = 17;
            result = 31 * result + (name == null ? 0 : name.hashCode());
            result = 31 * result + (age == null ? 0 : age.hashCode());
            return result;
        }

## 2、为啥HashMap中 “重写equals时也要同时覆盖hashcode” ##

public class MyTest {
        private static class Person{
            int idCard;
            String name;
    
            public Person(int idCard, String name) {
                this.idCard = idCard;
                this.name = name;
            }
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()){
                    return false;
                }
                Person person = (Person) o;
                //两个对象是否等值，通过idCard来确定
                return this.idCard == person.idCard;
            }
    
        }
        public static void main(String []args){
            HashMap<Person,String> map = new HashMap<Person, String>();
            Person person = new Person(1234,"乔峰");
            //put到hashmap中去
            map.put(person,"天龙八部");
            //get取出，从逻辑上讲应该能输出“天龙八部”
            System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
        }
    }

实际输出结果：

> `结果：null`

如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–>hash–>indexFor–>最终索引位置 ，而通过key取出value的时候 key(hashcode2)–>hash–>indexFor–>最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）  
　　所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1Y2hhaGFlcmthbmc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/dc398c1dd46b4a3fbe72465d9ae50f1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1Y2hhaGFlcmthbmc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/54eecb22558c4b658398f29153c007a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1Y2hhaGFlcmthbmc_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/a66f27ffd8b44a7ab8009d3295f9aead.png