Hash算法、hash_table、一致hash名词解读
haoteby 2024-11-11 12:45 6 浏览
前言
Hash（哈希）作为一个coder面试中高频出现的名词，了解掌握它非常重要；
但其实，很多同学对于这些名词经常搞混，或答非所问，或不得要领；
本文就这些基本名词作一些解释，希望能帮助看到的同学梳理知识点，提供一些帮助。
本文会围绕名词解释进行。
名词解释
- hash、哈希
- hash也就是哈希，也叫散列，其实算是一种技术；
- 通过hash函数，将一组输入映射到一个限定范围内数值；
- 哈希算法
- 这里就举个最简单的例子，这个例子将一个任意整形，映射到0-9范围内。
int hash_func(int input){
return input%10;
}- 哈希冲突
- hash冲突就是多个输入产生了同样的映射地址，比如上面的例子，1和11输出都是1，这就是hash冲突；
- 由于应用场景的需要，优秀的hash算法总是尽量避免hash冲突；本篇暂不深究冲突解决；
- hash_table
- 一种基于hash（映射）的数据结构，用于存储kv类数据；
- 原理是根据输入key，通过hash算法，直接计算出存储地址；
- 在解决好冲突的前提下，他的存取效率非常之高，因为只需要执行一次hash函数计算，性能O（1），而像map之类的结构，则需要经过多次查询，效率O（lgn）；
- 一般不需要排序并且数据量比较大的数据，都可以使用hash_table来存储。
- hash_map
- 各种库里基于hash_table实现的数据结构基本都叫这个名字，stl里的hash_map已经被unordered_map实现代替了。
- 一致性hash
- 一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对k/n个关键字重新映射，其中 k是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。【wiki】
- 一致性hash主要用于解决分布式缓存问题；
- 一个典型的用法是，将分布式节点hash到一个整数环，环上的每个间隔视为一个槽或者桶；
- 目标数据的key同样hash到这个整数环上，依据处于环上的位置获取应该存储的节点；
- 当一个节点移除时，只需要将从这个节点位于环上位置到下一位置之间的key进行重新hash缓存即可；
- 当新增一个节点时，也同样只需要将这个节点位于环上位置到下一位置之间的key进行重新hash即可。
如果还有不清楚的，评论区见
相关推荐
- 5个珍藏多年的资源网站，免费又实用，建议收藏
-
今天给大家分享5个珍藏多年的资源网站，每个都是免费的，而且非常的实用，建议收藏。1、wallhaven一个国外知名的壁纸网站，拥有海量的8k、4k的超清图片壁纸，该网站的图片是由各地的创作者提供下载，...
- 设计网站推荐 | 国内外设计类素材网站
-
网站分享|十个不得不推荐的设计类素材网站！一些压箱底的常用的设计类素材分享！一定要打开这些网站试一试哦！...
- 阿里巴巴旗下菜鸟裹裹换新LOGO?长高了
-
LOGO大师整理编辑（ID：logods）...
- 10个做PPT必备的素材网站，越用越上瘾，每个都是宝藏
-
Pexelshttps://www.pexels.com/zh-cn/...
- 阿里旗下的四款免费小工具 好用并且能大大提升工作效率
-
好的工具能大大的提升你的工作效率，今天给大家分享的是阿里旗下的四款经典免费小工具，主要是用来设计，能方便，且高效的提高你的工作效率，觉得有用就收藏了吧。第一个：阿里巴巴图标库阿里巴巴图标库有将近80多...
- UI设计入门干货!八大软件+技能+素材网站
-
随着互联网行业的发展，UI设计师越来越多的被提及，UI设计师大火，需求岗位越来越多，也有越来越多的人转行投身UI设计师。UI设计是什么？一般所说的UI设计多指UI视觉设计，主要负责APP、Web、H5...
- 干货!宝藏PPT素材——海量图标免费使用
-
我是星辰四个月的假期收集了一些PPT素材，筹备了这个公众号今天终于和大家见面了此公众号不定时更新各种素材干活和PPT模板记得关注我哦~后台发送“PPT”领取免费PPT模板总是很难找到合适PPT素材？费...
- 写了100多篇原创文章，我常用的在线工具网站推荐给大家
-
摘要不知不觉写博客已经一年多了，累计写了100多篇原创文章，今天给大家分享下我经常使用的在线工具网站，希望对大家有所帮助！MarkdownNice支持自定义样式的在线Markdown编辑器，编辑完成...
- 设计者必备神器:必须收藏的在线软件推荐
-
本内容来源于@什么值得买SMZDM.COM｜首席生活家保密对于新电脑或重新刷系统的电脑，安装一堆软件是很费时间的，而软件多了会对系统运行速度有影响，特别是机械硬盘，响应时间与软件数量成正比的。而用了...
- 干货 | 设计师必备网站，大神作品、图片素材一网打尽
-
经常会听到这样的一句话：设计师每日正式开始工作的第一件事，就是打开3个及以上的设计/素材网站。网站中的优秀作品不仅可以帮助设计师提升自己，还能激发创作的灵感，所以今天，我们为大家整理了一些国内外优秀的...
- 推荐11个超好用的在线作图网站
-
现在做图好像已经不是设计师的专利不管是新媒体人、文案，还是随便一个人不会随时随地做几张漂亮图不能分分钟出点海报、封面图、邀请函什么的还怎么昂首挺胸在办公室里混不会PS没关系，不会做图可不行所以今天老贼...
- 做设计还只知道花瓣包图网?这100+个免费商用素材网站送给你
-
作为设计师你常用的网站是哪些呢？花瓣？站酷？千库？千图？包图？这些网站确实是大家最常用的网站，各种风格的元素、模板、源文件，用起来可以说是得心应手了~但是一旦出现了这个场景，你就也跟着崩溃了........
- 5个好看的图标网站，直接搜索下载
-
今天和大家分享5个图标网站，里面收录大量丰富的图标，在这里找到好图标不是什么难事。Iconsdbwww.iconsdb.com...
- 8个高清无版权的图片资源网站，质量高又免费，够你用一辈子
-
很多时候我们找素材总是要花费很多时间，今天就给大家分享8个，高清无版权的图片资源网站，质量高又免费，够你用一辈子。01*Logosc...
- 淘宝PPT设计师不会告诉你的4个网站!帮你剩下不少钱
-
之前的文章中，给各位推荐过图片素材网站，像：500px，unsplash等，也给各位推荐过图标网站，像阿里巴巴图标库。这些网站都很好用。但是，我最近发现，有一类素材网站，在做PPT时也会经常用到，...