Hash

概述蚂蚁的转化归因在初期运行两个多小时的状况下，进行了一系列优化，其中建设hash cluster表及强制hash关联及Shuffle的手动干涉进行remove操作此局部优化占了较大比重。本文则次要讲述hash cluster表的一些使用。Hash cluster表具备两个作用：· 存储预排序的重排压缩。Hash cluster表采纳分桶排序操作，若雷同的值反复度高，则能够达到更好的压缩成果。· 上游工作的Shuffle Remove。Hash cluster表因为采纳对指定字段分桶操作，上游若一些关联、聚合操作与分桶键策略雷同，则会进行Shuffle Remove操作。MaxCompute操作中，Shuffle是低廉的，因而有必要在优化阶段尽可能移除不必要的Shuffle。什么状况下能够移除Shuffle？简略来说就是数据自身曾经具备某些数据分布个性，刚好这个数据分布个性满足了上游算子对这份数据的散布要求，就不须要再做Shuffle，这个也是Hash cluster表的重要利用场景。 残缺内容请点击下方链接查看： https://developer.aliyun.com/article/1209042%20?utm_content=g... 版权申明：本文内容由阿里云实名注册用户自发奉献，版权归原作者所有，阿里云开发者社区不领有其著作权，亦不承当相应法律责任。具体规定请查看《阿里云开发者社区用户服务协定》和《阿里云开发者社区知识产权爱护指引》。如果您发现本社区中有涉嫌剽窃的内容，填写侵权投诉表单进行举报，一经查实，本社区将立即删除涉嫌侵权内容。

