摘要：小概哈希容器也可以理解为是一种映射容器，采用哈希算法映射算法，散列算法，将不定长的数据压缩成定长的数据，这串定长值我们称为哈希值，并将不同的哈希值分组存起来，每一个分组我们认为是一个槽我们将不同的数据格式通过哈希算法，将其映射到不同的槽内，
小概
哈希容器也可以理解为是一种映射容器，采用哈希算法（映射算法，散列算法），将不定长的数据压缩成定长的数据，这串定长值我们称为 哈希值，并将不同的哈希值分组存起来，每一个分组我们认为是一个 槽
我们将不同的数据格式通过哈希算法，将其映射到不同的槽内，当我们需要取数据时，把需要的数据转化成哈希值，再凭借哈希值去找对应的槽，然后便可以将数据取出来
可以理解为一个键值对容器
put(key, value)
get(key)
图解如下
并且进行以下设定
$key$ - 键
$h_{key}$ - 哈希值
$hash(key)$ - 哈希算法
$bucket$ - 槽
$bucketNum$ - 槽数
哈希表我们现在假设 key 为整数，用 数组 分配槽的情况，并开始讨论如何设计，让对这一容器增删改查的时间复杂度趋近于 $O(1)$
哈希算法映射可以如下表示，下标 $n$ 代表变化的取值
$$(x_n, y_n) -> (x, y)$$
更通常的映射关系如下，并且我们在这里讨论这种情况
$$(x_n, y_n) -> (0, bucketNum - 1)$$
如何将不定长的数据压缩成定长的数据，我们主要给出以下几种常用的方法
线性哈希：$hash(key) = a × key + b $
平方哈希：$hash(key) = sub(key^2, a, b)$，设函数 $sub(num, a, b)$ 代表取 $num$ 第 $a$ 位数到第 $b$ 位数，则
余数哈希：$hash(key) = key % a $
入槽设 $bucketNum = 4，hash(key) = key % 4$，我们现在要对一对值为 6-"6号书籍" 的键值对进行如下操作
hashMap.put(6, "6号书籍");
hashMap.get(6);
那么，$hash(6) = 2$，并把 "6号书籍" 存入 $bucket[2]$ 中，查询时再取出 $bucket[h_6]$
碰撞处理我们处理$(x_n, y_n) -> (0, bucketNum - 1)$映射时，不定长的数据集可以认为是无穷大的，现在要将无限大的数据集压缩进有限数据集内，一定会引发 碰撞，即不同的数据装入一个槽内
解决冲突的方法有很多，我们主要给出以下几种常用的方法：
再哈希：遇到碰撞时，将哈希值再哈希，直到无碰撞
公共溢出区：将碰撞数据存入其中
接数据结构：碰撞时，往该槽内接入其他数据结构，并把膨胀的数据存入其中，如图解中接的就是 链表
性能瓶颈现在开始讨论如上设计哈希表的性能问题
我们在对容器进行操作时，处理最频繁的便是 $hash(key)$，每次存储和查找都需要计算 $h$，所以 如何设计哈希算法 便显得十分重要
另一个瓶颈在于，如何更加合理地分配 $ bucketNum $，能够尽可能地减少冲突，这也是一个值得思考的方面，我们要知道虽然我们对碰撞已经进行过处理，但这步操作也会损耗相当的效率
退一步来讲，假设已经出现碰撞，如何处理碰撞、碰撞的数据应当如何搜索 也非常值得我们考虑，比方说，若采用的是如图解中的链表法，假设 $bucketNum = 100$，但一堆数据很不幸运地落入同一个 $bucket$ 内，那么我搜索这堆数据时，和遍历搜索已经基本没区别了，时间复杂度趋近与 $O(n)$
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67540.html
摘要：前言在使用加载数据数据库常见的优化操作后端掘金一索引将放第一位，不用说，这种优化方式我们一直都在悄悄使用，那便是主键索引。 Redis 内存压缩实战 - 后端 - 掘金在讨论Redis内存压缩的时候，我们需要了解一下几个Redis的相关知识。 压缩列表 ziplist Redis的ziplist是用一段连续的内存来存储列表数据的一个数据结构，它的结构示例如下图 zlbytes: 记录整...
摘要：本篇的上篇为源码分析上。主体思路分析中使用的哈希函数，围绕初始化时使用的结构体展开。这样得到一个关于请求的首部哈希数组。源码中大多数的代码是跟预估表大小相关的。的哈希表的核心是表的管理结构体数组及表内存空间分配。 本篇的上篇为 Nginx 源码分析：ngx_hash_t（上）。 建议先读完上篇再来读下篇。 上篇回顾了hash表的基础概念，分析了Nginx中hash表的内存模型及逻辑...
阅读 3526·2021-10-09 09:41
阅读 2732·2021-10-08 10:18
阅读 2163·2021-09-10 10:51
阅读 2666·2021-09-10 10:50
阅读 761·2021-09-09 09:33
阅读 3368·2021-09-06 15:14
阅读 3002·2019-08-30 11:06
阅读 3229·2019-08-29 14:04
