作者：三分恶 链接：https://juejin.cn/post/7033769296320790542 来源：稀土掘金

认识哈希表

HashMap其实是数据结构中的哈希表在Java里的实现。

哈希表本质

哈希表也叫散列表，我们先来看看哈希表的定义：

哈希表是根据关键码的值而直接进行访问的数据结构。

就像有人到公司找老三，前台小姐姐拿手一指，那个墙角的工位就是。 简单说来说，哈希表由两个要素构成：桶数组和散列函数。

• 桶数组：一排工位
• 散列函数：老三在墙角

桶数组

我们可能知道，有一类基础的数据结构线性表，而线性表又分两种，数组和链表。 哈希表数据结构里，存储元素的数据结构就是数组，数组里的每个单元都可以想象成一个桶（Bucket）。 假如给若干个程序员分配工位：蛋蛋、熊大、牛儿、张三，我们观察到，这些名字比较有特色，最后一个字都是数字，我们可以把它提取出来作为关键码，这些一来，就可以把他们分配到对应编号的工位，没分配到的工位就让它先空着。 那么在这种情况下，我们查找/插入/删除的时间复杂度是多少呢？很明显，都是O(1)。 但咱们也不是葫芦娃，名字不能都叫一二三四五六七之类的，假如来的新人叫南宫大牛，那我们怎么分配他呢？ 这就引入了我们的第二个关键要素——散列函数。

散列函数

我们需要在元素和桶数组对应位置建立一种映射映射关系，这种映射关系就是散列函数，也可以叫哈希函数。 例如，我们一堆无规律的名字诸葛钢铁、刘华强、王司徒、张全蛋……我们就需要通过散列函数，算出这些名字应该分配到哪一号工位。

散列函数构造

散列函数也叫哈希函数，假如我们数据元素的key是整数或者可以转换为一个整数，可以通过这些常见方法来获取映射地址。

• 直接定址法直接根据key来映射到对应的数组位置，例如1232放到下标1232的位置。
• 数字分析法取key的某些数字（例如十位和百位）作为映射的位置
• 平方取中法取key平方的中间几位作为映射的位置
• 折叠法将key分割成位数相同的几段，然后把它们的叠加和作为映射的位置
• **除留余数法H**（key)=key%p（p<=N）,关键字除以一个不大于哈希表长度的正整数p，所得余数为哈希地址，这是应用最广泛的散列函数构造方法。

在Java里，Object类里提供了一个默认的hashCode()方法，它返回的是一个32位int形整数，其实也就是对象在内存里的存储地址。 但是，这个整数肯定是要经过处理的，上面几种方法里直接定址法可以排除，因为我们不可能建那么大的桶数组。 而且我们最后计算出来的散列地址，尽可能要在桶数组长度范围之内，所以我们选择除留取余法。

哈希冲突

理想的情况，是每个数据元素经过哈希函数的计算，落在它独属的桶数组的位置。 但是现实通常不如人意，我们的空间是有限的，设计再好的哈希函数也不能完全避免哈希冲突。所谓的哈希冲突，就是不同的key经过哈希函数计算，落到了同一个下标。 既然有了冲突，就得想办法解决冲突，常见的解决哈希冲突的办法有：

链地址法

也叫拉链法，看起来，像在桶数组上再拉一个链表出来，把发生哈希冲突的元素放到一个链表里，查找的时候，从前往后遍历链表，找到对应的key就行了。

开放地址法

开放地址法，简单来说就是给冲突的元素再在桶数组里找到一个空闲的位置。 找到空闲位置的方法有很多种：

• 线行探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置
• 平方探查法: 从冲突的位置x开始，第一次增加1^2个位置，第二次增加2^2...，直至找到空闲的位置
• 双散列函数探查法

……

再哈希法

构造多个哈希函数，发生冲突时，更换哈希

建立公共溢出区

建立公共溢出区，把发生冲突的数据元素存储到公共溢出区。 很明显，接下来我们解决冲突，会使用链地址法。