Java基础系列（四十八）：集合之HashMap

HashMap简介

说起HashMap，大家肯定都不会陌生，我们用的最多的大概就是这个容器类来存储k-v数据，正如它的名字所说的那样，它是基于散列表实现的，散列表的强大之处在于查找时的时间复杂度为O(1)，因为每个对象都有一个对应的索引，我们可以直接根据对象的索引去访问这个对象，而这个索引就是我们对象的hash值。

在Java中散列表是通过链表 + 数组进行实现的，每个链表可以称之为一个桶，而对象的位置就是通过计算该对象的哈希值，然后与桶的总数（也就是HashMap的长度）取余，所得到的结果就是保存这个元素的桶的索引，如果出现两个对象具有同样的哈希值，就会出现Hash冲突的现象，这个时候就需要用新的对象与链表（桶）中的对象进行比较，查看这个对象是否已经存在。如果不存在，就新增一个。

但是这里遇到了一个问题，如果说桶的数量很有限（比如只有三个桶），但是数据量却很大，比如有10000个数据，这样就会导致哈希冲突非常的严重，这时，JDK 8以后的版本为我们提供了一种新的思路，当链表的长度大于8的时候，就会将后续的元素存储到红黑树（也叫平衡二叉树）当中，这样可以大大的提高我们的查询效率。

构造

首先，我们来看一下源码的构造函数

可以看出，源码中给出了四种构造函数，第一个表示的给定初始化Map长度（桶数）和装填因子的构造函数，装填因子的作用是决定何时对散列表进行再散列，比如，初始化装填因子是0.75，当表中75%的位置已经填入了元素，这个表就会用双倍的桶数进行再散列。如果没有设置初始值，就会采用默认的值（长度为16，装填因子为0.75）

第四个代表的是构造一个包含该Map的HashMap对象。

Node

通过观察源码，我们可以发现HashMap是基于一个叫Node的内部类作为骨干来实现的，而这个内部类Node是Entry的一个实现。


这里可以看一下Node的hashCode()方法的实现：
这里之所以进行了异或运算，是为了让散列的更均匀，以减少哈希冲突的次数。
关于TreeNode是一些有关于红黑树的实现，这里不再多做篇幅进行讲解，后面会在数据结构和算法中进行详细的学习。

关于GET，PUT的实现

我们首先来看一些get()方法的实现：

这里可以看到，首先通过key和计算出的hash值来找到对应的Node，然后获取到该Node的Value或者是null。

这里的hash算法也是为了让散列的更均匀，减少散列冲突的次数

这里的实现可以分为以下几步：

1. 根据传入的hash值，可以直接计算出对应的索引（n - 1）& hash。
2. 判断第一个存在的节点的key是否和查询的key相等。如果相等，直接返回该节点。
3. 对该Node进行遍历
4. 判断该集合的结构是链表还是红黑树，如果是红黑树调用内部的方法找到key对应的value。
5. 如果结构是链表，遍历获取到对应key所对应的value。

然后，我们来看put()方法的实现：

首先来解释一下方法中的参数：boolean onlyIfAbsent表示只有在该key对应原来的value为null的时候才插入，也就是说如果value之前存在了，就不会被新put的元素覆盖。其余的流程和get()方法的思路有很大层度上相似，这里需要注意的有圈住的地方，插入成功后，要判断是否需要转换为红黑树，因为插入后链表长度加1，而binCount并不包含新节点，所以判断时要将临界阈值减1。当新长度满足转换条件时，调用treeifyBin方法，将该链表转换为红黑树。

(注：remove()方法实际上是通过调用removeNode()方法来实现的，和这两个方法的思路大致上是类似的，有兴趣的同学可以自己去研读，这里由于篇幅问题不再多做深入。)

关于HashMap的知识我们就先讲到这里，如果有可能你们会在源码系列再次看到

原创文章，文笔有限，才疏学浅，文中若有不正之处，万望告知。

云撸猫

公众号