HashMap介绍

数据结构是一门组织联系数据的学科，其中一种数据结构就是 HashMap，它是一种以键值对的形式存储数据的数据结构，时间复杂度可以达到 O（1）

---

HashMap常用方法

HashMap 的方法有很多，这里介绍几个常用的：

以下代码均使用该实例：

Map<T, T> map = new HashMap<>();
1

1. put（）方法
   用于将键值对存入 map 中

map.put("zhangsan", 20);
map.put("lisi", 22);
1
2

注意： （1）map 中不允许存在相同的 K 值，所以当使用 put 函数放入键值对时，如果此时 map 中已经有了当前 K 值，则会将原有 K 所对应的 V 值覆盖。
（2）HashMap 中的 put（）方法允许使用 null 作为 K

2. get（）方法
   用于获取 map 中已存放的键值对中指定 K 值对应的 V 值。

map.get("zhangsan");
map.get("zhangsan2");
1
2

此时的输出结果分别对应 20，null

3. remove（）方法
   用于删除 map 中存放的键值对

map.remove("zhangsan");
1

此时 map 中只剩下 <“lisi”, 20> 这组键值对

4. keySet（）方法
   用于获取 map 中所有不重复 K 值集合，返回一个 Set

Set set = map.keySet();
1

set 中的所有元素的是不重复的。

5. EntrySet（）方法
   用于获取 map 中所有键值对的映射关系

Set<Map.Entry<String, Integer>> setEntry = map.EntrySet();
1

其 setEntry 中存放的就是若干个 Map.Entry 类型的键值对

---

哈希表

HashMap 的底层实现就是一张哈希表，或者叫哈希桶（HashBuck）

哈希表的存取都通过哈希函数来进行映射，得到相应的映射关系，找到对应的哈希地址来进行存储，从而其时间复杂度达到O（1）

哈希表的存取

举个栗子来描述哈希表的存取

假设 K 值为 Integer 类型的

哈希函数：K % array.length
那么对应的存取将都由这个哈希函数进行映射

比如以下有 4 个数据：0， 4， 18， 22
以及一个 array 数组（大小为 10）

将这四个数据分别代入哈希函数求得哈希地址为：0，4，8，2

将其对应存放进 array 数组里

如果要取元素，也同样通过哈希函数进行映射拿到对应哈希地址取出元素。

但是这样的存取，就必然会存在一个问题，那就是 “哈希冲突”

哈希冲突

当哈希函数确定之后，如果存入大量的数据，都通过这个哈希函数进行映射，那必然会出现哈希地址重复的情况，这就是哈希冲突。
如果一味的不管哈希冲突，就会导致新的数据将旧的数据覆盖，为了解决这个问题，可以采用增加数组长度的方式，但是因为数据个数一定是远远大于数组长度的，也就导致哈希冲突是无法避免的，
所以哈希表采用的方法是开链法

所谓开链法，就是将所有的数据通过数组 + 链表的形式进行组织

每一个链表节点必须有 3 个域，分别是 next 域，K 域，V 域
而数组中存放的每个元素是引用类型，存放链表第一个节点的地址。

如下图，将 4 个键值对存入哈希表

<0, “a”> <4, “c”> <18, “d”> <22, “b”>

使用开链法的方式进行存储将是以上形式，这样可以有效的避免哈希冲突带来的麻烦。

比如现在又要插入几个键值对：<10，“e”>，<28，“f”>

结果如下：

注：哈希表中的链表采用的是头插法，我这里为了方便画图采用了尾插法，请见谅~

以上就是哈希桶进行存取数据的方式，但是现在又有了新的问题，哈希表的存取需要让时间复杂度达到 O（1），如果链表的长度过长，那么就会导致存取的时间复杂度达不到 O（1）。

这里就提出了一个概念，叫做负载因子

负载因子

在哈希表中，数据的个数是无法确定已经更改的，为了避免链表的长度过长而降低时间复杂度，只能通过增加数组长度的方式来解决。

而负载因子 = 数据的个数 / 数组的长度

我们知道，数据的个数是不可控的，而当我们增加数组的长度，就可以降低负载因子，从而负载因子就可以作为我们评判数组是否扩容的标准。

在源码中，默认的负载因子大小为 0.75，也就意味着，当存入的数据太多，导致负载因子超过 0.75 时，数组就会进行扩容。

通过负载因子的控制，链表的长度就不会很长，可以控制在常数范围内

---

扩容机制

在哈希表中，除了给定了默认的负载因子大小为 0.75，还给定了一个 1 << 30 作为哈希表的最大默认容量，每一次存储数据之后会计算对应的负载因子是否超过了 0.75，如果超过了 0.75，将会判断当前容量的两倍有没有超过 1 << 30，如果没有超过，则进行二倍扩容，如果超过了，则将 1 << 30 作为新的容量大小。

在每一次数组进行扩容之后，原来存放的数据必须进行重新哈希，因为此时的数组长度已经发生了变化，这样就能够达到我们想要缩短链表长度的目的，如下：

