散列表的相关概念

HashMap是Java源码中非常优秀的源码，涉及到很多的概念，算法、红黑树、数组、链表... 之前也尝试过硬着头皮去学习，但是由于基础本身就不是很牢固，所以后面也没有多少收获。那么，这次笔者先来梳理一下HashMap的一些概念。

1. 散列函数

 Hash函数，可译为“散列函数”或“哈希函数”。**就是把任意长度的输入，通过散列算法，映射成固定长度的输出，该输出就是散列值。**这是一种压缩转换，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不能通过散列值唯一的确定输入值，但有一点可以确认的是不同的输出肯定对应不同的输入。散列函数简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

​ 一个好的散列函数应（近似地）满足简单均匀散列：每个关键字都被等可能地散列到m个桶中的任何一个，并与其它关键字已散列到那个桶无关。

桶的概念请看本文第三节

 将散列函数单独提出来写，是由于散列函数的概念也就这些，先来提前熟悉概念，后面可以不用这样书面化。要想知道更多，就继续看下面的内容吧。

2. 散列表(哈希表)

 散列表（Hash Table）是根据关键码值(key value)而直接进行访问的数据结构。他通过关键码值映射到表中的一个位置来访问数据，以加快查找速度。这个映射函数就叫做散列函数，存放记录的表叫做散列表。

 看到这里，先不要懵，来看下面的解释。

 散列表是基于数组的，那么要访问数据，就需要相应的地址(索引)。是怎么得到这个地址的呢？  例如现在有一个任意的关键字值key，一个函数f(key)，通过函数f(key)计算关键字key就可以得到相应的地址。这个函数*f(key)*就是散列函数。

 在散列表中，通过hash函数计算后的散列地址都是整数类型的。

(1) 构造散列表的几种方法。

a. 直接寻址法

 取关键字或关键字的某个线性函数的值为散列地址。即H(key) = key 或 H(key) = a.key + b;

b.数字分析法

 分析一组数据，找出数据中差别较大的部分，构成散列地址，这样能很好地避免冲突。

 举例：有一组文章的创建时间数据

 分析上面的表格，得出每个文章的创建时间的前面4位都差不多，如果使用这4位来创建散列地址，造成的冲突可能会很大。而这些创建时间的后面8位则相差很大，这时候使用后面8位来创建散列地址，就可以很大程度上面避免冲突。这就是数字分析法。

c. 平方取中法

 平方取中法很简单，如题。平方取中法就是取关键字的平方后的中间几位数字作为散列地址。

d. 折叠法

 折叠法就是将关键字分割成位数相同的几部分，最后一部分的位数可以不同，然后取这几部分的叠加和（舍去进位）作为散列地址。

e. 随机数法

​ 选一个随机函数，取关键字随机函数值作为散列地址。H(key) = random(key)， random()为随机函数。

f. 除留余数法

 取关键字被某个不大于散列表表长m的数p除后所得余数为散列地址。 H(key)=key MOD p (p<=m)。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

(2) 冲突

 概念：不同的关键码值映射到相同的同一散列地址。

  解决办法

a. 链接法(Channing)

  在链接法中，在散列到同一桶中的所有元素都放在一个链表中。

 链接法的理解含简单，当遇到散列地址相同的是时候，在散列地址对应的桶中，生成一个链表，链表存储这些发生冲突散列地址相同的关键码值。具体类型可以参考下图。

桶的概念请看本文第三节

b. 开放寻址法(open addressing)

 在开放寻址法中，所有的元素都存放在散列表中，也就是说每个表项或包含动态集合的一个元素，或包含NIL。当查找某个元素时，要系统地检查所有的表项，知道找到所需的元素，或者最终查明该元素不在表中。不像链接法，这里既没有链表，也没有元素存放在散列表外。因此在开放寻址法中，散列表可能被填满，以至于不能插入任何新的元素。该方法导致的一个结果便是装填因子α绝对不会超过1（α≤l）.

 开放寻址法就是一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

 Hi = (H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列。di可有下列三种取法：

 （1）di=1,2,3,…, m-1，称为线性探测再散列；

 （2）di=12, -(12), 22, -(22), 32, …, ±(k2),(k<=m/2)，称二为次探测再散列；

 （3）di=伪随机数序列，称为伪随机探测再散列。

 所谓伪随机数，用同样的随机种子，将得到相同的数列。

c. 再散列法

 再散列法理解起来很简单，就是在冲突发生的时候，利用不同散列函数，计算另一个散列地址，知道冲突不在发生。这种发放不容易产生“聚集”，但增加了计算时间

 即：Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函数。

d. 建立一个公共溢出区

 把冲突的数据都放在另一个地方，不在表里面。

3. 桶

A bucket is each element in the Array you are referring to.

 这里要单独拿一节来说桶，是因为我自己一直都不能理解桶这个概念，经常在看到这个概念的都是一头雾水，希望能给看到这篇文章并且存在同样疑惑的同学一些帮助。

 桶就是数组中的每个元素。

 HashMap初始化时，会创建一个长度为capacity的Entry数组。数组中每个存储元素的位置就被称为桶(bucket)。每个bucket都会有指定索引，可以通过索引快速访问bucket。

 无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的桶(bucket)中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。

扩展 What exactly is bucket in hashmap?

 以上都是我自己的一些整理和理解梳理的概念。