03 | 哈希检索：如何根据用户ID快速查询用户信息？
该思维导图由 AI 生成，仅供参考
使用 Hash 函数将 Key 转换为数组下标
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了哈希表的实现原理及其在快速查询用户信息中的应用。首先介绍了使用有序数组和二叉检索树实现快速查询的方式，然后重点讨论了使用Hash函数将Key转换为数组下标，实现O(1)级别的查询能力。文章还探讨了Hash冲突的问题和解决方案，包括开放寻址法和链表法。通过链表法，可以很好地解决开放寻址法的冲突恶化问题，从而保证哈希表的检索效率。此外，文章还指出了哈希表的缺点，如需要足够大的空间和无法支持范围查询。总结指出，哈希表的本质是一个数组，通过Hash函数将查询的Key转为数组下标，利用数组的随机访问特性，使得能在O(1)的时间内完成检索。最后，文章鼓励读者深刻理解基础的数据结构和算法，为未来学习更复杂的系统打下扎实的基础。
《检索技术核心 20 讲》，新⼈⾸单¥59
全部留言(30)
- 最新
- 精选
徐洲更我这几天刚好看过一个C语言的哈希表实现源代码khash.h，它用的就是open addressing方法。 在删除元素的时候 不会真正的删除，会有一个flag记录状态。后续插入新的元素还能用。否则就会导致每次就要重新申请内存，rehash，计算量太大。链表法的话，删除的是对应的node ，时间复杂度是O(1) 所以删除很快作者回复: 是的。这种加一个flag记录状态的设计，其实在许多算法和系统中都有出现。是我们可以学习和掌握的一种方法。
2020-03-28322
每天晒白牙链表法可以直接删除，开放寻址法不行。 开放寻址法在 hash 冲突后会继续往后面看，如果为空，就放到后面，这样会存在连续的几个值的 hash 值都相同的情况，但如果想删除的数据在中间的话，就会影响对后面数据的查询了 可以增加一个删除标识，这种添加删除标识的在数据库中也常用作者回复: 没错！这种增加一个删除标识的做法，其实在许多算法和系统的设计中都有出现。也是一种常见的设计思路。
2020-03-28211
奕通过开放寻址法是不可以简单的删除元素的，如果要删除的元素是通过寻址法找的存储下标，那么该元素所在的下标不是本身 hash 后的位置 链表法是可以的：因为元素本身的 hash 值和存储位置的下标 值是一致的作者回复: 哈希表在查找元素的时候，不是只看下标的，还要对比下标位置的元素值，相同才算找到。这也是为什么会有线性探查等方法。 不能直接删除的问题在于，直接删除会把探查序列中断。举个例子:有三个元素a，b，c的hash值是冲突的，那么探查序列会把他们放在三个位置上，比如1，2，3（探查序列是123），如果我们把b删了，那么2这个位置就空了。这时候，要查询c，探查序列就会在2的位置中断，查不到c。
2020-03-277
pedro今天的内容权当回顾吧，期待后续的干货。作者回复: 对于有基础和经验的工程师，可以当做回顾。同时也思考一下工业界的实际实现方案。 在后面，我准备写几篇加餐，补充更多的实践工程内容。让有经验的工程师更有收获。
2020-03-2736
Bachue Zhou感觉当使用链表法时，哈希算法就不再是完整的搜索算法了，而只是为下一步搜索算法减少搜索范围的算法，至于下一步算法是什么，其实没啥限制，既可以是链表或平衡树，也可以是另一个哈希算法。作者回复: 你的这个思考很棒！我在前面的课程和后面的课程都会提到，不同的高效检索算法，其实本质都是快速划分检索空间，然后在子检索空间中再用合适的算法去检索。 因此，可以hash + 二叉树，或者数组 + bitmap，这些都是可能的解决方案。
2020-12-185
研发为什么哈希表没有有序存储的能力？ 有序存储指的不是存入和取出元素的顺序是一致的吗？哈希表本质是数组，数组是有序存储的，为什么哈希表不是？作者回复: 有序存储，你可以理解为按某种规则排序然后依次存储，然后访问时也能按这个次序依次取出。比如说，我们可以按数值排序从小到大存储，或者按数据进入时间排序从旧往新存储，这些都可以看做有序存储。 数组本身是支持有序存储的。但是，如果你给数组加上了限定条件，那么数组就会损失一部分能力了。比如说，栈也是使用数组实现的，但是它限定了只能后进先出，这样就失去了数组的随机访问能力(也失去了按值从小到大有序输出的能力)。 而哈希表限定了“用对象的哈希值作为下标直接存储和访问”，因此，哈希表中的数据是零散的，不连续的，也无法按照存入时间或者大小有序访问。如果你把数据进行了整理，那么就会失去哈希表的“用对象的哈希值作为下标直接存储和访问”的特点了。
2020-06-2624
yang看了一下评论区和老师的回复，先回答问题： 1. 链表法删除元素: 用Hash(Key)找到对应的下标，根据下标在数组找到了这个节点 node = table[index]，那删除就可以直接 node = node.next；这里数组里存的不是虚头节点呀，是真实的元素呀？ 2. 开放寻址法中的 线性探测、二次线性探测、双散列也好，都是在得到的index 对应的table[index] != null 的情况下，以不同形式继续找， 那我想问一下老师，这里table[index] != null 的时候，会比较 已存在元素 和 待插入元素的 key 吗? 也就是说， 开放寻址法是否允许key相同的元素存在呢? 因为我看文章，在开放寻址法中，只是判断 计算出来位置对应的元素是否存在，并没有比较存在时，两者的key是否相同。 如果允许元素的key相同，这样会影响删除方式。 如果允许key相同的元素存在，删除的时候应该用同样的开放寻址法找到最后一个不为空 且key相同的元素置为null。 如果不允许key相同的元素存在，那就像老师给其他同学评论的，a b c计算出的hash值相同，位置连续， 删除b，会出现空洞的情况，影响这一局部元素的插入 删除 查询。老师给出的方法是：增加标记位，删除为true， 查询、删除遇到删除=true的情况可以继续往后找，新增元素 遇到 删除=true的时候可以直接替换，并修改状态为false; 疑问: a. 不管是 线性探测法、二次探测法、双散列，只要到了数组最后一个元素发现是满的时候，就会扩容 产生rehash吗？ b. 不论是 线性探测法、二次探测法、双散列，他们在插入元素的时候，会比较已存在元素和待插入元素的key是否相同吗？也就是说允许key重复的元素出现吗？ c. 线性探测法步长为1，二次探测法采用index = index + 2^i (i为第几次探测)进行探测、 我想问的是双散列，第一次通过Hash(Key)得到的index位置上有元素，那么第二次的Hash函数是不是就是上一次用到的Hash函数呢? 另外，每次Hash的时候，其中的key是怎么变的啊？ 字有点多，恳请老师见谅～！作者回复: 你的思考很细致！非常好！ 1.链表保持一个虚的链表头，这样会更易于操作。 2.扩容时机其实不是等到数组满时才扩容，而是在装载因子超过一定阈值时就会触发。否则哈希表的效率会很差了。 3.一般来说，哈希表是不允许插入重复的key的，会覆盖。不过也有改造的支持重复key的哈希表，如multiHashMap。 4.关于多个哈希函数的问题，其实有两个哈希函数就可以生成多个不相关的哈希函数。假设有两个哈希函数f1和f2，那么f3=f1+2*f2，f4=f1+3*f2，以此类推。因此，双散列的具体公式应该是 h(key，i) =( h1(key) + i*h2(key) ) % 数组长度
2020-04-093
aoe原来处理冲突还可以用“开放寻址”的方法！又学习了通过flag标记可以解决删除问题。强大的flag，环形数组也用了这个标记，让实现变简单了，还给flag起了个拉风的名字“哨兵”作者回复: “立个flag”其实是蛮有用的事情。你会发现，在许多系统中，删除其实代价都不小，因此，许多系统对于删除操作都分为了“立flag”，“事后清理”的机制。 比如说，操作系统删除文件，就会先放入垃圾箱； 再比如说，数据库设计时，也经常会为数据设立一个“是否有效”的字段，删除其实是将字段状态修改。
2020-04-023
阿斯蒂芬哈希（散列）算得上是基础常用的top3数据结构了吧。 写几点感悟： 一：散列函数的耗时为什么被「忽略」？ 之前在阅读《算法图解》中，散列表有一段这样的描述： 「你结合使用散列函数和数组创建了一种被称为散列表（hashtable）的数据结构。散列表是你学习的第一种包含额外逻辑的数据结构」 我觉得这个「包含额外逻辑」从一个特别的角度描述了散列表的特性。比起数组和链表家族，散列表的存取阶段都多了一步「计算散列（哈希）值并映射」的过程，其实这个就是额外的逻辑。然而经常在讨论散列表的性能时，通常会「达成共识忽略」这一步的性能和具体实现细节。其实为什么呢？ 尝试理解下：就如老师举例说明的使用英文字母序号做系数再加上二十六进制指数的「魔法」一样，散列值的本质就是「计算」，而恰恰现代计算机最强的功能之一就是计算，感谢数学家和计算机科学家的努力，发明高效且分布均匀的散列函数，可以说几乎对大多数程序员的大多数场景下都是透明的，我们可以接近将这一步骤当作常数级别的耗时，因此在分析散列表的总耗时的时候，可以愉快地忽略，而只需要关注真正用于检索的耗时，比如定位到了索引后可能需要的内存交互甚至磁盘交互的耗时。 二：开放寻址法如此「不堪」，有什么应用场景？ 虽然讲到散列冲突的解决方案，开放寻址法总是第一个拿出来被「锤」，但是既然天天被吊打，为什么还要学，实际有什么用处？这里又到了应用「实际场景」的思维模型了。Java的ThreadLocal用来存储线程隔离的本地变量，其中有个ThreadLocalMap散列结构，内部解决散列冲突的策略就是开放寻址法。为什么它会这么淡定使用呢，个人理解还是因为它的使用场景相对简单，一般往ThreadLocal中存放的数据量不大，使用开放寻址而不是链表法，节省了链表的指针开销，而且兼顾了效率，ThreadLocalMap的场景非常契合开放寻址的优点。 以上两点感悟还处于自我总结阶段，没有很多查证，还望老师指点。作者回复: 你的思考非常好！你提的这两点都是在工程中需要考虑到的效率问题。你往下看第四讲，你就会发现，为了节省一次哈希计算，我们可以在合适的场景下直接用位图；还有布隆过滤器其实就是使用开放寻址法解决冲突的思路。 就如你所说，所有的实现都有利有弊，我们要熟悉它们，然后考虑“实际场景”，才能做出合理的设计和实现
2020-04-122
峰不能，这样不能和数据不存在的情况区分，链表法就可以了，核心考量是冲突元素是否是聚集的。 hash 表中的hash 是一个将key 转化成数组下标的映射关系，我们这里只讲到这个转化尽可能的均匀的散列，但如果加上尽可能保留原始key 空间的距离大小信息(以前我学降维得出的结论是数据降维要做的事情是把你想从高维空间保留的信息尽可能在数据的低维表示上同样成立)，是否就可以在一定程度上解决hash 完全没法做范围查询的缺陷，好早之前看过点局部敏感hash 的一些东东，想来应该可以结合。作者回复: 是的。直接删除会有问题。探查链条会被终止。 局部敏感哈希能在距离信息进行一定的保留，因此在近似检索中是一个方案。在进阶篇我会介绍。
2020-03-272