java中和hash相关并且常用的有两个类hashTable和hashMap,两个类的底层存储都是数组，这个数组不是普通的数组，而是被称为散列表的东西。
散列表是一种将键映射到值的数据结构。它用哈希函数来将键映射到小范围的指数（一般为[0..哈希表大小-1]）。同时需要提供冲突和对冲突的解决方案。
今天我们来学习一下散列表的特性和作用。
文末有代码地址，欢迎下载。
散列表的关键概念散列表中比较关键的三个概念就是散列表，hash函数，和冲突解决。
散列是一种算法（通过散列函数），将大型可变长度数据集映射为固定长度的较小整数数据集。
散列表是一种数据结构，它使用哈希函数有效地将键映射到值，以便进行高效的搜索/检索，插入和/或删除。
散列表广泛应用于多种计算机软件中，特别是关联数组，数据库索引，缓存和集合。
散列表必须至少支持以下三种操作，并且尽可能高效：
搜索（v） – 确定v是否存在于散列表中，
插入（v） – 将v插入散列表，
删除（v） – 从散列表中删除v。
因为使用了散列算法，将长数据集映射成了短数据集，所以在插入的时候就可能产生冲突，根据冲突的解决办法的不同又可以分为线性探测，二次探测，双倍散列和分离链接等冲突解决方法。
数组和散列表考虑这样一个问题：找到给定的字符串中第一次重复出现的的字符。
怎么解决这个问题呢？最简单的办法就是进行n次遍历，第一次遍历找出字符串中是否有和第一个字符相等的字符，第二次遍历找出字符串中是否有和第二个字符相等的字符，以此类推。
因为进行了n*n的遍历，所以时间复杂度是O(n²)。
有没有简单点的办法呢？
考虑一下字符串中的字符集合其实是有限的，假如都是使用的ASCII字符，那么我们可以构建一个256长度的数组一次遍历即可。
具体的做法就是遍历一个字符就将相对于的数组中的相应index中的值+1，当我们发现某个index的值已经是1的时候，就知道这个字符重复了。
数组的问题
那么数组的实现有什么问题呢？
数组的问题所在：
键的范围必须很小。 如果我们有（非常）大范围的话，内存使用量会（非常的）很大。
键必须密集，即键值中没有太多空白。 否则数组中将包含太多的空单元。
我们可以使用散列函数来解决这个问题。
通过使用散列函数，我们可以：
将一些非整数键映射成整数键，
将大整数映射成较小的整数。
通过使用散列函数，我们可以有效的减少存储数组的大小。
hash的问题
有利就有弊，虽然使用散列函数可以将大数据集映射成为小数据集，但是散列函数可能且很可能将不同的键映射到同一个整数槽中，即多对一映射而不是一对一映射。
尤其是在散列表的密度非常高的情况下，这种冲突会经常发生。
这里介绍一个概念：影响哈希表的密度或负载因子α= N / M，其中N是键的数量，M是哈希表的大小。
其实这个冲突的概率要比我们想象的更大，举一个生日悖论的问题：
一个班级里面有多少个学生会使至少有两人生日相同的概率大于 50%？
我们来计算一下上面的问题。
假设Q（n）是班级中n个人生日不同的概率。
Q（n）= 365/365×364/365×363/365×…×（365-n + 1）/ 365，即第一人的生日可以是365天中的任何一天，第二人的生日可以是除第一人的生日之外的任何365天，等等。
设P（n）为班级中 n 个人的相同生日的概率，则P（n）= 1-Q（n）。
计算可得，当n=23的时候P(23) = 0.507> 0.5（50％）。
也就是说当班级拥有23个人的时候，班级至少有两个人的生日相同的概率已经超过了50%。 这个悖论告诉我们：个人觉得罕见的事情在集体中却是常见的。
好了，回到我们的hash冲突，我们需要构建一个好的hash函数来尽量减少数据的冲突。
什么是一个好的散列函数呢？
能够快速计算，即其时间复杂度是O（1）。
尽可能使用最小容量的散列表，
尽可能均匀地将键分散到不同的基地址∈[0..M-1]，
尽可能减少碰撞。
在讨论散列函数的实现之前，让我们讨论理想的情况：完美的散列函数。
完美的散列函数是键和散列值之间的一对一映射，即根本不存在冲突。 当然这种情况是非常少见的，如果我们事先知道了散列函数中要存储的key，还是可以办到的。
好了，接下来我们讨论一下hash中解决冲突的几种常见的方法。
线性探测先给出线性探测的公式：i描述为i =（base + step * 1）％M，其中base是键v的散列值，即h（v），step是从1开始的线性探测步骤。
线性探测的探测序列可以正式描述如下：
h（v）//基地址
（h（v）+ 1 * 1）％M //第一个探测步骤，如果发生碰撞
（h（v）+ 2 * 1）％M //第二次探测步骤，如果仍有碰撞
（h（v）+ 3 * 1）％M //第三次探测步骤，如果仍有冲突
…
（h（v）+ k * 1）％M //第k个探测步骤等…
先看个例子，上面的数组中，我们的基数是9，数组中已经有1，3，5这三个元素。
现在我们需要插入10和12，根据计算10和12的hash值是1和3，但是1和3现在已经有数据了，那么需要线性向前探测一位，最终插入在1和3的后面。
上面是删除10的例子，同样的先计算10的hash值=1，然后判断1的位置元素是不是10，不是10的话，向前线性探测。
看下线性探测的关键代码：
//插入节点
void insertNode(int key, int value)
{
HashNode temp = new HashNode(key, value);
//获取key的hashcode
int hashIndex = hashCode(key);
//find next free space
while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
&& hashNodes[hashIndex].key != -1)
{
hashIndex++;
hashIndex %= capacity;
}
//插入新节点，size+1
if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
size++;
}
//将新节点插入数组
hashNodes[hashIndex] = temp;
}
如果我们把具有相同h(v)地址的连续存储空间叫做clusters的话，线性探测有很大的可能会创建大型主clusters，这会增加搜索（v）/插入（v）/删除（v）操作的运行时间。
为了解决这个问题，我们引入了二次探测。
二次探测先给出二次探测的公式：i描述为i =（base + step * step）％M，其中base是键v的散列值，即h（v），step是从1开始的线性探测步骤。
h（v）//基地址
（h（v）+ 1 * 1）％M //第一个探测步骤，如果发生碰撞
（h（v）+ 2 * 2）％M //第2次探测步骤，如果仍有冲突
（h（v）+ 3 * 3）％M //第三次探测步骤，如果仍有冲突
…
（h（v）+ k * k）％M //第k个探测步骤等…
就是这样，探针按照二次方跳转，根据需要环绕哈希表。
看一个二次探测的例子，上面的例子中我们已经有38，3和18这三个元素了。现在要向里面插入10和12。大家可以自行研究下探测的路径。
再看一个二次探索删除节点的例子。
看下二次探测的关键代码：
//插入节点
void insertNode(int key, int value)
{
HashNode temp = new HashNode(key, value);
//获取key的hashcode
int hashIndex = hashCode(key);
//find next free space
int i=1;
while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
&& hashNodes[hashIndex].key != -1)
{
hashIndex=hashIndex+i*i;
hashIndex %= capacity;
i++;
}
//插入新节点，size+1
if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
size++;
}
//将新节点插入数组
hashNodes[hashIndex] = temp;
}
在二次探测中，群集（clusters）沿着探测路径形成，而不是像线性探测那样围绕基地址形成。 这些群集称为次级群集（Secondary Clusters）。
由于在所有密钥的探测中使用相同的模式，所以形成次级群集。
二次探测中的次级群集不如线性探测中的主群集那样糟糕，因为理论上散列函数理论上应该首先将键分散到不同的基地址∈[0..M-1]中。
为了减少主要和次要clusters，我们引入了双倍散列。
双倍散列先给出双倍散列的公式：i描述为i =（base + step * h2(v)）％M，其中base是键v的散列值，即h（v），step是从1开始的线性探测步骤。
h（v）//基地址
（h（v）+ 1 * h2（v））％M //第一个探测步骤，如果有碰撞
（h（v）+ 2 * h2（v））％M //第2次探测步骤，如果仍有冲突
（h（v）+ 3 * h2（v））％M //第三次探测步骤，如果仍有冲突
…
（h（v）+ k * h2（v））％M //第k个探测步骤等…
就是这样，探测器根据第二个散列函数h2（v）的值跳转，根据需要环绕散列表。
看下双倍散列的关键代码：
//插入节点
void insertNode(int key, int value)
{
HashNode temp = new HashNode(key, value);
//获取key的hashcode
int hashIndex = hash1(key);
//find next free space
int i=1;
while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
&& hashNodes[hashIndex].key != -1)
{
hashIndex=hashIndex+i*hash2(key);
hashIndex %= capacity;
i++;
}
//插入新节点，size+1
if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {
size++;
}
//将新节点插入数组
hashNodes[hashIndex] = temp;
}
如果h2（v）= 1，则双散列（Double Hashing）的工作方式与线性探测（Linear Probing）完全相同。 所以我们通常希望h2（v）> 1来避免主聚类。
如果h2（v）= 0，那么Double Hashing将会不起作用。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/124240.html
相关文章
-
#yyds干货盘点# 3. 无转折不编程，滚雪球学 Python
摘要：在流程控制中，你将同步学到关系运算符与逻辑运算符。关系运算符在中关系运算符其实就是比大小的概念，所以要学习的就是大于小于等于等内容。逻辑运算符逻辑运算符在中有个，分别是。含有逻辑运算符的式子，最终返回的结果也是布尔值。 滚雪球学 Python，目标就是让 Python 学起来之后，越滚越大。三、无转折不编程如果...
-
#yyds干货盘点#——css移动端兼容
摘要：移动端的问题描述的边框。产生原因首先先要了解一个概念设备像素比，它是默认缩放为的情况下，设备像素和逻辑像素的比值。解决方式在滚动容器上增加滚动方法微软雅黑设置设置外部为设置内容元素为。内部元素超出即产生滚动，超出的部分隐藏。 移动端的 1px问题描述：1px 的边框。在高清屏下，移动端的 1px 会很粗。产生原因：首先先要...
-
#yyds干货盘点#k8s Service 资源及其模型
摘要：每个工作节点的组件通过持续监控着各及其关联的对象，并将对象的创建或变动实时反映至当前工作节点上相应的或规则上。资源都可统一根据其工作逻辑分为和这种类型。 Service 是 Kubernetes 的核心资源类型之一，通常被看作微服务的一种实现。它事实上是一种抽象：通过规则定义出由多个 Pod 对象组合而成的逻辑集合，以及访...
-
Flutter 中轮播图详解[Flutter专题31]#yyds干货盘点#
在 Flutter 中创建图像轮播 从社交媒体应用程序到电子商务应用程序，大多数现代应用程序都有某种图像轮播来展示产品、图像或广告。 由于 flutter 提供的内置小部件，从头开始实现图像轮播并不像您想象的那么难。 在本文中，您将学习如何从头开始创建图像轮播并根据需要进行自定义。最后，您将学习如何使用carousel_slider插件以更少的代码创建图像轮播。 这些是我...
