接下来我们要讲一个很重要的知识点，叫哈西。哈西是一类算法，注意我的用词，我说的是一类算法，不是一种算法，它有很多种算法，算法其实就是功能吗？我们可以把它看成是一个函数， 然后可以给他传一段内容，他经过运算之后会返回一串哈系直。当然也有人叫散劣子，叫什么都没关系，我们这里就称他为哈系直了，他就是一串之无串。常见的哈系算法也名第五、 sha、 一二五六五幺二等等， 他们的功能都是一样的，只是算法的复杂程度不一样。不过现在 md 五和 sha 已经被破解了，我们要用的话至少要用 sha 二五六。至于这些算法背后是怎么实现的，我们就没必要关心了，因为这是一道很多的数学知识，我们并不是研究数学的。现在我们需要关心的是这个哈西子他有什么特点？ 他的第一个特点就是输入敏感，只要我们输入的内容发生任何一丁点变化，哪怕你只改了一个标点符号，新的哈蝎子，都会出现 巨大的变化。如果我们输入的内容一样，使用的哈吸算法也一样，那得到了哈吸值也一定是一样的。而哈吸值的第二个特点是不可逆，就是说我们不能根据哈吸值反对出来传输的内容是什么。再来看第三个特点，计算极快而长度固定， 一部十个 g 的高清电影和一个是 kb 的文本文件，都可以在零点一秒内得出结果。也就是说，不管你长得有多胖，骨头有多硬，对于火葬场来说，把你化成灰都是一把火的事情，而且只要采用的哈西双法一样， 返回的哈系直的长度也都是固定的，假如十个 g 的文件算出来的哈系直长度是三十二，那十 kb 的文件算出来的哈系直长度也是三十二。然后我们再来看哈系算法有什么用途， 前面我们说对于同一个哈气算法，输入的内容只要不变，得到了计算结果也不变，这就可以拿来做密码加密了。现在我打开 qq 的登录界面，然后我在这里输入账号，输入密码，这时候当我们点击登录之后，这个 qq 的客户端就会把我们输入的账号密码连着网络传输到 qq 的服务端去，然后服务端再做判断，判断我们输的账号密码对不对，如果对上了就让我们登录成功。但是你有没有想一个问题，只要我们的数据通过网络传输，那我们这个数据包就有可能被别人捡获到。我们现在还没学网络相关的知识，我就简单发个图给你看。 这是 qq 的客户端，然后这是 qq 的服务端，当你点击登录之后，你的账号密码就会沿着网络传输到服务端，而我这时候作为一个攻击者，我就从这中间把你的数据包给截取到，截取到之后我一看发现居然是明文的账号是六六六，密码是一二三，然后我就可以登录你的账号了。
粉丝5.3万获赞38.1万
相关视频
02:31查看AI文稿AI文稿现在我们再来看一下哈西缩影接口，为了便于理解，我们还是直接来看图，看不懂对吧？没关系，了解就行。首先这里有一张员工表，然后这里还有一张哈西表，哈西表其实就是一个数组，你可以暂时理解为拍摄里面的列表，我们可以通过列表的缩影快速访问对应的值。 这里为了区分列表的缩影，我们就暂且把列表的缩影称之为下标。 ok， 现在假设我们要给内幕之段建立哈西，所以那就要拿到所有的内部之段，然后他内部有一个特殊的哈西函数， 我们把内幕传给这个哈西函数，他就会计算出来一个哈西马，这个哈西马一定会等于哈西表里面的某一个下标，比如把刘备传给他，计算出来的哈西马是二，接着就把刘备这一行数据的地址存到哈西表下边二的位置，以后要找刘备这一行数据，就可以通过这个地址找到他。 当然这个地址是我乱写的，我们就假设刘莎莎是刘备这一行数据的地址，然后再来计算关羽的哈西马，假设是一，那就把关羽这一行数据的地 选到哈西表下边唯一的位置，接着计算张飞的落在五号位置，黄忠落在六号。最后还有个马超，假设我们的数据量比较大，马超大，哈西马计算出来刚好和黄忠的一样，有可能吧，这个我们讲哈西的时候也说过，称之为哈西碰撞或者哈西冲突，这种情况怎么解决呢？ 其实也很简单，在他后面加一个列表，然后记录马超这一行数据的地址就可以了，如果以后再出现哈奇马为六的，那就继续在这个列表中追加就可以了。 ok， 这就是哈西所赢，相信你也发现了，哈西所赢他只能找固定的值，也就是说他只能做等值匹配， 如果要查一个范围的数据或者进行排序的话，哈西所以你就做不到了。但他也有自己的优点，就是查询效率极高，大部分情况下效率都要比毕加速高，因为通常他只需要做一次检索就可以找到对应的数据。比如要找刘备，那就把刘备进行哈西运算，然后得到哈西马， 拿到哈西马直接就可以找到数据对应的地址。注意，我说的是大部分情况下只需要检索一次，因为一旦出现了哈西冲突，还需要去列表里面进行查找。 ok， 这就是哈西索银。 在麦搜扣里面， memory 引擎就支持哈西索引。 memory 我们知道它的数据是存在内存的，加上哈西索引的加持，数据的查询速度是非常快的。 不过现在 memory 已经被另外一款数据库软件 redis 替代了，它的数据也存在内存的，但我们知道内存和硬盘不一样，内存空间有限，而且断电数据会丢失，所以一般都是用来做缓存。 redis 我们后面也会讲，现在你先有一个印象， ok， 在 mercicle 里面，除了 memory 支持哈奇索音外， innot 里面也有一个自适应哈吸功能， 这个功能会根据我们的查询条件，在特定情况下自动根据毕加速索引构建哈西索引，当然他是自动的，不需要人为干预。
236小飞有点东西
02:44
07:46查看AI文稿AI文稿大家好，今天要讲的内容是哈西表 hash table。 先来看一个简单的问题，已知数组 a 其中保存了 n 个整数，我们要从数组 a 中查找整数 k， 确定 k 是否存在。数组 a 中 最朴素的方法是使用循环，将 k 和 a 中的每个整数按顺序比较，如果相等，直接返回一，循环结束后返回零。 这种方法虽然简单直接，但是效率很低。如果数组 a 中有大量元素，并且需要多次查找时，那么这种方法的效率将无法容忍。 例如，在数组 a 中保存了七、十、七、五等数字，如果循环查找一、二、三等，等到十，这十个数字是否在数组 a 中， 那么就需要调用十次 fantasy 函数进行查找。所以每次调用 fantasy 函数都要比较 n 次，因此查询的时间复杂度是大 on。 如果查询次数也为 n， 那么整体的复杂度就是大 on 的平方。 实际上，我们希望设计一种算法，使每次查找的时间复杂度为常数级 w 一，这样查找效率 与待查找表中元素数量就是无关的。那么这种方法就是今天要介绍的阿西表 ash table。 先来看一个哈西表的特例情况，假设待处理数据的范围是零到九十九，此时可以直接使用一个 a 一百数组，用它的下标来记录零到九十九之间的这一百个元素是否出现，出现了多少次。 例如，数字五出现了一次，那么 a 五就等于一九出现了三次， a 九就等于三。这是最简单的哈西思想 样例代码如下，在使用哈西表之前，需要先创建哈西表，在内函数中设置一个长度是一百的数组 table 初始化，其中的元素为零，作为哈西表的表体。然后使用函数 create has 创建哈西表。 在 create hash 函数中，使用 i 电力数组 a 中的全部 n 个元素，通过 table ai 加加。利用 table 数组的下标记录数字 ai 出现的次数。 例如，当 i 等于零时， a 零等于七， table 七加加， i 等于一， a 一等于十七， table 十七加加， i 等 等于二， a 二等于五， table 五加加，这样就记录了七十七、五，这三个数字各出现了一次。 完成哈奇表的建立后，便利 table 数组得到每个数据出现的次数。如果 table i 大于零，那么打印 i 值出现的次数 table i。 例如，二出现了两次，三出现了一次，五出现了两次等等。 从哈奇表中查找某个 k 值是否存在，非常的简单，直接返回 table key 不等于零的结果就可以了。也就是如果 table key 不是零，那么返回一，否则 返回零在内函数中，我们使用函数 find k 查找一到十是否出现在数数 a 中，这里给出了对应的运行结果。 如果数组 a 中的数据范围不是零到九十九，而是 int 型，从负的二到三十一次方，到二到三十一次方减一， 或者 a 是浮点，数字符串，甚至是数组对象等等。更复杂的元素应该怎么样处理呢？ 这时就需要使用哈奇函数将数据转换为表长范围内的整数， 将这个整数作为数组下标，访问哈西表。对于整数型数据，可以直接将它取于表长，得到对应的数组下标。 例如，如果要将五二三插入到长度为一百的 table 中，用五二三取一百等于二十三，再将 table 二十三加一，那么 table 的下标二十三就记录了五二三这个数字。 如果数据是字符串，则需要专门的设计哈奇函数。 最简单的，比如便利字符串中的字符，将他们的 as， car 码相加得到整数，再取于表长得到哈锡纸。 例如字符串 a、 b、 c 中的 a、 b、 c 三个字符 ask 二码分别是九十七、九十八、九十九，将它们相加，得到二百九十四。取于一百是九十四， 那么 table 九十四就记录了字符串 a、 b， c 是否出现 阿西函数可能将不同的数据映射到同一个数组下标上，这时就发生了冲突。例如按照刚才的方法，五二三和二十三会同时映射到 k 包二十三， a， b， c 和 c， b， a 会 同时映射到 table 九十四。当冲突发生时，就会导致查询出现错误，例如此时我们查询一二三二二三三二三，或者 a、 b， c， c， b， a， a， c， b 等等，都会返回真， 但并不能确定具体是哪个数据真的出现了。 关于哈西表冲突的解决，有很多经典的方法，例如线性探测法、拉链法等等，都可以解决这一问题。 实际上，解决哈西表的冲突是哈西算法设计中最为重要的部分，后面也会为大家介绍相关的内容， 那么到这里，哈西表 hostable 就讲完了，感谢大家的观看，我们下节课再会。
558小黑黑讲AI
03:31查看AI文稿AI文稿每天一条，讲清一个技术底层逻辑。今天分享一致性 hash 如何从简单眼镜到虚拟节点。你有没有想过这个问题，为什么百万 qps 时，一致性 hash 是 完美方案，但到了千万 qps， 很多大厂却要改造甚至重写？ 首先要搞清楚一个前提，一致性 hash 只适合有状态路由，比如缓存、分片、绘画、保持。如果你的服务是无状态的，轮询就够了。它要解决的核心矛盾有两对， 我们从最简单的 hash 取模说起。假设五台缓存节点承载十万 qps， note 等于 hash 括号， t 括号对 n 取模公式简单、分布均匀、小规模集群的合理起点。问题出在扩容时，从五台扩到六台，你猜有多少 t 会重新映射？ 答案是百分之八十三。更可怕的是，百万 qps 场景下，这百分之八十三的缓存瞬间失效，流量直接穿透到数据库，引发缓存血崩。一致性 hash 用一个环形空间解决这个问题， 把节点和 key 都映射到零到二的三十二次方减一的环上，每个 key 顺时针找到的第一个节点就是它的归属。新增节点 d 时，只有 d 和它前一个节点之间的 t 受影响，从接近百分之一百的失效率降到了只影响约百分之五。我们来对比一下二十个节点的级群。新增一个节点 has 取模会导致百分之九十五的 t 重新映射，一致性 has 只影响百分之五。在百万 qps 场景下，这个差异决定了系统是否会被打垮。 但一致性 has 也有问题，那就是数据倾斜，当节点数量少的时候，负荷可能严重不均。三个节点的情况下，最重的节点可能是最轻的六倍。百万 qps 的 集群，一个节点扛五十万，另一个只分到八万，这就是第二对矛盾的体现。虚拟节点就是为了解决这个问题， 每个物理节点不再只是环上一个点，而是映设为多个分身。三个物理节点每个配五十个虚拟节点还上，就等效于一百五十个节点附在倾斜大幅改善，这就是用大数定律换均匀性 虚拟节点也有代价。路由表要维护更多节点查找要做二分。千万 qps 场景下，二十个物理节点配一百个虚拟节点，路由表有两千个点，每次查找约十一次，比较，虽然内存占用不大，但 cpu 缓存命中率会受影响。 到了千万 qps 集群往往是易购的，经过多轮扩容，有老服务器，也有新服务器，这时候需要加全虚拟节点，高配三十二核给二百个虚拟节点，低配八核只给五十个，按能力分配流量，这才是合理的。 即使加权了，还是可能出现局部过载，比如热点 key 集中在某个区间。 google 提出了有界负债一致性 hash， 每个节点是一个负债上限，平均负债的一加 excellent 倍，超过上限就顺时针溢出到下一个节点，这个 excellent 就是 路由一致性和负债均衡之间的旋钮。一致性 hash 并不是唯一选择 jump hash 零内存，但只能尾部追加。 rounddev hash 支持任意增删，但计算复杂度是 o 括号、 n 括号。在千万 qps 的 工程事件中，一致性 hash 加虚拟节点仍然是最成熟的方案，节点故障是必然事件，朴素一致性 hash 会把故障节点的全部负债压到下一个节点，可能引发连锁崩溃。 虚拟节点方案会把负债分散到多个物理节点，这在千万 qps 场景下是比正常均衡更关键的能力。从 hash 取模到有界负债，每一步都是解决上一步的痛点。 hash 取模解决不了伸缩问题，一致性 hash 解决了伸缩，但负债倾斜， 虚拟节点解决了倾斜，但无法应对异构集群加权，虚拟节点又无法应对动态波动，这就是从十万到千万 qps 的 眼镜逻辑。这么长的视频你都看完了，点个关注吧！
32柯杰
04:56查看AI文稿AI文稿reddies 中的散列表也叫哈西表或者哈西奥，他是什么形式呢？他是 k filed y 六 字段值这种形式啊，就一个键，他可以对应着多对这个字段和值，然后同一个散列表里的字段是不可以重复的，但是不同这个散列表里的，因为你 k 是不重复的，但你的字段爱重复重复啊，但是同一个散列表里不可以啊。 嗯，就是这样。然后我们看一下他的基本操作，首先我们怎么 c 的呢？就是 hc 糖，然后可以设置一到多段这个字段和直 啊，但是注意就老版本他只能设置一对啊。呃，然后他老版本想要设置多个是 hmc， 但是新版本都给他合成一个了啊，然后他老老老的这个还能用，但他不推荐再使用了啊。 hmc， 然后注意，我们补讲一下，就昨天昨天说的这些，我 们这些就是 ces 的这些选项。呃，如果有单独的命令，现在也是推荐用单独的命令啊，这种选项现在也是不推荐用了。 让我们接着来看啊，我们来见一下 ready 斯克林。这个因为是除夕，所以我弄了一个红色的命令，行，对吧？就这一天，然后明天我们变回黑色。呃，我们 h sit 可以设置啊 k， 比如说 哈西啊，就叫 h 一 filed filed 呢，我随便就是 f 一，然后 y 六 v 一，然后我可以再设置 f 二 v 二，没有问题啊，我们存进去了两对，对吧？ 让我们如何获取呢？就爱吃给他这个他是获取一对，现在暂时还不能获取两对爱吃给，比如说 我们要获取 h 一比的 f 一，然后他是 v 一，没有问题啊，然后我们要偏要获取怎么办呢？ hm get 啊， hm get h 一 f 一 f 二啊，是不是这样 v 一 v 二被获取出来了，然后我们要获取全部呢？还是给他奥，然后把 k 填进去就行了。 h get 哦，比如说我们获取 h 一可以看到啊，这样， 但是他会把我们的 fail 的也给获取出来啊。 fail 的和 y 六，然后我们怎么删除呢？我们，呃，我们可以用直接 d， e， l 删除这个 k， 但这是整个删除整个哈系表，你要只想删除一个字段或者多个字段呢？就是 h， d， e， l， k， 然后 failed， 你要删除几个就删除几个，我们不演示了，然后仅在它不存在的时候添加，就是 h sit n， x not exist， 对吧？这个我们也不演示了吧。 h case 啊，查看一个伞列表中所有的字段。 h case h 一啊，这样看我们的 f 一和 f 二就出来了。 h values 啊，查看他所有的 value 还是愣啊，就看他一共有多少对儿这个 filed value h excess 的，看一个字段是否存在啊。 克斯斯特斯。那么 h 一，比如说我们看 f 三是不是存在，不存在就是零，存在几个就是几高，但它就只能一连和一对吧。呃， h string 论啊，这个是查看它 y 六的长度， 跟我们 stream 的用法是一样的。 h 一，比如说我们 f 一是二，对吧？ 没有问题。然后如果 y 六这个 y 六的自助串，他的内容他是自助串啊，但他内容如果是数值的话，我们还是可以用这种。英克瑞掰，然后给他一个数值，他增长一个，然后前面加个 s 啊。 h 英克瑞掰， 然后也可以加个小数啊 by floud 然后我们补讲一下，就是我们的字符串，其实他也是可以加小数的啊，就这样 incred by 可以是整数或者 incred by floud 是小数啊，这个我们来表演一下吧。 呃，这个哈西的跟那个用法一样，只是前面多了一个 h， 我们来吧。嗯， h 二，我们先 c 退一下 h sit h 二 f 一，然后它是，比如说它是一二三，然后呢？我们 h in gray by in gray bye 啊 lot。 好，我们的 h 二 f 一，然后我们要增长多少呢？比如说我们增长一点一一。可以看到啊，小数 啊，整数是一样的，我们不演示了。然后便利的话，我们讲完各种几种常见的这个数据类型以后再统一的说便利啊，因为他们便利都是高度相似的。呃，就没了，你明白了吗？ fun channel。
58良构小方
02:18查看AI文稿AI文稿为什么 hashmap 计算下标的哈西扰动函数能降低 cash 碰撞？ hello， 大家好，我是架构师奶爸。因为 key cash code 函数调用的是 t 建值类型自带的哈西函数返回 in 型散列值， in 值范围每负两千一百四十七万四千八百三十六，四十八至二十一万四千七百四十八三六四七， 加起来大概四十亿的映射空间。只要哈西函数映射的比较均匀松散，一般应用是很难出现碰撞的。但问题是，一个四十亿长度的数组，内存是放不下的。 假如 hashmap 数组的初始大小才十六，就需要用之前需要对数组的长度取模运算得到的余数才能用来访问数组下标源码。中模运算就是把散列值和数组长度 减一，再做一个，与操作位运算比，取于运算要快。模运算圆码如上图所示。这也正好解释了为什么 hashmap 的数组长度要取二的整数密。因为这样数组长度减一正好相当于一个低位演码 与操作的结果就是散裂值的高位全部归零，只保留低位值用来作数组下标访问。以初始程度十六为例， 十六减一等于十五二，禁制表示，如上图所示和某个散裂值作与操作如上图所示， 结果就是截取了最低的四倍值，这样是要快捷一些。但是新的问题来了，就算散裂值分布再松散，要是只取最后几倍的话，碰撞也会很严重。如果散裂本身做的不好，分布上呈等差数列的漏洞，如果正好 让最后几个地位呈现规律性重复，那就更难搞了。这时候扰动函数的价值就体现出来了。看一下扰动函数的示意图，如上所示，又移十六位，正好是三十二比特的一半。自己的高半区和低半区作异惑，就是为了混合原始哈西马的高位和低位， 以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相利用起来了。想了解更多 java 架构师岗位知识，请关注我架构师奶爸，点赞、转发、收藏，共同筑基 java 架构师！
37架构师奶爸