作者：京东科技 董健 导读缓存Redis，是咱们最罕用的服务，其实用场景宽泛，被大量利用到各业务场景中。也正因如此，缓存成为了重要的硬件老本起源，咱们有必要从空间上做一些优化，降低成本的同时也会进步性能。 上面以咱们的案例阐明，将缓存空间缩小70%的做法。 场景设定1、咱们须要将POJO存储到缓存中，该类定义如下 public class TestPOJO implements Serializable { private String testStatus; private String userPin; private String investor; private Date testQueryTime; private Date createTime; private String bizInfo; private Date otherTime; private BigDecimal userAmount; private BigDecimal userRate; private BigDecimal applyAmount; private String type; private String checkTime; private String preTestStatus; public Object[] toValueArray(){ Object[] array = {testStatus, userPin, investor, testQueryTime, createTime, bizInfo, otherTime, userAmount, userRate, applyAmount, type, checkTime, preTestStatus}; return array; } public CreditRecord fromValueArray(Object[] valueArray){ //具体的数据类型会失落，须要做解决 }}2、用上面的实例作为测试数据 ...

本文作者：钟荣荣 Presto TSC member/Commiter将Alluxio与Presto联合运行在社区中越来越风行，应用固态硬盘或内存来缓存热数据集，可能实现近Presto worker的数据本地行，从而防止了近程读取数据导致的高提早。Presto反对基于哈希的软亲和调度（soft affinity scheduling），这样整个集群中雷同数据只缓存一、两个正本，更多的热数据能被缓存到本地，进步缓存效率。现有哈希算法在集群规模发生变化时成果并不现实。针对这一问题，本文介绍了一种可用于软亲和调度的新哈希算法——一致性哈希（consistent hashing）。 软亲和调度Presto应用一种叫做软亲和调度（soft affinity scheduling）的调度策略，将一个分片（split, 最小的数据处理单位）调度到同一个Presto worker（首选节点）上。分片和Presto worker之间的映射关系是由分片上的哈希函数计算出来的，确保同一个分片总是被散列到同一个worker上。 在第一次解决分片时，数据将被缓存在首选worker节点上。当后续的查询处理同一分片时，这些申请将再次被调度到同一个worker节点上。此时，因为数据曾经缓存在本地，不须要再近程读取数据。 为了进步负载平衡，更好地解决worker节点响应不稳固的问题，会抉择两个首选节点。如果第一个节点忙碌或没有响应，则会应用第二个节点。数据可能会被物理缓存到两个worker节点上。 对于软亲和调度的更多信息，请查看“通过 Alluxio 数据缓存升高Presto提早”（https://prestodb.io/blog/2020...） 哈希算法软亲和调度依附哈希算法来计算分片和worker节点之间的映射关系。原先应用的是取模函数： 该哈希策略很简略，而且在集群稳固、worker节点没有变动的状况下成果很好。然而，如果某个worker节点临时不可用或者掉线，worker节点的数量可能会发生变化，分片到worker节点的映射将全副须要重新分配，导致缓存命中率大幅降落。如果呈现问题的worker稍后从新上线，则须要再次重新分配。 针对这个问题，Presto在通过取模计算出哪个worker调配给特定分片时，会对worker总数取模，而不是正在运行的worker数量。然而，这只能缓解worker节点长期掉线造成的重新分配问题。有时候因为工作负载的稳定，减少/删除worker是正当操作。在这些状况下，是否可能放弃正当的缓存命中率而无需进行大规模的重新分配？ 咱们的解决方案是一致性哈希算法。 一致性哈希一致性哈希由David Karger在1997年第一次提出，是一种将网络拜访申请散发到一组数量时常发生变化的网络服务器的调配算法。该技术被宽泛用于负载平衡、分布式哈希表等。 一致性哈希的工作原理比方，将哈希输入范畴[0, MAX_VALUE]映射到一个圆环上（将MAX_VALUE连贯到0）。为了阐明一致性哈希的工作原理，咱们假如一个Presto集群由3个Presto worker节点组成，其中有10个分片被重复查问。 首先，worker节点被散列到哈希环上。每个分片都被调配给哈希环上与该分片的哈希值相邻的worker（注：这里“相邻”定义为从分片哈希值所在位置，按顺时针方向找到的第一个worker节点）。 上述情况下，分片的调配如下： 删除一个worker当初，如果worker2因为某种原因下线，那么依据算法，分片0、5和7将被调度到对应下一个哈希值的worker，也就是worker1上。 只有被调配到到已下线worker（在这里是worker2）的分片须要从新确定调配到哪个worker。其余数据不受影响。如果 worker32 稍后上线，分片 0、5 和 7 将会被重新分配到 worker2，不会影响其余worker的命中率。 减少一个worker如果工作负载减少，须要在集群中减少另一个worker节点——worker4, worker4的哈希值在哈希环上的地位状况如下图所示： 在这种状况下，分片8将落入worker4的区间，所有其余分片的调配不受影响，因而这些分片的缓存命中率不会受到影响。重新分配的后果如下： 虚构节点从下面能够看出，一致性哈希能够保障在节点变动的状况下，均匀只有 的分片须要被重新分配。然而，因为worker散布不足随机性，分片可能不会平均地散布在所有worker节点上。针对这一问题，咱们引入了“虚构节点 ”的概念。虚构节点可能在某个节点断开连接时将它的负载重新分配给多个节点，从而缩小因集群不稳固而造成的负载稳定。 将每个物理worker节点映射成多个虚构节点。这样虚构节点便代替原先的物理节点，位于哈希环上。随后，每个分片将首先被调配到相邻（顺时针方向最邻近）的虚构节点，再路由到虚构节点映射的物理节点。下图的示例是一种可能呈现的状况，即每个物理worker节点都对应3个虚构节点。 随着哈希环上节点数量的减少，哈希空间将被宰割地更平均。 在一个物理节点宕机的状况下，与该物理节点绝对应的所有虚构节点都将被从新散列。这里不是所有的分片都被重新分配到同一个节点上，而是会调配到多个虚构节点，从而映射到多个物理节点上，以达到更好的负载平衡。 如下图所示，当删除worker3时，分片2和3将被从新散列到worker2，而分片8被从新散列到worker1。 如何在Presto中应用一致性哈希？这是咱们最近奉献给Presto的一个试验性功能。如果有动向进行测试或单干，请分割咱们。 应用该性能前，请先依据指南（https://prestodb.io/docs/curr...）或教程（https://docs.alluxio.io/os/us...）启用Presto的缓存。确保你抉择SOFT_AFFINITY作为调度策略的配置项。在/catalog/hive.properties文件中，增加hive.node-selection-strategy=SOFT_AFFINITY。 须要通过在config.properties中增加node-scheduler.node-selection-hash-strategy=CONSISTENT_HASHING来启用一致性哈希。 论断如上所述，当减少或删除节点时，一致性哈希能够使工作负载重新分配所产生的的影响降到最低。当集群的worker节点发生变化时，基于一致性哈希算法进行工作负载在worker节点间的调配，能够尽量升高对现有节点上缓存命中率的影响。因而，在Presto集群规模依照工作负载的须要扩缩容的场景下，或者部署环境中的硬件设施不齐全受控而导致worker节点可能随时被重新分配和调整的场景下，一致性哈希策略都会成为一种更好的抉择。 在Alluxio社区，咱们始终在不断改进Alluxio和各类计算引擎（例如文中的Presto）在功能性和可用性方面的集成。随着在Presto调度中引入一致性哈希，Alluxio能够利用Presto的软亲和个性，实现更好的数据本地性和缓存效率，最终进步解决性能并降低成本。咱们将继续致对整个数据生态圈进行奉献，不断改进和优化咱们的产品。

1. 题目形容给你两个有序(递增)整数数组 nums1 和 nums2 ，请你以数组模式返回两数组的交加，M为较长数组长度，N为较短数组长度。例如：给定：nums1 = [1,2,3,4,5,6], nums2 = [1,2,3]输入:[1,2,3]这道题常见且并不难，有意思的是解法十分多，在nums1 和 nums2长短不同场景下，筛选最高效的解法2. 哈希表这是最容易想到的解法，对较短的数组进行哈希，遍历较长的数组，就能够失去交加 function intersect(nums1, nums2){ let hash = new Set()//这里用set来代表哈希，他们实质是一样的 for (let i = 0; i < nums2.length; i++) { hash.add(nums2[i]) } for (let i = 0; i < nums1.length; i++) { if (hash.has(nums1[i])) { ans.push(nums1[i]) } } return ans}工夫复杂度：O(M+N)<br/>空间复杂度:对于较短的数组进行了哈希，O(N) 3. 二分查找思考一个场景,较长的数组十分长，哈希表的解法是线性的，显然没有很好的利用数组有序这个条件，这时二分查找怀才不遇，因为两者长度相差越大，二分效率越高； function intersect(nums1, nums2){ //因为是递增，定义一个left,略微缩小下查找范畴 let left = 0; for (let i = 0; i < nums2.length; i++) { //二分查找 let index = binarySearch(nums1, nums2[i], left) if (index != -1) { ans.push(nums2[i]) left = index + 1 } } return ans}function binarySearch(nums, target, left = 0, right = nums.length - 1){ //非凡解决 端点的状况 能够减速间断数组的查找 if(nums[left] == target){ return left } if(nums[right] == target){ return right } while(left <= right){ mid = Math.floor((left + right)/2) if (nums[mid] == target) { return mid }else if(nums[mid] > target){ right = mid - 1 }else{ left = mid + 1 } } return -1}这里重点提一下为什么要优化二分查找的左终点，如果咱们不给定左终点，那么每次二分都是从0 到 len -1二分，而因为数组是有序的，如果曾经在num1中找到了target,那么下一个待查找target的地位必然在上一个target的左边，这样就防止了二分查找每次从0开始,最现实状况下比方nums1 = [1,2,3,4,5,6], nums2 = [4,5,6],第一次查找到4,残余的5,6显然在4的左边，理论只有O(N)次就能够了工夫复杂度：M为较长数组长度，N为较短数组长度，最差/均匀复杂度O(N*logM)，而且因为咱们优化了二分查找的左终点，最最现实状况下复杂度能够达到O(N)；不是现实状况下，工夫复杂度取决于交加在nums1中的散布状况，交加在nums1中越靠右散布，查找效率越高<br/>空间复杂度:如果递归数组是援用的话，咱们只应用了常量级变量空间 O(1)4. 双指针如果两个数组长度相差不大，那么双指针显然效率更高； ...

一、什么是hash　Hash，个别翻译做“散列”，也有间接音译为“哈希”的，就是把任意长度的输出（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输入，该输入就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输出的空间，不同的输出可能会散列成雷同的输入，而不可能从散列值来惟一的确定输出值。简略的说就是一种将任意长度的消息压缩到某一固定长度的音讯摘要的函数。哈希表是依据设定的哈希函数H（key）和解决抵触办法将一组关键字映射到一个无限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储地位，这种表称为哈希表或散列，所得存储地位称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比拟快的一种。简略解释：哈希（Hash）算法，即散列函数。它是一种单向明码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数能够将任意长度的输出通过变动当前失去固定长度的输入。哈希函数的这种单向特色和输入数据长度固定的特色使得它能够生成音讯或者数据。二、罕用hash算法的介绍：MD4　MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年设计的，MD 是 Message Digest（音讯摘要） 的缩写。它实用在32位字长的处理器上用高速软件实现——它是基于 32位操作数的位操作来实现的。 MD5　MD5（RFC 1321）是 Rivest 于1991年对MD4的改良版本。它对输出仍以512位分组，其输入是4个32位字的级联，与 MD4 雷同。MD5比MD4来得简单，并且速度较之要慢一点，但更平安，在抗剖析和抗差分方面体现更好。 SHA-1及其他　SHA1是由NIST NSA设计为同DSA一起应用的，它对长度小于264的输出，产生长度为160bit的散列值，因而抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4雷同原理，并且模拟了该算法。 三、哈希碰撞（hash抵触）及解决在计算hash地址的过程中会呈现对于不同的关键字呈现雷同的哈希地址的状况，即key1 ≠ key2，然而f(key1) = f(key2)，这种状况就是Hash 抵触。具备雷同关键字的key1和key2称之为同义词。通过优化哈希函数能够缩小这种抵触的状况（如：平衡哈希函数），然而在通用条件下，思考到于表格的长度无限及要害值（数据）的有限，这种抵触是不可避免的，所以就须要解决抵触。 抵触解决抵触解决分为以下四种形式： 凋谢地址再哈希链地址建设公共溢出区其中凋谢地址又分为： 线性探测再散列二次探测再散列伪随机探测再散列1.凋谢地址凋谢地址法解决抵触的根本准则就是呈现抵触后依照肯定算法查找一个空地位寄存。公式： Hi为计算出的地址，H(key)为哈希函数，di为增量。其中di的三种获取形式既是下面提到的凋谢地址法的三种分类（线性探测再散列、二次探测再散列、伪随机探测再散列）。 线性探测再散列，即顺次向后查找二次探测再散列，即顺次向前后查找，增量为1、2、3的二次方。伪随机探测再散列伪随机，顾名思义就是随机产生一个增量位移。2.再哈希法再哈希法，就是呈现抵触后采纳其余的哈希函数计算，直到不再抵触为止。，其中RHi为不同的哈希函数。 3.链地址法链接地址法不同与前两种办法，他是在呈现抵触的中央存储一个链表，所有的同义词记录都存在其中。形象点说就行像是在呈现抵触的中央间接把后续的值摞下来。例如HashMap，如下图。 4.建设公共溢出区建设公共溢出区的根本思维是：假如哈希函数的值域是[1,m-1]，则设向量HashTable[0...m-1]为根本表，每个重量寄存一个记录，另外设向量OverTable[0...v]为溢出表，所有关键字和根本表中关键字为同义词的记录，不论它们由哈希函数失去的哈希地址是什么，一旦发生冲突，都填入溢出表。

zcash在sprout版本中，计算MerkleTreeRoot时，应用Sha256计算hash。因为Sha256须要依赖的位运算，在ZK电路中是实现计算复杂度和老本高，因而在sapling版本中采纳 Pedersen Hash Function来计算hash。 Pedersen Hash Function来源于Pedersen Commitment。安全性依赖于离散对数问题。Pedersen Hash Function不是齐全伪随机，所以不能和Sha256一样，作为一个随机数源。 Pedersen Hash Function的计算规定与相关性。1.Pedersen Hash2.Mixing Pedersen Hash3.Windowed Pedersen Commitment4.Homomorphic Pedersen Commitment Pedersen Hash Function与zcash的sapling协定在中的利用(待补充）

哈希碰撞是什么？所谓哈希（hash），就是将不同的输出映射成举世无双的、固定长度的值（又称"哈希值"）。它是最常见的软件运算之一。 如果不同的输出失去了同一个哈希值，就产生了"哈希碰撞"（collision）。 举例来说，很多网络服务会应用哈希函数，产生一个 token，标识用户的身份和权限。 AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8下面这个字符串就是一个哈希值。如果两个不同的用户，失去了同样的 token，就产生了哈希碰撞。服务器将把这两个用户视为同一个人，这意味着，用户 B 能够读取和更改用户 A 的信息，这无疑带来了很大的安全隐患。 黑客攻击的一种办法，就是设法制作"哈希碰撞"，而后入侵零碎，窃取信息。 如何避免哈希碰撞？避免哈希碰撞的最无效办法，就是扩充哈希值的取值空间。 16个二进制位的哈希值，产生碰撞的可能性是 65536 分之一。也就是说，如果有65537个用户，就肯定会产生碰撞。哈希值的长度扩充到32个二进制位，碰撞的可能性就会降落到 4,294,967,296 分之一。 更长的哈希值意味着更大的存储空间、更多的计算，将影响性能和老本。开发者必须做出抉择，在平安与老本之间找到均衡。 上面就介绍，如何在满足平安要求的前提下，找出哈希值的最短长度。 生日攻打哈希碰撞的概率取决于两个因素（假如哈希函数是牢靠的，每个值的生成概率都雷同）。 取值空间的大小（即哈希值的长度）整个生命周期中，哈希值的计算次数这个问题在数学上早有原型，叫做"生日问题"（birthday problem）：一个班级须要有多少人，能力保障每个同学的生日都不一样？ 答案很出乎意料。如果至多两个同学生日雷同的概率不超过5%，那么这个班只能有7集体。事实上，一个23人的班级有50%的概率，至多两个同学生日雷同；50人班级有97%的概率，70人的班级则是99.9%的概率（计算方法见后文）。 这意味着，如果哈希值的取值空间是365，只有计算23个哈希值，就有50%的可能产生碰撞。也就是说，哈希碰撞的可能性，远比设想的高。实际上，有一个近似的公式。 下面公式能够算出，50% 的哈希碰撞概率所须要的计算次数，N 示意哈希的取值空间。生日问题的 N 就是365，算进去是 23.9。这个公式通知咱们，哈希碰撞所需消耗的计算次数，跟取值空间的平方根是一个数量级。 这种利用哈希空间不足够大，而制作碰撞的攻打办法，就被称为生日攻打（birthday attack）。 数学推导这一节给出生日攻打的数学推导。 至多两个人生日雷同的概率，能够先算出所有人生日互不雷同的概率，再用 1 减去这个概率。 咱们把这个问题构想成，每个人排队顺次进入一个房间。第一个进入房间的人，与房间里已有的人（0人），生日都不雷同的概率是365/365；第二个进入房间的人，生日举世无双的概率是364/365；第三个人是363/365，以此类推。 因而，所有人的生日都不雷同的概率，就是上面的公式。 下面公式的 n 示意进入房间的人数。能够看出，进入房间的人越多，生日互不雷同的概率就越小。 这个公式能够推导成上面的模式。 那么，至多有两个人生日雷同的概率，就是 1 减去下面的公式。 哈希碰撞的公式下面的公式，能够进一步推导成一般性的、便于计算的模式。 依据泰勒公式，指数函数 ex 能够用多项式开展。 如果 x 是一个极小的值，那么下面的公式近似等于上面的模式。 当初把生日问题的1/365代入。 因而，生日问题的概率公式，变成上面这样。 假如 d 为取值空间（生日问题里是 365），就失去了一般化公式。 下面就是哈希碰撞概率的公式。 利用下面的公式写成函数。 const calculate = (d, n) => { const exponent = (-n * (n - 1)) / (2 * d) return 1 - Math.E ** exponent;}calculate(365, 23) // 0.5000017521827107calculate(365, 50) // 0.9651312540863107calculate(365, 70) // 0.9986618113807388一般来说，哈希值由大小写字母和阿拉伯数字形成，一共62个字符（10 + 26 + 26）。如果哈希值只有三个字符的长度（比方abc），取值空间就是 62 ^ 3 = 238,328，那么10000次计算导致的哈希碰撞概率是100%。 ...

01 文件哈希值是什么？文件哈希值，即文件内容的HASH值。是通过对文件内容进行加密运算失去的一组二进制值，主要用途是用于文件校验或签名。正是因为这样的特点，它经常用来判断两个文件是否雷同。 COS 文件上传下载场景下，数据传输过程可能会呈现谬误，哈希值可用于比照确认已上传到 COS 的文件与本地文件的一致性。 02 用户痛点COS 对象只提供 CRC64 校验码：因为对象存储的特殊性，COS 存储的对象，目前只提供 CRC64 校验值。自定义计算哈希值有开发成本：有的开发者须要 MD5、SHA1、SHA256 等校验值，须要自行实现哈希计算过程。03 解决方案COS工作流+云函数，自定义计算 利用数据工作流+云函数新个性，COS 为开发者提供了文件哈希值计算模板。用户可轻松实现自定义计算 COS 文件哈希值函数。 计划劣势： 可视化操作：一键配置，简化开发流程，无需编码工作，大幅晋升研发效率；多样化抉择：反对 MD5 、SHA1 、SHA256、CRC64，满足各场景用户需要；自动化执行：文件上传 COS 后，即刻触发工作流开始计算校验码；04 配置步骤1.到 COS 控制台存储桶详情，创立工作流，能够自定义过滤后缀过滤规定，创立自定义函数节点。 2.在函数节点弹窗里，点击新建函数，浏览器新标签会关上 SCF 的创立云函数的页面。 3.创立云函数 A. 抉择“计算COS对象的哈希值”模板；B. 配置足够的内存、执行超时工夫；C. 该函数模板反对两个环境变量； hashTypeList 指定要计算的算法，可选，默认["crc64","md5", "sha1", "sha256"]caseType 指定哈希值大小写，可选默认 lowercase，能够传入 uppercaseD. 启用权限配置，绑定蕴含以后存储桶读写权限的角色，创立运行角色请看文档；E. 点击实现； 如需新建运行角色，能够抉择“云函数”作为角色载体，配置 QcloudCOSFullAccess权限，或新建角色自行绑定只蕴含所需存储桶度权限的桶写权限。 4.回到方才工作流的页面，选中刚创立的函数。并保留工作流。 5.上传文件，查看工作流解决胜利后，能够看到上传的文件已胜利增加多个哈希头部。 05 结语更多自定义解决能力，等你来实现！如果您有应用 COS 工作流 + Serverless 云函数开发更多乏味性能的想法，请点击浏览全文支付更多福利！对于更多请返回：https://cloud.tencent.com/act...

摘要：依据设定的哈希函数 H(key) 和所选中的解决抵触的办法，将一组关键字映象到一个无限的、地址间断的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储地位，如此结构所得的查找表称之为“哈希表”。本文分享自华为云社区《查找——HASH》，原文作者：ruochen。 对于频繁应用的查找表，心愿 ASL = 0记录在表中地位和其关键字之间存在一种确定的关系 HASH定义依据设定的哈希函数 H(key) 和所选中的解决抵触的办法，将一组关键字映象到一个无限的、地址间断的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储地位，如此结构所得的查找表称之为“哈希表” HASH函数的结构结构准则 函数自身便于计算计算出来的地址散布平均，即对任一关键字k，f(k) 对应不同地址的概率相等，目标是尽可能减少抵触间接定址法哈希函数为关键字的线性函数 H(key) = keyH(key) = a * key + b此法仅适宜于：地址汇合的大小 = = 关键字汇合的大小长处：以关键码key的某个线性函数值为哈希地址，不会产生抵触毛病：要占用间断地址空间，空间效率低数字分析法假如关键字汇合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，剖析关键字集中的整体， 并从中提取散布平均的若干位或它们的组合作为地址此办法仅适宜于：能事后预计出整体关键字的每一位上各种数字呈现的频度平方取中法以关键字的平方值的两头几位作为存储地址。求“关键字的平方值” 的目标是“扩充差异” ，同时平方值的两头各位又能受到整个关键字中各位的影响此办法适宜于:关键字中的每一位都有某些数字反复呈现频度很高的景象折叠法将关键字宰割成若干局部，而后取它们的叠加和为哈希地址。有两种叠加解决的办法：移位叠加和间界叠加此办法适宜于:关键字的数字位数特地多除留余数法Hash(key)=key mod p (p是一个整数)p≤m (表长) p 应为小于等于 m 的最大素数为什么要对 p 加限度？给定一组关键字为: 12, 39, 18, 24, 33, 21若取 p=9, 则他们对应的哈希函数值将为:3, 3, 0, 6, 6, 3 可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而减少了“抵触”的可能 随机数法H(key) = Random(key) （Random 为伪随机函数）此办法用于对长度不等的关键字结构哈希函数思考因素 ...

先上代码 前面有介绍 import cv2import numpy as np#均值哈希算法def aHash(img): # 缩放为8*8 img = cv2.resize(img, (8, 8), interpolation=cv2.INTER_CUBIC) # 转换为灰度图 gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) # s为像素和初值为0，hash_str为hash值初值为'' s = 0 hash_str = '' # 遍历累加求像素和 for i in range(8): for j in range(8): s = s + gray[i, j] # 求均匀灰度 avg = s / 64 # 灰度大于平均值为1相同为0生成图片的hash值 for i in range(8): for j in range(8): if gray[i, j] > avg: hash_str = hash_str + '1' else: hash_str = hash_str + '0' return hash_str#差值感知算法def dHash(img): #缩放8*8 img=cv2.resize(img,(9,8),interpolation=cv2.INTER_CUBIC) #转换灰度图 gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY) hash_str='' #每行前一个像素大于后一个像素为1，相同为0，生成哈希 for i in range(8): for j in range(8): if gray[i,j]>gray[i,j+1]: hash_str=hash_str+'1' else: hash_str=hash_str+'0' return hash_str#Hash值比照def cmpHash(hash1,hash2): n=0 #hash长度不同则返回-1代表传参出错 if len(hash1)!=len(hash2): return -1 #遍历判断 for i in range(len(hash1)): #不相等则n计数+1，n最终为类似度 if hash1[i]!=hash2[i]: n=n+1 return n# 取各个mp4 第2秒的截图 进行比拟# 图1img1=cv2.imread(r'a.jpg')# 图2img2=cv2.imread(r'b.jpg')hash1= aHash(img1)hash2= aHash(img2)print(hash1)print(hash2)n=cmpHash(hash1,hash2)print ('均值哈希算法类似度：'+ str(n))hash1= dHash(img1)hash2= dHash(img2)print(hash1)print(hash2)n=cmpHash(hash1,hash2)print ('差值哈希算法类似度：'+ str(n))#差值越小 代表 越相近均值哈希算法 && 差值哈希算法 区别(另附感知哈希):均值哈希（aHash）：图片缩放，个别为88，或者3232；图片灰度化；求平均值，并依据平均值将每一个像素二值化（大于均值为1小于均值为0）；将8*8=64位bit，每8个比特为一个十六进制值，转换成字符串，生成哈希值（指纹）； ...

HotRing 热点感知KV索引 有序环哈希论文浏览笔记 【FAST'20】HotRing: A Hotspot-Aware In-Memory Key-Value Store https://www.usenix.org/system... huazhong 简介背景、动机热点问题很广泛。如：阿里生产环境中，50%~90%的拜访，只波及1%的数据。内存KV构造的热点问题不被器重，大多数KV构造不能感知热点。目前内存KV构造缩小热点访存的办法有局限：CPU cache太小；rehash（为缩小抵触）不适宜自身微小的表，且性能晋升无限。次要思维设计热点感知的内存KV构造——有序环哈希构造。 次要挑战及应答办法： 热点转移：把抵触链改为环。头节点挪动到热点项；两种策略检测热点转移。高并发拜访：应用无锁构造，实现插删，并扩大到热点特定操作（热点转移检测、头指针挪动、有序环rehash）。奉献反对快速访问热点数据。有轻量的运行时热点转移检测策略。无锁机制，反对高并发拜访，贯通热点特定操作（热点转移检测、头指针挪动、有序化rehash）。实在环境测试，高度不均衡的负载试验，2.58x。有序环把抵触链改为有序环构造。 $order_k = (tag_k, key_k) $。 对抵触环以 tag-key 形式排序。 查找。不命中： 不命中，均匀只须要查找一半的元素（抵触链则须要遍历整条）。 热点转移辨认两种掂量：accurancy、反馈提早。 把头指针挪动到热点项。 随机挪动每隔R个申请，若第R个申请不是拜访热点项（指头指针所指元素），则将头指针指向以后拜访项。不需历史统计数据，挪动到潜在热点项。 实现简略，反应时间较快。 R小，反馈提早可能小，但会造成频繁的指针挪动，低效。试验表明，R = 5 较好。 毛病： 辨认精度低。负载歪斜不显著时，该办法低效。若抵触环有多个热点，无奈应答，频繁的挪动反而影响其余操作统计采样辨认精度更高，反馈提早稍长。能够应答环上多个热点的状况。 索引格局利用头指针、item的残余16bit空间。 active：管制统计采样。 total count：统计采样时环的总拜访次数。 rehash：管制rehash。 occupied：管制并发，保障并发拜访的正确性。 counter：某一项的拜访次数。 address：下一项的地址。 统计采样：每R个申请，若第R个申请不是拜访热点项（指头指针所指元素），则触发采样：active地位1（需CAS原语），之后对该环的拜访都会被计数（total counter 和 counter），采样的次数等于该环item的个数。 热点挑整计算每一项 $t$ 的income：$ W_t = \sum \limits_{i=1}^N \frac{n_i}{N} \cdot [(i-t)mod k ] $. ($n_i$：项$i$ 的计数， $N$：总计数 $k$ ： 环长) ...

作者：傅同学爱可生研发部成员，次要负责中间件产品开发，热衷技术原理。本文起源：原创投稿*爱可生开源社区出品，原创内容未经受权不得随便应用，转载请分割小编并注明起源。前言之前爱可生开源社区公众号发表了《dble 沿用 jumpstringhash，移除 Mycat 一致性 hash 起因解析》。随后又发表了本文上篇，初步解释了 Jump Consistent Hash 的原理。首先让咱们回顾一下： 扩容时，随机抉择要挪动的元素 从现有 n 节点扩容到 n+1 节点时，n 节点上每个元素有 1/(n+1) 的概率挪动到新节点应用稳固的、可重现的随机数序列——以 key 为随机数种子咱们遗留了一个问题，O(n) 的算法复杂度不够现实，如何优化？ 优化复杂度与其在 bucket 逐渐减少的过程中，每次随机地决定是否跳跃到新增的 bucket。咱们尝试随机决定下一次加到第几个 bucket 才跳跃。当然，这个随机选取的指标须要合乎肯定的概率分布。假如上一次 k 的跳跃产生在减少第 b+1 个 bucket 时，即 ch(k,b) != ch(k,b+1) 且 ch(k,b+1) = b+1（本文 bucket 编号从 1 开始）。这一次跳跃，咱们随机抉择了一个地位  j+1，即 ch(k,j+1) != ch(k,j) 且 ch(k,j) = ch(k,b+1)。作为单次抉择，跳跃产生在 b+2（间断跳）或者 INT_MAX（再也不跳了），都是可能的。但总体上，j 的抉择要满足肯定的法则。定义事件：对于任意 i >= b+2，在减少第 b+2、b+3 ... i 个 bucket 时，都没有产生跳跃。该事件当且仅当 j+1 > i，即 j >= i 时成立。该事件的概率能够这么算： 从 b+1 减少到 b+2，不跳跃的概率是 (b+1)/(b+2)始终加到第 i 个 bucket，都不跳跃，其概率为 (b+1)/(b+2)*(b+2)/(b+3)*...*(i-1)/(-) = (b+1)/i即 P(j>=i) = (b+1)/i。该等式对于任意 i 都成立。j 是咱们任选的，可能 j>=i，也可能 j<i。抉择形式待定，但要让概率 P(j>=i)等于(b+1)/i。每次要抉择 j 时，咱们生成一个 [0,1) 上均匀分布的随机数 r，显然，布尔表达式 r <= (b+1)/i 为 true 的概率是 (b+1)/i。咱们先变换一下表达式：r <= (b+1)/i 变换后可得 i <= (b+1)/r。因为 i 是整数，(b+1)/r 向下取整不等式仍然成立，表达式最初变换为 i <= floor((b+1)/r)。当上述表达式为 true 时，咱们就选则大 j (j>=i)；否则，咱们就选则小 j (j<i)。这个抉择形式, 就使 P(j>=i) = (b+1)/i 成立。 ...

明天的知识点 (2020.12.22) —— 第616天 (我也要出题)[html] 说说js代码写到html里还是独自写到js文件里哪个好？为什么？[css] Sass的数字操作是什么？[js] 哈希表的原理是什么？[软技能] 你认为中级前端工程师和高级前端工程师的差别在哪里？《论语》，曾子曰：“吾日三省吾身”（我每天屡次检查本人）。前端面试每日3+1题，以面试题来驱动学习，每天提高一点！让致力成为一种习惯，让奋斗成为一种享受！置信 保持 的力量！！！欢送在 Issues 和敌人们一起探讨学习！ 我的项目地址：前端面试每日3+1【举荐】欢送跟 jsliang 一起折腾前端，零碎整顿前端常识，目前正在折腾 LeetCode，打算买通算法与数据结构的任督二脉。GitHub 地址 微信公众号欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个Star, 同时欢送微信扫码关注 前端剑解 公众号，并退出 “前端学习每日3+1” 微信群互相交换（点击公众号的菜单：交换）。 学习不打烊，充电加油只为遇到更好的本人，365天无节假日，每天早上5点纯手工公布面试题（死磕本人，愉悦大家）。心愿大家在这虚夸的前端圈里，放弃沉着，保持每天花20分钟来学习与思考。在这变幻无穷，类库层出不穷的前端，倡议大家不要等到找工作时，才狂刷题，提倡每日学习！（不忘初心，html、css、javascript才是基石！）欢送大家到Issues交换，激励PR，感激Star，大家有啥好的倡议能够加我微信一起交换探讨！心愿大家每日去学习与思考，这才达到来这里的目标！！！（不要为了谁而来，要为本人而来！）交换探讨欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个[Star]

作者：赵红杰DBLE 我的项目测试负责人，主导分布式中间件的测试，在测试中一直发现产品和本身的 bug。迭代验证，乐在其中。本文起源：原创投稿*爱可生开源社区出品，原创内容未经受权不得随便应用，转载请分割小编并注明起源。背景社区有大佬分享过跳增 hash 的文章，然而过后并不了解跳增 hash 应用的场景。刚接触分布式数据库中间件 dble 的时候，最蛊惑的概念之一是 hash 分片算法。看到哈希，第一印象是散列表，感觉是存储相干的。hash 一个重要的特色是须要不同输出产生不同输入，然而在分片算法里，是须要多个值映射到一个分片节点上。这么大的差别，为什么能够用 hash 来对分布式数据库做逻辑分片，并且还命名叫 hash 分片！！！它们之间有哪些神似呢？ 概念散列表要了解他们之间的类似和差别，先从对 hash 最后的意识——散列表说起。散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输出映射到一个数字，个别用映射出的数字作为存储地位的索引。数组在查找时效率很高，然而插入和删除却很低。而链表刚好反过来。设计正当的散列函数能够集成链表和数组的长处，在查找、插入、删除时实现 O(1) 的效率。散列表的存储构造应用的也是数组加链表。执行效率比照能够看下图 1.3： 散列表的次要特点：1. 将输出映射到数字2. 不同的输出产生不同的输入3. 雷同的输出产生雷同的输入 当填装因子超过阈值时，能主动扩大。填装因子 = 散列表蕴含的元素数 / 地位总数，当填装因子 =1，即散列表满的时候，就须要调整散列表的长度，主动扩大的形式是：申请一块旧存储容量 X 扩容系数的新内存地址，而后把原内存地址的值通过其中的 key 再次应用 hash 函数计算存储地位，拷贝到新申请的地址。 值呈均匀分布。这里的平均指程度方向的，即数组维度的。如果多个值被映射到同一个地位，就产生了抵触，须要用链表来存储多个抵触的键值。极其状况是极限抵触，这与一开始就将所有元素存储到一个链表中一样。这时候查找性能将变为最差的 O(n)，如果程度方向填充因子很小，但某些节点下的链表又很长，那值的平均性就比拟差。 hash 分片了解了散列表的根本特点，再来看看分布式数据库的 hash 分片。hash 分片设计的要点：1. 固定的数据映射到固定的节点 / 槽位2. 数据分布平均3. 扩容不便次要是扩容时尽可能挪动较少的数据。扩容之后实现新的数据分布平均。想要实现动静扩容，尽可能不影响业务并保障效率，须要做到挪动尽可能少的数据，一致性 hash 就是为了解决挪动较少数据的问题，然而一致性 hash 的毛病是数据分布的平均性较差。为了解决这个问题，聪慧的 dev 们又设计了跳增一致性 hash 算法。到这里，能够看出 hash 与分片最严密或者说最神似的点在于：1. 固定的输出有固定的输入2. 值呈均匀分布如果分布式数据库的分片数据分布不平均，最糟状况就像散列表的极其抵触一样，落在最终数据库上的压力跟不应用分布式雷同。3. 不便扩容当分片填充斥的时候，须要扩容使总数据量在总分片之间再次达到数据均匀分布状态，扩容须要用 hash 函数从新映射旧值到新的分片。 散列表和 hash 分片想要有好的体现都依赖于设计良好的 hash 函数。正是因为这些类似特点，Hash 在分布式数据库里失去比拟多的应用。回到测试的老本行，这些点便是咱们测试思考的重点。理解了分布式与 hash 的关联，再来八几句 hash 函数，能够说hash函数设计的好坏，间接决定了分片策略是否适合。一致性 hash 和跳增 hash，大家参考社区相干文章：https://opensource.actionsky....hash 取模分片还有一种比较简单的 hash 函数是取模 hash。目前的分布式数据库根本都提供了这种分片反对。次要业务场景是：分片键的值存在枯燥递增或递加、分片键的值不确定，基数大且反复的频率低、须要写入的数据随机散发、数据读取随机性较大。取模 hash，举个最简略的例子就能明确：分片数设置为 2，要把数据均匀分布在这 2 个分片上，间接对分片 key 取模 2，这样模值为 0 的数据落在分片 1，模值为 2 的数据落在分片 2。只有输出的数据奇偶平均，分片数据就保障平衡。取模 hash 在 dble 里还做了一些变种反对，比方能够指定每个分片的间断值的数量，比方自然数 0-99 放分片 1，自然数 100-599 放分片 2，具体配置形式参考官网文档。这样做次要目标是改善 hash 在范畴查问时的效率问题。Hash 取模分片非常简单，均衡性比拟好，能扩散数据热点，并且能疾速人为辨认数据所在分片。毛病也很显著。1\. 在业务上范畴查问效率比拟低2\. 扩容不便因为取模 hash 强依赖于分片数，当新增或删减分片节点——即扩缩容时，大量的数据在从新映射后都须要移动。比方下面的 2 分片数据，如果减少到 3 分片，原来分片 1 上的数据只有 1/3 的数据能够保留不动，另外 2/3 的数据都须要挪到新的分片上，分片 2 也是如此。如果真的应用了 hash 取模分片，为了前期在扩容时挪动尽可能少的数据，dble 的倡议是：取模的基数不能大于 2880，起因是：2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 45, 48, 60, 64, 72, 80, 90, 96, 120, 144, 160, 180, 192, 240, 288, 320, 360, 480, 576, 720, 960, 1440 是 2880 的约数。 ...

multiHash是将哈希算法和哈希长度以哈希放在一起，应用base64进行编码的一种哈希。其格局如下：详情可参见：https://multiformats.io/multi... <hash-func-type><digest-length><digest-value>hash-func-type:哈希函数类型 sha1:0x11 ,sha2-256:0x12digest-length:是哈希长度digest-value:是真正的哈希值例如： sha1:0x11length:0x14 (0x14-> 20 -> 20*8=160sha1("multihash"):88c2f11fb2ce392acb5b2986e640211c4690073emultiHash:0x111488c2f11fb2ce392acb5b2986e640211c4690073ebase32:CEKIRQXRD6ZM4OJKZNNSTBXGIAQRYRUQA47A====base58:5dsgvJGnvAfiR3K6HCBc4hcokSfmjjbase64:ERSIwvEfss45KstbKYbmQCEcRpAHPg==sha-256:0x12length:0x20(0x20 -> 32 -> 32*8=256)sha256("multihash"):0x12209cbc07c3f991725836a3aa2a581ca2029198aa420b9d99bc0e131d9f3e2cbe47multiHash: 0x122012209cbc07c3f991725836a3aa2a581ca2029198aa420b9d99bc0e131d9f3e2cbe47base32:CIQJZPAHYP4ZC4SYG2R2UKSYDSRAFEMYVJBAXHMZXQHBGHM7HYWL4RY=base58:QmYtUc4iTCbbfVSDNKvtQqrfyezPPnFvE33wFmutw9PBBkbase64:EiCcvAfD+ZFyWDajqipYHKICkZiqQgudmbwOEx2fPiy+Rw==