这样即可降低哈希表中链表的长度，达到提高效率的目的。

---

其他机制

由上文已经了解到了几个简单的机制，譬如默认负载因子大小为 0.75，最大容量为1 << 30，超过默认负载因子将出发扩容机制等等。。

接下来还有几个比较重要的机制。

哈希表容量问题

首先，如果在实例化时不指定哈希表的容量，则哈希表的默认容量为 16，但并非是构造出 map 对象的那一时刻就给定容量，在 JDK 8 中，实例化 map 之后其实他的容量依然是为 0 的，如果我们不指定 map 大小，那么将在第一次 put（）元素时为其开辟大小为 16 的容量。
如果指定了哈希表的容量，如：

Map<String, Integer> map = new HashMap<>(20);
1

则同理，在实例化之后，并不分配容量，而是在第一次 put（）元素时为其分配大小，但值得一说的是，这里给它分配的容量大小并不是 20，而是 32，具体原因看完第二点便可知道。

哈希函数问题
哈希表的容量大小必须是 2 的次幂，其原因是为了提高哈希表的效率，降低哈希冲突。
在源码中，计算并不是使用 hash（K）% array.length 来进行计算的，取而代之的是 hash（K）&（array.length - 1）。
因为按位与运算比取模运算的效率要高很多，而 & 运算存在一个问题，hash（K）的值可能为 1 也可能为 0，而如果（array.length - 1）的值也可奇可偶的话，那么运算出来是偶数的概率则会特别大，为了解决这个问题，就采用了让 array.length - 1，并且保证数组长度是偶数的方法来确保 array.length - 1 是奇数，这样计算的结果奇偶概率分散，即可大大降低哈希冲突的概率。

树化问题

就算哈希表有了负载因子，有了开链法，有了扩容机制，但还是架不住数据量的庞大，这就导致链表长度随时会过长，为了不让这种现象影响哈希表的性能，在哈希桶中会在每一次 put（）元素之后进行判断，如果当前链表长度超过 8 则会将链表转换成一种查找效率极高的数据结构 - - 红黑树（这里不介绍），以此来保证其时间复杂度达到O（1）。

当变成红黑树之后，如果哈希表中使用 remove（）方法删除元素，导致链表长度小于 6，则又会将红黑树进行链化，变成原来的链表。

hashcode 问题

上文讲的例子中，K 的值是 Integer 类型的，但我们在使用 HashMap 的时候极有可能用到的 K 值是 String 类型或者其他类型的数据，那该如何进行计算呢？

答案就是重写 hashcode（）方法，使用 hashcode（）方法可以将不是整型的数据转化为一个合法的整型数据，从而方便进行哈希映射。

那么，就又引出了一个新的问题，举一个栗子，如果要存放用户对应的身份证信息，那就需要不管是几个实例的 map，只要存放的 K 值相同，查找到的身份证信息就应该相同，但是 hashcode（）方法就出问题了：

class Person {
    public String name;
    
    public Person(String name) {
        this.name = name;
    }
    
    @Override
    public int hashCode() {
        return Object.hash(name);
    }
}
Map<String, Integer> map = new HashMap<>();
map.put("zhangsan", 123);

Person person1 = new Person("zhangsan");
Person person2 = new Person("zhangsan");

person1.hashcode();
person2.hashcode();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

此时的 person1 和 person2 的 hash 值将会不相等，因为这是针对两个不同对象的 hashcode，所以对应的值会不相等，但他们的 name 都是 “zhangsan”，所以我们希望他们拿到的哈希值是一样的。

这就需要 “hashcode and equals” 来解决这个问题了。

我们只需要在 Person 类中同时重写 hashcode（）方法和 equals（）方法。

class Person {
    public String name;
    
    public Person(String name) {
        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;
        return Object.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Object.hash(name);
    }
    
    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                '}'";
    }
}

Person person1 = new Person("123");
Person person2 = new Person("123");
        
System.out.println(person1.hashcode());
System.out.println(person2.hashcode());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

此时拿到的哈希值就会是相等的了，重写的 equals（）方法会帮助我们判断对象是否相等，如果相等，就会返回 TRUE，在 hashcode（）时返回一个相同的值。

相当于如果我们在查字典，要查 “二” 这个字
equals（）方法就帮我们找到了 E 所对应的位置
而hashcode（）方法则帮我们找到 “er”

所以，在使用哈希表存放自定义类型数据类型的时候，一定要重写 hashcode（）方法和 equals（）方法。

总结

以上就是本文的全部内容，首先是 hashmap 的常用方法：put，get，keySet等等。
然后是哈希表的底层是一个哈希桶，使用链表 + 数组的形式进行组织。

接下来是哈希表中的一些机制，比如何时开辟内存，超过负载因子进行二倍扩容并重新哈希，链表长度超过阈值树化，哈希桶容量必须是 2 的幂次等等。

希望本文可以给大家带来帮助~ 感谢~~