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==

了解SPA现代前端项目多为单页Web应用(SPA)，在单页Web应用中路由是其中的重要环节。SPA 是 single page web application 的简称，译为单页Web应用。 简单的说 SPA 就是一个WEB项目只有一个 HTML 页面，一旦页面加载完成，SPA 不会因为用户的操作而进行页面的重新加载或跳转。 取而代之的是利用 JS 动态的变换 HTML 的内容，从而来模拟多个视图间跳转。 前度路由简单的说，就是在保证只有一个 HTML 页面，且与用户交互时不刷新和跳转页面的同时，为 SPA 中的每个视图展示形式匹配一个特殊的 url。在刷新、前进、后退和SEO时均通过这个特殊的 url 来实现。我们需要实现下满两点： 改变 url 且不让浏览器像服务器发送请求。可以监听到 url 的变化可以在不刷新页面的前提下动态改变浏览器地址栏中的URL地址hash 模式和 history 模式，就是用来实现上面功能的 Hash模式在url后面加上#，如http://127.0.0.1:5500/前端路由/hash.html#/page1这个url后面的#/page1就是hash值 hash 值的变化不会导致浏览器像服务器发送请求location.hash可以获取hash值hashchange是hash值发生改变的调用的函数基于以上三点我们可以写一个路由实例 <!DOCTYPE html><html lang="en"> <head> <meta charset="UTF-8" /> <meta name="viewport" content="width=device-width, initial-scale=1.0" /> <meta http-equiv="X-UA-Compatible" content="ie=edge" /> <title>Document</title> </head> <body> <ul> <li><a href="#/">/</a></li> <li><a href="#/page1">page1</a></li> <li><a href="#/page2">page2</a></li> </ul> <div class="content-div"></div> </body> <script> class RouterClass { constructor() { this.routes = {}; // 记录路径标识符对应的cb this.currentUrl = ""; // 记录hash只为方便执行cb window.addEventListener("load", () => this.render()); window.addEventListener("hashchange", () => this.render()); } /* 初始化 */ static init() { window.Router = new RouterClass(); } /* 注册路由和回调 */ route(path, cb) { this.routes[path] = cb || function() {}; } /* 记录当前hash，执行cb */ render() { this.currentUrl = window.location.hash.slice(1) || "/"; this.routes[this.currentUrl](); } } RouterClass.init(); const ContentDom = document.querySelector(".content-div"); const changeContent = content => (ContentDom.innerHTML = content); Router.route("/", () => changeContent("默认页面")); Router.route("/page1", () => changeContent("page1页面")); Router.route("/page2", () => changeContent("page2页面")); </script></html>History模式History 接口允许操作浏览器的曾经在标签页或者框架里访问的会话历史记录。可以参考下两篇文章对history的说明https://css-tricks.com/using-the-html5-history-api/https://developer.mozilla.org/zh-CN/docs/Web/API/History下面介绍在这个模式下需要用到的api ...

区块链中经常会听到挖矿这个名词，因为它和现实中的挖矿不一样，所以很多人对这个词很费解。为什么那么多人去挖矿呢？因为挖矿成功后会有奖励。为什么挖矿需要大量的矿机呢？因为有大量的哈希计算。这个计算的过程就被称为挖矿。 哈希函数要想明白什么是挖矿，就必须要先了解计算机中的一类函数——哈希函数。比如md5、sha256等都是哈希函数的一种实现方式，它们最终都是将任意长度的数据都转换为固定长度的数据。就如同你去办身份证一样，不管你高矮胖瘦、贫富贵贱，给你的身份证id都是一个18为的数字，这个过程就如同进行了一次哈希。 我们来简单感受一下sha256哈希函数： 1. 输入长度可变，输出长度固定不论输入的是多长，都能得到一个定长的字符串hash("a")ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bbhash("hongtao")7530e08344cf1ec5157f34e2447182d7ec7040a36fba24fc7006499513d96c26 2. 对数据敏感只要数据有一点变化，那么就能得到一个完全不一样的字符串hash("hongtao") 7530e08344cf1ec5157f34e2447182d7ec7040a36fba24fc7006499513d96c26hash("hongtaofu") 1059ac7a8f6d4eb9024231eb260bfcc30d23fdf1b461164741f71835c49689063. 单向性给定一个字符串，比如“hongtao”，我们可以马上计算出他的哈希是： “7530e08344cf1ec5157f34e2447182d7ec7040a36fba24fc7006499513d96c26”。但是给你一个哈希： “3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d”，要想计算出他的一个原像，这比登天还难 4. 不可被碰撞比如给定一个字符串“a”，他的哈希是： “ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb”。你不可能通过计算或者暴力破解去找到另外一个字符串，使得他的哈希也是： “ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb”5.从概率的角度来分析一下哈希函数：sha256函数：实际上输出的值就是256个bit（比特），如果我们想随机去碰撞一个哈希值，那么他的概率是多少呢？每一个bit可以是0或者1，256位要求全部相同，那么概率就是$\frac{1}{2^{256}}$ ≈ 1.157 X $\frac{1}{10^{77}}$。而宇宙的总原子量是$10^{79}$个，总质量$10^{56}$g。大型计算机的速度在$10^{20}$Hz/s，个人计算机计算哈希的速度在$10^{10}$Hz/s。所以如果要想去碰撞哈希，这完全是不可能的。 挖矿先上一副全网络挖矿统计图： 当前全网算力是95.21EH/s，1EH/s = 百亿亿次哈希/秒。而比特币的所有矿工大概需要计算十分钟，才会有一个矿工碰巧找到满足要求的哈希 一个哈希的部分碰撞比如有一个数据和一个随机数(nonce)，我们对它们作哈希，希望得到的哈希前面有6个0 Hash("hongtao"+nonce)=000000xxxx..50...xxxx(十六进制，共64位);这个时候我们修改nonce，哈希也会发生变化，需要经过 16 x 16 x 16 x 16 x 16 x 16 = 16,777,216次哈希计算，才能得到想要的哈希。 hash("hongtao623022891")0000000bd07143fcbb02e54dc5b68f0e391f80a44d72f9ebe53ae7cc31434056 笔者的电脑是2.9GHz x 6核，大概用了1分钟才计算完，这个时候任何人想要修改前面的数据，比如把hongtao修改为taohong，修改过后都需要进行一分钟的计算才能找到合法的随机数 如果前面要求不是6个0，而是16个0，就需要计算$16^{10}$ x 1分钟。笔者的电脑需要计算2091917年才能计算出来。 现在我们就可以利用一个哈希的部分碰撞去保证数据的很难修改了，最终达到个人、组织或国家无法修改的难度。当区块被链接起来过后，历史数据将达到所有国家都无法修改的难度 什么是挖矿我们先看看比特比区块的数据： 难度：这个难度前面讲过，是根据以往的2016可区块计算出来的，表示这个区块头的哈希需要满足前面有多少个0。随机数nonce：这个就是矿工不停修的数字，然后去得到满足相应要求的哈希，如果算出来了，就代表成功挖到这个区块的矿了。将获得这个区块的奖励我们来看一个区块头的信息： 可以看到，当前区块的哈希和上一个区块的哈希，前面都是0。0越多代表挖矿难度越大，0越少代表挖矿难度越小。现在要求的挖矿难度是17个0。我们前面计算了需要16个0的话需要挖2091917年，所以现在的比特币，想要用个人电脑去挖矿，简直是比中彩票、比陨石撞击地球还难。 注：这里为了方便大家的理解，直接将难度说成了前面需要多少个0，实际上对难度的定义是通过其他表达式来表示的 最后所以挖矿需要大量的矿机，这些矿机实际上就是计算机，只是这些计算机对哈希的计算能力进行了增强。比如将哈希算法固定到硬件上面，以此来获得高速的哈希计算能力。还有的机器通过显卡挖矿，这是因为显卡也具有一定的计算能力，这样可以充分利用计算机的资源。由于计算机的速度满足摩尔定律，每过18个月，速度就会翻倍。而计算机内存的速度增长却很缓慢，大概每年7%，所以有的虚拟币挖矿需要求结合内存，这样大家的挖矿就相对于平等一些。挖矿是一个很消耗资源的，尤其是电力，所以矿机一般都选择电费便宜的地方。

简介MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。 家族成员MurmurHash1, MurmurHash2, MurmurHash3计算 mmh3 十六进制字符串Python3>>> import binascii>>> import mmh3>>> binascii.b2a_hex(mmh3.hash_bytes('CN305183362S')).decode('utf8')'a4fb17cba6d455e4812ad28989780cbc' # 32个字符，128 bitJavaimport java.math.BigInteger;import org.apache.commons.lang.ArrayUtils;public class AppTester { public static void main(String[] args) { final byte[] origin = "CN305183362S".getBytes(); long[] vec = org.apache.commons.codec.digest.MurmurHash3.hash128(origin, 0, origin.length, 0); // 将 long 转换为 BigInteger BigInteger bigInteger0 = BigInteger.valueOf(vec[0]); BigInteger bigInteger1 = BigInteger.valueOf(vec[1]); // 将 BigInteger 转换为 byte[] byte[] array0 = bigInteger0.toByteArray(); byte[] array1 = bigInteger1.toByteArray(); // 翻转 byte[] ArrayUtils.reverse(array0); ArrayUtils.reverse(array1); // 将 byte[] 转换为无符号整数，并转为十六进制字符串 String part0 = (new BigInteger(1, array0)).toString(16); String part1 = (new BigInteger(1, array1)).toString(16); System.out.println(part0 + part1); // a4fb17cba6d455e4812ad28989780cbc }}本文出处 walker snapshot

当我们在做 SPA 应用的时候，为了兼容老的浏览器（如IE9）我们不得不放弃 HTML5 browser history api 而只能采用 hash 路由的这种形式来实现前端路由，但是因为 hash 被路由占据了，导致本来不是问题的锚点功能却成了一个不大不小的问题。 经过我自己的搜索目前有两种方式能够解决这个问题，为了能在 react 生态下面简单优雅的使用，我专门封装了一个锚点组件 react-anchor-without-hash，它使用了类似原生 a 标签的写法，并且可以支持滚动的距离和指定滚动的元素，尽可能的满足业务的需求。 不过在介绍这个组件之前，还是得先说一下两种基本的解决方案。 两种解决方案scrollIntoViewscrollIntoView 方法可以让当前的元素滚动到浏览器窗口的可视区域内。 它的使用方法如下： var element = document.getElementById("box");element.scrollIntoView();这个 api 兼容 IE8 及以上的浏览器，所以可以放心使用。 注：IE10 之前的 IE 浏览器部分支持，具体请查看Can I Use。scrollTop另一个方法是使用 scrollTop 这个 api，这个方法的兼容性也是比较好的，这个方法相比于 scrollIntoView 来说需要你自己定义要滚动的元素和要滚动的高度，虽然看起来麻烦一些，但是好处是自由度比较高，试想一下下面的场景： 你有一个 A 元素在 Content 里面，Content 设置了滚动，你想让 A 元素滚动到可视区域内。 如果用 scrollIntoView 会变成下面这样，A 元素显示到整个浏览器视口的最上面，这样就会和 Header 重合，被遮挡住一部分。 所以这时候需要使用 scrollTop 去设置 content 滚动距离，比如说是 60px，最后的效果就变成了我们想要的结果。 使用方式如下： const cont = document.querySelector('#container');const a = document.querySelector('#a');cont.scrollTop = a.offsetTop + 60;react-anchor-without-hash以上两种方式如果想方便的在项目里面使用多少都需要封装一下，而且使用起来和原生的 a 标签形式也相差甚远。 ...

南朝四百八十寺多少楼台烟雨中 前言本题摘自LeetCode第242题，有效的字母异位词， 题目描述给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 事例1： 输入: s = "anagram", t = "nagaram"输出: true事例2： 输入: s = "rat", t = "car"输出: false解题思想1.初始化两个数组（理解为哈希表），对应26个英文字母，开始值都为0 int a[26] = {0}; int b[26] = {0}; 2.分别遍历s、t字符串的中的字符，给字符在数组中的位置值进行加加操作 3.对比a、b数组中的值是否一致 C语言代码实现 BOOL isVaildAgment(char *s, char *t) { int lengthS = strlen(s); int lengthT = strlen(t); int a[26] = {0}; int b[26] = {0}; for (NSInteger i = 0; i < lengthS; i++) { int index = s[i]-'a'; a[index] = 1; } for (NSInteger i = 0; i < lengthT; i++) { int index = t[i]-'a'; b[index] = 1; } for (NSInteger i = 0; i < 26; i++) { if (a[i] != b[i]) { return false; } } return true; }

一、history window.history(可直接写成history)指向History对象，它表示当前窗口的浏览历史。History对象保存了当前窗口访问过的所有页面网址 1. length history.length属性保存着历史记录的url数量，初始时该值为1，如果当前窗口先后访问了三个网址，那么history对象就包括3项，history.length=32.跳转方法：允许在浏览器历史之间移动 go() 接受一个整数为参数，移动到该整数指定的页面，比如history.go(1)相当于history.forward(),history.go(-1)相当于history.back(),history.go(0)相当于刷新当前页面back() 移动到上一个访问页面，等同于浏览器的后退键,常见的返回上一页就可以用back()，是从浏览器缓存中加载，而不是重新要求服务器发送新的网页forward() 移动到下一个访问页面，等同于浏览器的前进键如果移动的位置超出了访问历史的边界，以上三个方法并不报错，而是默默的失败3.history.pushState() 在浏览器历史中添加记录 if(!!(window.hostory && history.pushState)) { // 支持History API} else { // 不支持}以上代码可以用来检查当前浏览器是否支持History API。如果不支持的话可以考虑使用Polyfill库History.jshistory.pushstate()方法接受三个参数，以此为： state: 一个与指定网址相关的状态对象，popState事件触发时，该对象会传入回调函数，如果不需要这个对象，此处可填nulltitle: 新页面的标题，但是所有浏览器目前都忽略这个值，因此这里可以填nullurl: 新的网址，必须与当前页面处在同一个域，浏览器的地址栏将显示这个网址假定当前网址是example.com/1.html，我们使用pushState方法在浏览记录(history对象)中添加一个记录 var stateObj = {foo:'bar'};history.pushState(stateObj,'page 2','2.html')添加上边这个新纪录后，浏览器地址栏立刻显示example.com/2.html，但不会跳转到2.html，甚至也不会检查2.html是否存在，它只是成为浏览历史中的新纪录。这时，你在地址栏输入一个新的地址，然后点击了后退按钮，页面的url将显示2.html；你再点击以此后退按钮，url将显示1.html总之，pushState方法不会触发页面刷新，只是导致了history对象发生变化，地址栏会有反应。如果pushState的url参数，设置了一个新的锚点值（即hash），并不会触发hashChange事件，如果设置了一个跨域网址，则会报错。 //报错history.pushState(null,null,'https://twitter.com/hello')上边代码中，pushState()想要插入一个跨域的网址，导致报错，这样设计的目的是防止恶意代码让用户以为他们是在另一个网站上 4. history.replaceState()history.replaceState()方法的参数和pushState()方法一摸一样，区别是它修改浏览器历史当中的记录假定当前页面是example.com/example.html history.pushState({page:1},'title 1','?page=1')history.pushState({page:2},'title 2','?page=2')history.replaceState({page:3},'title 3','?page=3')history.back() //url显示为example.com/example.html?page=1history.back() //url显示为example.com/example.htmlhistory.go(2) //url显示为example.com/example.html?page=35. history.state属性history.state返回当前页面的state对象 history.pushState({page:1},'title 1','?page=1')history.state //{page:1}5. popState 事件每当同一个文档的浏览历史（即history）出现变化时，就会触发popState事件需要注意：仅仅调用pushState方法或replaceState方法，并不会触发该事件，只有用户点击浏览器后退和前进按钮时，或者使用js调用back、forward、go方法时才会触发。另外该事件只针对同一个文档，如果浏览历史的切换，导致加载不同的文档，该事件不会被触发使用的时候，可以为popState事件指定回调函数 window.onpopstate = function (event) { console.log('location: ' + document.location); console.log('state: ' +JSON.stringify(event.state));};// 或者window.addEventListener('popstate', function(event) { console.log('location: ' + document.location); console.log('state: ' + JSON.stringify(event.state));});回调函数的参数是一个event事件对象，它的state属性指向pushState和replaceState方法为当前url所提供的状态对象（即这两个方法的第一个参数）。上边代码中的event.state就是通过pushState和replaceState方法为当前url绑定的state对象这个state也可以直接通过history对象读取history.state注意：页面第一次加载的时候，浏览器不会触发popState事件 ...

一致性哈希算法在分布式缓存领域的 MemCached，负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用，它主要是为了解决传统哈希函数添加哈希表槽位数后要将关键字重新映射的问题。 本文会介绍一致性哈希算法的原理及其实现，并给出其不同哈希函数实现的性能数据对比，探讨Redis 集群的数据分片实现等，文末会给出实现的具体 github 地址。 Memcached 与客户端分布式缓存Memcached 是一个高性能的分布式缓存系统，然而服务端没有分布式功能，各个服务器不会相互通信。它的分布式实现依赖于客户端的程序库，这也是 Memcached 的一大特点。比如第三方的 spymemcached 客户端就基于一致性哈希算法实现了其分布式缓存的功能。 其具体步骤如下: 向 Memcached 添加数据，首先客户端的算法根据 key 值计算出该 key 对应的服务器。服务器选定后，保存缓存数据。获取数据时，对于相同的 key ，客户端的算法可以定位到相同的服务器，从而获取数据。在这个过程中，客户端的算法首先要保证缓存的数据尽量均匀地分布在各个服务器上，其次是当个别服务器下线或者上线时，会出现数据迁移，应该尽量减少需要迁移的数据量。 客户端算法是客户端分布式缓存性能优劣的关键。 普通的哈希表算法一般都是计算出哈希值后，通过取余操作将 key 值映射到不同的服务器上，但是当服务器数量发生变化时，取余操作的除数发生变化，所有 key 所映射的服务器几乎都会改变，这对分布式缓存系统来说是不可以接收的。 一致性哈希算法能尽可能减少了服务器数量变化所导致的缓存迁移。 哈希算法首先，一致性哈希算法依赖于普通的哈希算法。大多数同学对哈希算法的理解可能都停留在 JDK 的 hashCode 函数上。其实哈希算法有很多种实现，它们在不同方面都各有优劣，针对不同的场景可以使用不同的哈希算法实现。 下面，我们会介绍一下几款比较常见的哈希算法，并且了解一下它们在分布均匀程度，哈希碰撞概率和性能等方面的优劣。 MD5 算法：全称为 Message-Digest Algorithm 5，用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一，主流编程语言普遍已有 MD5 实现。MD5 的作用是把大容量信息压缩成一种保密的格式（就是把一个任意长度的字节串变换成定长的16进制数字串）。常见的文件完整性校验就是使用 MD5。 CRC 算法：全称为 CyclicRedundancyCheck，中文名称为循环冗余校验。它是一类重要的，编码和解码方法简单，检错和纠错能力强的哈希算法，在通信领域广泛地用于实现差错控制。 MurmurHash 算法：高运算性能，低碰撞率，由 Austin Appleby 创建于 2008 年，现已应用到 Hadoop、libstdc++、nginx、libmemcached 等开源系统。Java 界中 Redis，Memcached，Cassandra，HBase，Lucene和Guava 都在使用它。 ...

前言最近在看一些NPM库的时候总是看到各种哈希签名算法，之前工作中也有用到过签名算法，但并没有深入理解过其中的原理，于是找了点资料稍微了解了一下，总结了这篇文章。哈希摘要算法哈希函数（也称散列函数），是一种根据任意长度数据计算出固定签名长度的算法，比如MD5，SHA系列。哈希签名摘要算法特点不是加密算法，而是一种摘要算法不可逆，“单向”函数签名长度固定存在2的N次方种结果，N表示签名长度以MD5为例MD5是由美国密码学家罗纳德·李维斯特（Ronald Linn Rivest）设计一种加密算法。128个bits长度，也就是16个字节输出结果由为“0-F”字符组成，不区分大小写存在2的128次方种输出结果MD5算法一、源数据处理计算原文长度(bits)对512求余的结果，需要填充原文使得原文对512求余的结果等于448, 填充的方法是第一位填充1，其余位填充0。填充完后，信息的长度为512 * N + 448。剩余64bits存储空间用来填充源信息长度，填充在448byte 数据之后。最终经过处理后的数据长度为 512 * N。动手画了一张简单的图来说明：二、处理数据1、数据进行处理前，会定义4个常量，作为初始值这4个常量分别是var a = 0x67452301;var b = 0xEFCDAB89;var c = 0x98BADCFE;var d = 0x10325476;翻译成二进制就是var a = 1732584193;var b = -271733879;var c = -1732584194;var d = 271733878;2、将处理后的数据，外循环处理N次，N为第一步中512的整数倍。每次外循环处理的会产生新的“a、b、c、d”值，每次新产生的“a、b、c、d”值会再一次提供给下一次外循环使用3、在每个外循环中又进行内循环处理64次，在这64次数据处理中会不停的将 512 bytes 数据中的 16个小单元不停的通过4个函数进行交叉处理，共计进行64轮计算。4、最终生成新的“a、b、c、d”，新的“a、b、c、d”分别是占用32bytes的数据5、最终生成的“a、b、c、d”转换为对应的ascll占用的字节，32 bytes * 4 = 128 bytes， 一个字节占用8个bytes， 也就是16个字节,16个字节转换为ASCII码，再将ASCII码转换为16进制数据，即可得到一个32个字节长度的hash值。内外循环代码function binl_md5(x, len) { /* append padding */ x[len >> 5] = x[len >> 5] | 0x80 << (len % 32); x[(((len + 64) >>> 9) << 4) + 14] = len; var i, olda, oldb, oldc, oldd, a = 1732584193, b = -271733879, c = -1732584194, d = 271733878; // 每次计算位移值，可以理解为是常量 var ffShift = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22]; var ggShift = [5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20]; var hhShift = [4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23]; var iiShift = [6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]; // Todo: 四个字节一组，每个组别之间不停的交叉计算，不停的根据已计算出来的值多次计算赋值 // x[i]装的是4个字节的数据 // x.length 为 512 * N / 32 // i += 16 每512bits长度的数据分为了16组，而每次循环的计算单位是以512为一个单元的，所以每次都是+16 for (i = 0; i < x.length; i += 16) { olda = a; oldb = b; oldc = c; oldd = d; // 64轮计算中包含原始“a、b、c、d”值。 // 以及位移值，以及一个计算常量，这两个是MD5规范中所定义的常量 a = md5_ff(a, b, c, d, x[i], ffShift[0], -680876936); d = md5_ff(d, a, b, c, x[i + 1], ffShift[1], -389564586); c = md5_ff(c, d, a, b, x[i + 2], ffShift[2], 606105819); b = md5_ff(b, c, d, a, x[i + 3], ffShift[3], -1044525330); a = md5_ff(a, b, c, d, x[i + 4], ffShift[4], -176418897); d = md5_ff(d, a, b, c, x[i + 5], ffShift[5], 1200080426); c = md5_ff(c, d, a, b, x[i + 6], ffShift[6], -1473231341); b = md5_ff(b, c, d, a, x[i + 7], ffShift[7], -45705983); a = md5_ff(a, b, c, d, x[i + 8], ffShift[8], 1770035416); d = md5_ff(d, a, b, c, x[i + 9], ffShift[9], -1958414417); c = md5_ff(c, d, a, b, x[i + 10], ffShift[10], -42063); b = md5_ff(b, c, d, a, x[i + 11], ffShift[11], -1990404162); a = md5_ff(a, b, c, d, x[i + 12], ffShift[12], 1804603682); d = md5_ff(d, a, b, c, x[i + 13], ffShift[13], -40341101); c = md5_ff(c, d, a, b, x[i + 14], ffShift[14], -1502002290); b = md5_ff(b, c, d, a, x[i + 15], ffShift[15], 1236535329); a = md5_gg(a, b, c, d, x[i + 1], ggShift[0], -165796510); d = md5_gg(d, a, b, c, x[i + 6], ggShift[1], -1069501632); c = md5_gg(c, d, a, b, x[i + 11], ggShift[2], 643717713); b = md5_gg(b, c, d, a, x[i], ggShift[3], -373897302); a = md5_gg(a, b, c, d, x[i + 5], ggShift[4], -701558691); d = md5_gg(d, a, b, c, x[i + 10], ggShift[5], 38016083); c = md5_gg(c, d, a, b, x[i + 15], ggShift[6], -660478335); b = md5_gg(b, c, d, a, x[i + 4], ggShift[7], -405537848); a = md5_gg(a, b, c, d, x[i + 9], ggShift[8], 568446438); d = md5_gg(d, a, b, c, x[i + 14], ggShift[9], -1019803690); c = md5_gg(c, d, a, b, x[i + 3], ggShift[10], -187363961); b = md5_gg(b, c, d, a, x[i + 8], ggShift[11], 1163531501); a = md5_gg(a, b, c, d, x[i + 13], ggShift[12], -1444681467); d = md5_gg(d, a, b, c, x[i + 2], ggShift[13], -51403784); c = md5_gg(c, d, a, b, x[i + 7], ggShift[14], 1735328473); b = md5_gg(b, c, d, a, x[i + 12], ggShift[15], -1926607734); a = md5_hh(a, b, c, d, x[i + 5], hhShift[0], -378558); d = md5_hh(d, a, b, c, x[i + 8], hhShift[1], -2022574463); c = md5_hh(c, d, a, b, x[i + 11], hhShift[2], 1839030562); b = md5_hh(b, c, d, a, x[i + 14], hhShift[3], -35309556); a = md5_hh(a, b, c, d, x[i + 1], hhShift[4], -1530992060); d = md5_hh(d, a, b, c, x[i + 4], hhShift[5], 1272893353); c = md5_hh(c, d, a, b, x[i + 7], hhShift[6], -155497632); b = md5_hh(b, c, d, a, x[i + 10], hhShift[7], -1094730640); a = md5_hh(a, b, c, d, x[i + 13], hhShift[8], 681279174); d = md5_hh(d, a, b, c, x[i], hhShift[9], -358537222); c = md5_hh(c, d, a, b, x[i + 3], hhShift[10], -722521979); b = md5_hh(b, c, d, a, x[i + 6], hhShift[11], 76029189); a = md5_hh(a, b, c, d, x[i + 9], hhShift[12], -640364487); d = md5_hh(d, a, b, c, x[i + 12], hhShift[13], -421815835); c = md5_hh(c, d, a, b, x[i + 15], hhShift[14], 530742520); b = md5_hh(b, c, d, a, x[i + 2], hhShift[15], -995338651); a = md5_ii(a, b, c, d, x[i], iiShift[0], -198630844); d = md5_ii(d, a, b, c, x[i + 7], iiShift[1], 1126891415); c = md5_ii(c, d, a, b, x[i + 14], iiShift[2], -1416354905); b = md5_ii(b, c, d, a, x[i + 5], iiShift[3], -57434055); a = md5_ii(a, b, c, d, x[i + 12], iiShift[4], 1700485571); d = md5_ii(d, a, b, c, x[i + 3], iiShift[5], -1894986606); c = md5_ii(c, d, a, b, x[i + 10], iiShift[6], -1051523); b = md5_ii(b, c, d, a, x[i + 1], iiShift[7], -2054922799); a = md5_ii(a, b, c, d, x[i + 8], iiShift[8], 1873313359); d = md5_ii(d, a, b, c, x[i + 15], iiShift[9], -30611744); c = md5_ii(c, d, a, b, x[i + 6], iiShift[10], -1560198380); b = md5_ii(b, c, d, a, x[i + 13], iiShift[11], 1309151649); a = md5_ii(a, b, c, d, x[i + 4], iiShift[12], -145523070); d = md5_ii(d, a, b, c, x[i + 11], iiShift[13], -1120210379); c = md5_ii(c, d, a, b, x[i + 2], iiShift[14], 718787259); b = md5_ii(b, c, d, a, x[i + 9], iiShift[15], -343485551); a = safe_add(a, olda); b = safe_add(b, oldb); c = safe_add(c, oldc); d = safe_add(d, oldd); } // 最终生成4个占用32 bytes控制的值 return [a, b, c, d];}四轮计算线性函数F(X,Y,Z) =(X&Y)|((~X)&Z) G(X,Y,Z) =(X&Z)|(Y&(~Z)) H(X,Y,Z) =X^Y^Z I(X,Y,Z)=Y^(X|(~Z)) 6、第五点可以解释为什么生成的hash值中只会包含“0-F”，且不区分大小写的原因，长度为16。function rstr2hex(input) { var hex_tab = ‘0123456789abcdef’, output = ‘’, x, i; for (i = 0; i < input.length; i += 1) { x = input.charCodeAt(i); output += hex_tab.charAt((x >>> 4) & 0x0F) + hex_tab.charAt(x & 0x0F); x:${input.charCodeAt(i)}, output: ${output}`); } return output;}以上代码来自 https://github.com/blueimp/JavaScript-MD5，稍有改动。适用场景：私密数据加密，比如用户密码一般都不会明文存储，而是通过加密后存入数据库赌场开盘前将开票结果公布，开盘后通过签名对比校验是否存在作弊行为检测文件是否下载完成，比如迅雷下载…如何破解MD5中，虽然由源文可以推导出签名，反过来，并不能由签名推导出源文。但MD5并不是坚不可摧，目前有两种破解方式碰撞法，虽然MD5签名存在2的128次方种输出结果，但每个签名对应的原文并不是唯一的，只要计算机性能够强大，给予充足的时间，总能找到能输出相同签名的数据源。映射法，把常规字符串对应的签名存储，比如常用的“123456”，“abcdefg”等。当得到MD5签名时，就可以映射出源数据。如何防范：使用安全性更高的SHA256，并不是说SHA256不能被破解，只是相对于MD5来说算法步骤更多，也更复杂，破解难度更大。源数据 + KEY，比如“123456”加上KEY就变成了“123456@#DFF23DS”,其中“@#DFF23DS”就是服务端存储的KEY。“源数据 + KEY” => 签名。源数据 + KEY + 动态数据，KEY有可能会被猜到，如果再加上动态数据的话，破解难度会进一步提升，比如用户名、动态密码。“源数据 + KEY + 动态密码” => 签名。多次MD5，MD5(“123456”)很容易被猜到，MD5(MD5(“123456”)),将MD5后的签名再进行一次MD5呢，如果进行三次，十次，是不是破解的难度会更大，当然这么做会增加计算时间，需要权衡。其他：中文编码需要转码，否则前端与后端编码后的值可能不一致。除了MD5算法，还存在很多其他形式的哈希函数算法，比如SHA系列，他们的设计思路大体相同。参考资料阮一峰讲解操作符按位移动操作符各种进制在线转换维基百科MD5 维基百科SHA2NPM MD5 ...

前言记得一年前分享过一篇《一致性 Hash 算法分析》，当时只是分析了这个算法的实现原理、解决了什么问题等。但没有实际实现一个这样的算法，毕竟要加深印象还得自己撸一遍，于是本次就当前的一个路由需求来着手实现一次。背景看过《为自己搭建一个分布式 IM(即时通讯) 系统》的朋友应该对其中的登录逻辑有所印象。先给新来的朋友简单介绍下 cim 是干啥的：其中有一个场景是在客户端登录成功后需要从可用的服务端列表中选择一台服务节点返回给客户端使用。而这个选择的过程就是一个负载策略的过程；第一版本做的比较简单，默认只支持轮询的方式。虽然够用，但不够优雅????。因此我的规划是内置多种路由策略供使用者根据自己的场景选择，同时提供简单的 API 供用户自定义自己的路由策略。先来看看一致性 Hash 算法的一些特点：构造一个 0 ~ 2^32-1 大小的环。服务节点经过 hash 之后将自身存放到环中的下标中。客户端根据自身的某些数据 hash 之后也定位到这个环中。通过顺时针找到离他最近的一个节点，也就是这次路由的服务节点。考虑到服务节点的个数以及 hash 算法的问题导致环中的数据分布不均匀时引入了虚拟节点。自定义有序 Map根据这些客观条件我们很容易想到通过自定义一个有序数组来模拟这个环。这样我们的流程如下：初始化一个长度为 N 的数组。将服务节点通过 hash 算法得到的正整数，同时将节点自身的数据（hashcode、ip、端口等）存放在这里。完成节点存放后将整个数组进行排序（排序算法有多种）。客户端获取路由节点时，将自身进行 hash 也得到一个正整数；遍历这个数组直到找到一个数据大于等于当前客户端的 hash 值，就将当前节点作为该客户端所路由的节点。如果没有发现比客户端大的数据就返回第一个节点（满足环的特性）。先不考虑排序所消耗的时间，单看这个路由的时间复杂度：最好是第一次就找到，时间复杂度为O(1)。最差为遍历完数组后才找到，时间复杂度为O(N)。理论讲完了来看看具体实践。我自定义了一个类：SortArrayMap他的使用方法及结果如下：可见最终会按照 key 的大小进行排序，同时传入 hashcode = 101 时会按照顺时针找到 hashcode = 1000 这个节点进行返回。下面来看看具体的实现。成员变量和构造函数如下：其中最核心的就是一个 Node 数组，用它来存放服务节点的 hashcode 以及 value 值。其中的内部类 Node 结构如下：写入数据的方法如下：相信看过 ArrayList 的源码应该有印象，这里的写入逻辑和它很像。写入之前判断是否需要扩容，如果需要则复制原来大小的 1.5 倍数组来存放数据。之后就写入数组，同时数组大小 +1。但是存放时是按照写入顺序存放的，遍历时自然不会有序；因此提供了一个 Sort 方法，可以把其中的数据按照 key 其实也就是 hashcode 进行排序。排序也比较简单，使用了 Arrays 这个数组工具进行排序，它其实是使用了一个 TimSort 的排序算法，效率还是比较高的。最后则需要按照一致性 Hash 的标准顺时针查找对应的节点：代码还是比较简单清晰的；遍历数组如果找到比当前 key 大的就返回，没有查到就取第一个。这样就基本实现了一致性 Hash 的要求。ps:这里并不包含具体的 hash 方法以及虚拟节点等功能（具体实现请看下文），这个可以由使用者来定，SortArrayMap 可作为一个底层的数据结构，提供有序 Map 的能力，使用场景也不局限于一致性 Hash 算法中。TreeMap 实现SortArrayMap 虽说是实现了一致性 hash 的功能，但效率还不够高，主要体现在 sort 排序处。下图是目前主流排序算法的时间复杂度：最好的也就是 O(N) 了。这里完全可以换一个思路，不用对数据进行排序；而是在写入的时候就排好顺序，只是这样会降低写入的效率。比如二叉查找树，这样的数据结构 jdk 里有现成的实现；比如 TreeMap 就是使用红黑树来实现的，默认情况下它会对 key 进行自然排序。来看看使用 TreeMap 如何来达到同样的效果。运行结果：127.0.0.1000效果和上文使用 SortArrayMap 是一致的。只使用了 TreeMap 的一些 API：写入数据候，TreeMap 可以保证 key 的自然排序。tailMap 可以获取比当前 key 大的部分数据。当这个方法有数据返回时取第一个就是顺时针中的第一个节点了。如果没有返回那就直接取整个 Map 的第一个节点，同样也实现了环形结构。ps:这里同样也没有 hash 方法以及虚拟节点（具体实现请看下文），因为 TreeMap 和 SortArrayMap 一样都是作为基础数据结构来使用的。性能对比为了方便大家选择哪一个数据结构，我用 TreeMap 和 SortArrayMap 分别写入了一百万条数据来对比。先是 SortArrayMap：耗时 2237 毫秒。TreeMap：耗时 1316毫秒。结果是快了将近一倍，所以还是推荐使用 TreeMap 来进行实现，毕竟它不需要额外的排序损耗。cim 中的实际应用下面来看看在 cim 这个应用中是如何具体使用的，其中也包括上文提到的虚拟节点以及 hash 算法。模板方法在应用的时候考虑到就算是一致性 hash 算法都有多种实现，为了方便其使用者扩展自己的一致性 hash 算法因此我定义了一个抽象类；其中定义了一些模板方法，这样大家只需要在子类中进行不同的实现即可完成自己的算法。AbstractConsistentHash，这个抽象类的主要方法如下：add 方法自然是写入数据的。sort 方法用于排序，但子类也不一定需要重写，比如 TreeMap 这样自带排序的容器就不用。getFirstNodeValue 获取节点。process 则是面向客户端的，最终只需要调用这个方法即可返回一个节点。下面我们来看看利用 SortArrayMap 以及 AbstractConsistentHash 是如何实现的。就是实现了几个抽象方法，逻辑和上文是一样的，只是抽取到了不同的方法中。只是在 add 方法中新增了几个虚拟节点，相信大家也看得明白。把虚拟节点的控制放到子类而没有放到抽象类中也是为了灵活性考虑，可能不同的实现对虚拟节点的数量要求也不一样，所以不如自定义的好。但是 hash 方法确是放到了抽象类中，子类不用重写；因为这是一个基本功能，只需要有一个公共算法可以保证他散列地足够均匀即可。因此在 AbstractConsistentHash 中定义了 hash 方法。这里的算法摘抄自 xxl_job，网上也有其他不同的实现，比如 FNV1_32_HASH 等；实现不同但是目的都一样。这样对于使用者来说就非常简单了：他只需要构建一个服务列表，然后把当前的客户端信息传入 process 方法中即可获得一个一致性 hash 算法的返回。同样的对于想通过 TreeMap 来实现也是一样的套路：他这里不需要重写 sort 方法，因为自身写入时已经排好序了。而在使用时对于客户端来说只需求修改一个实现类，其他的啥都不用改就可以了。运行的效果也是一样的。这样大家想自定义自己的算法时只需要继承 AbstractConsistentHash 重写相关方法即可，客户端代码无须改动。路由算法扩展性但其实对于 cim 来说真正的扩展性是对路由算法来说的，比如它需要支持轮询、hash、一致性hash、随机、LRU等。只是一致性 hash 也有多种实现，他们的关系就如下图：应用还需要满足对这一类路由策略的灵活支持，比如我也想自定义一个随机的策略。因此定义了一个接口：RouteHandlepublic interface RouteHandle { /** * 再一批服务器里进行路由 * @param values * @param key * @return */ String routeServer(List<String> values,String key) ;}其中只有一个方法，也就是路由方法；入参分别是服务列表以及客户端信息即可。而对于一致性 hash 算法来说也是只需要实现这个接口，同时在这个接口中选择使用 SortArrayMapConsistentHash 还是 TreeMapConsistentHash 即可。这里还有一个 setHash 的方法，入参是 AbstractConsistentHash；这就是用于客户端指定需要使用具体的那种数据结构。而对于之前就存在的轮询策略来说也是同样的实现 RouteHandle 接口。这里我只是把之前的代码搬过来了而已。接下来看看客户端到底是如何使用以及如何选择使用哪种算法。为了使客户端代码几乎不动，我将这个选择的过程放入了配置文件。如果想使用原有的轮询策略，就配置实现了 RouteHandle 接口的轮询策略的全限定名。如果想使用一致性 hash 的策略，也只需要配置实现了 RouteHandle 接口的一致性 hash 算法的全限定名。当然目前的一致性 hash 也有多种实现，所以一旦配置为一致性 hash 后就需要再加一个配置用于决定使用 SortArrayMapConsistentHash 还是 TreeMapConsistentHash 或是自定义的其他方案。同样的也是需要配置继承了 AbstractConsistentHash 的全限定名。不管这里的策略如何改变，在使用处依然保持不变。只需要注入 RouteHandle，调用它的 routeServer 方法。@Autowiredprivate RouteHandle routeHandle ;String server = routeHandle.routeServer(serverCache.getAll(),String.valueOf(loginReqVO.getUserId()));既然使用了注入，那其实这个策略切换的过程就在创建 RouteHandle bean 的时候完成的。也比较简单，需要读取之前的配置文件来动态生成具体的实现类，主要是利用反射完成的。这样处理之后就比较灵活了，比如想新建一个随机的路由策略也是同样的套路；到时候只需要修改配置即可。感兴趣的朋友也可提交 PR 来新增更多的路由策略。总结希望看到这里的朋友能对这个算法有所理解，同时对一些设计模式在实际的使用也能有所帮助。相信在金三银四的面试过程中还是能让面试官眼前一亮的，毕竟根据我这段时间的面试过程来看听过这个名词的都在少数????（可能也是和候选人都在 1~3 年这个层级有关）。以上所有源码：https://github.com/crossoverJie/cim如果本文对你有所帮助还请不吝转发。 ...

题目要求Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.This is case sensitive, for example “Aa” is not considered a palindrome here.Note:Assume the length of given string will not exceed 1,010.Example:Input:“abccccdd"Output:7Explanation:One longest palindrome that can be built is “dccaccd”, whose length is 7.输入一个字符串，计算用这个字符串中的值构成一个最长回数的长度是多少。思路和代码这是一道easy难度的题目，但是一次性写对也有挑战。直观来看，我们立刻就能想到统计字符串中每个字符出现的次数，如果该字符出现次数为偶数，则字符一定存在于回数中。但是我们忽略了一点，即如果字符中存在一个额外的单个字符位于中间，该字符串也能构成回数，如aabaa。这个细节需要注意。下面是O(N)时间的实现： public int longestPalindrome(String s) { int[] count = new int[52]; int max = 0; for(char c : s.toCharArray()) { if(c>=‘a’ && c<=‘z’){ count[c-‘a’]++; if(count[c-‘a’] % 2 == 0) { max +=2; } } if(c>=‘A’ && c<=‘Z’){ count[c-‘A’ + 26]++; if(count[c-‘A’+26] % 2 == 0) { max += 2; } } } if(max < s.length()) { max++; } return max; } ...

这里总结一下Hash散列当出现不能插入位置的几种位移和计算方式，以免遗忘和出现不知道都在讲些神马；当我们key1和key2冲突的时候，主要有三种方式进行冲突解决；先来说两种开放定址法，所谓开放定址法就是重新计算了hash值；1.线性探查法：当我们插入key的位置，产生冲突之后，加1，查看该位置是否可以使用。如果不可以使用，再次+1，重复到找到位置，或者查完没有满足的位置，并且在这个途中，可以越过尾部，从hash序列头部进行枚举。但是该方法有一个缺点，就是容易造成元素扎堆；2.平方探查法：插入时，当H(key)的位置被占时，将检查下列位置：H(key)+1^2,H(key)-1^2,H(key)+2^2,H(key)-2^2…。如果在这个途中H(key)+k^2超过了表长，则进行取模操作;如果H(key)-k^2<0时，则进行((H(key)-k^2)%Tsize+Tsize)%Tsize,从而保证索引为正；这两个方向的操作称为正向和负向操作，为了避免计算麻烦，往往可以采用正向操作；注意一点，寻找的次数k在[0,Tsize]内，当k超过这个范围，必不可能插入，停止计算；第三中时拉链法则：3.拉链法：拉链法不计算新的hash值，而是在重复Hash值的地方构建一个单链表，从而将所有重复的节点连接起来，查询的时候遍历该链表中的所有元素；

题目要求Design a data structure that supports all following operations in average O(1) time.Note: Duplicate elements are allowed.insert(val): Inserts an item val to the collection.remove(val): Removes an item val from the collection if present.getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.Example:// Init an empty collection.RandomizedCollection collection = new RandomizedCollection();// Inserts 1 to the collection. Returns true as the collection did not contain 1.collection.insert(1);// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].collection.insert(1);// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].collection.insert(2);// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.collection.getRandom();// Removes 1 from the collection, returns true. Collection now contains [1,2].collection.remove(1);// getRandom should return 1 and 2 both equally likely.collection.getRandom();设计一个数据结构，支持能够在O(1)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。强烈建议先看一下这个问题的基础版本，传送门在这里。思路和代码遵循之前基础版本的思路，当解决这种问题的时候我们会用数组和hashmap来做位置的存储，从而更新的时候无需检索。但是在这题的情境下，存在一个问题，举个例子：假如现在插入1,2,3,3,4,3,3此时的map中应当是如下：1:[0] 2:[1] 3:[2,3,5,6] 4:[4]我们先执行删除1，按照之前的规则，我们会删除数组中最后一个元素，并将其值移动到这个位置上map应当被更新为2:[1] 3:[2,3,5,0] 4:[4]接着我们再删除2，此时虽然最后一个元素还是3，但是这个3在位置数组中的位置却是需要O(n)的时间来查询的，这就违反了O(1)的删除时间复杂度。网上有一些java实现采用OrderSet来解决，这是不合理的。因为有序堆本质上底层是一个最大堆或最小堆，它的插入和删除操作都需要O(lgn)的时间复杂度来完成这里我们采用的方式是继续冗余，即我们在插入每一个元素的时候，同时记录该元素在下标数组中的位置，举个例子：先插入1，则map的值为[1:[0]]，list的值为[[1,0]] 此处的0代表1这个值在下标数组[0]中位于第0个位置上。在插入2，则map的值为[1:[0], 2:[1]], list的值为[[1,0],[2,0]]再插入1，此时map=[1:[0, 2], 2:[1], list的值为[[1,0],[2,0],[1,1]]此时删除2，同理，我们还是会将数组中最后一个元素的值替换在删除掉元素的位置，此处我们从map中得出2最后一次在数组中出现的下标为1，我们需要将最后位置上的1替换掉当前2的值，之后我们还能从数组中得知，1这个数字它对应的位置下标的索引为2，因此我们再将map[1]中map[1][2]的值替换为2所在的新的位置，即1。此时的map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]代码如下：public class InsertDeleteGetRandomDuplicatesallowed_381 { private List<Pair> list; private Map<Integer, List<Integer>> index; /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. / public InsertDeleteGetRandomDuplicatesallowed_381() { list = new ArrayList<>(); index = new HashMap<>(); } public boolean insert(int val) { boolean contains = true; if(!index.containsKey(val) || index.get(val).isEmpty()) { contains = false; } List<Integer> tmp = index.getOrDefault(val, new ArrayList<>()); tmp.add(list.size()); index.put(val, tmp); list.add(new Pair(val, tmp.size()-1)); return !contains; } /* Removes a value from the collection. Returns true if the collection contained the specified element. / public boolean remove(int val) { if(!index.containsKey(val) || index.get(val).isEmpty()) { return false; } List<Integer> tmp = index.get(val); int position = tmp.remove(tmp.size()-1); if(position != list.size()-1) { Pair lastPair = list.get(list.size()-1); int lastValue = lastPair.value; List<Integer> lastValuePositions = index.get(lastValue); lastValuePositions.set(lastPair.position, position); list.set(position, lastPair); } list.remove(list.size()-1); return true; } /* Get a random element from the collection. */ public int getRandom() { int position = (int)Math.floor((Math.random() * list.size())); return list.get(position).value; } public static class Pair{ int value; int position; public Pair(int value, int position) { this.value = value; this.position = position; } } } ...

题目要求Design a data structure that supports all following operations in average O(1) time.insert(val): Inserts an item val to the set if not already present.remove(val): Removes an item val from the set if present.getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.Example:// Init an empty set.RandomizedSet randomSet = new RandomizedSet();// Inserts 1 to the set. Returns true as 1 was inserted successfully.randomSet.insert(1);// Returns false as 2 does not exist in the set.randomSet.remove(2);// Inserts 2 to the set, returns true. Set now contains [1,2].randomSet.insert(2);// getRandom should return either 1 or 2 randomly.randomSet.getRandom();// Removes 1 from the set, returns true. Set now contains [2].randomSet.remove(1);// 2 was already in the set, so return false.randomSet.insert(2);// Since 2 is the only number in the set, getRandom always return 2.randomSet.getRandom();设计一个数据结构，使得能够在O(1)的时间复杂度中插入数字，删除数字，以及随机获取一个数字。要求所有的数字都能够被等概率的随机出来。思路和代码其实有几个思路入手：如何实现O(1)的插入这里数字的插入还需要能够去重，即需要首先判断该数字是否已经存在，已经存在的话就不执行任何插入操作。如果底层是一个一般的数组，我们知道查询的时间复杂度为O(n)，明显不满足题目的意思。一个有序的数组能够将查询的时间复杂度下降到O(lgn），但是这依然不满足条件1，而且也无法做到所有的元素被等概率的查询出来，因为每插入一个元素都将改动之前元素的位置。而唯一能够做到O(1)时间查询的只有一个数据结构，即hash。因此，使用hash来查询时不可避免的。如何实现O(1)的删除这个其实是一个很经典的问题了，只要能够利用hash在O(1)的时间内找到这个数字的位置，就有两种方法来实现O(1)的删除，一个是利用伪删除，即每一个位置都对应一个状态为，将状态位社会为已经删除即可，还有一种就更有意思，就是将被删除位替换为数组最后一位的值，然后只需要删除最后一位就行。这种删除就无需将删除位右侧的元素全部左移造成O(n)的时间复杂度。这里我们采用的是第二种方法。如何实现O(1)的随机查询这个其实就是强调一点，我们需要维持原有的插入顺序，从而保证各个元素等概率被随机。综上所述，我们底层需要两种数据结构，一个hashmap来支持O(1)的查询，以及一个list来支持随机数的获取。代码实现如下：public class InsertDeleteGetRandom_380 { private List<Integer> list; private Map<Integer, Integer> hash; public InsertDeleteGetRandom_380() { list = new ArrayList<Integer>(); hash = new HashMap<Integer, Integer>(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. / public boolean insert(int val) { if(hash.containsKey(val)) { return false; } list.add(val); hash.put(val, list.size()-1); return true; } /* Removes a value from the set. Returns true if the set contained the specified element. / public boolean remove(int val) { if(!hash.containsKey(val)){ return false; } int position = hash.get(val); if(position != list.size()-1) { int last = list.get(list.size()-1); list.set(position, last); hash.put(last, position); } list.remove(list.size()-1); hash.remove(val); return true; } /* Get a random element from the set. */ public int getRandom() { int position = (int)Math.floor((Math.random() * list.size())); return list.get(position); }} ...

今天说一说从WIF到地址的这一串关系。简单说就一张图：或者他的简单版本好了，写完了。^_^当然，如果你想要搞清楚他们之间具体的计算方法，我们接着往下看。流程说明细说WIFL13wAkUX1SAx6K9zztkS8RjxDMedBEzbtgZSZRYKUUBMP23BEgLM这就是一个WIF，这串东西没什么意义，不用寻找他的意义了，他是一个byte58编码的字符串很遗憾base58并没有base64那么流行，所以很难找到web解码工具，我们写两行代码就可以分析出他们。8072520405d2ab00326dbcacfddd350b01222a7cc9efc5f304f742077ec9ade4630178a41006这串东西，才是Wif里面保存的真正数据红色部分就是私钥，黄色部分是加的盐，固定的信息。蓝色部分是对前面34个字节做了个hash，取了hash四个字节。从这个可以看出1.WIF 可以和私钥互转2.WIF保存了hash，有自我验证功能，不是你随便敲个字符串都是合法的WIF私钥NEO的公私钥验证方法使用的是ECC椭圆曲线算法。这类非对称加密算法的基本机制如下，私钥你保留着，公钥是公开的。你用私钥对一串数据进行签名。别人可以用 数据、签名、公钥 三者，断定这三者是不是匹配，签名是否有效。在NEO区块链上最主要的权限认证方式就是签名，所以私钥很重要，要保护好公钥公钥就是私钥的一部分，可以由私钥算出，但是反过来，公钥无法算出私钥。这个计算是单向的地址脚本地址脚本，看起来像是对公钥前面后面各加了一个字节实际上他是一个智能合约，将他反编译的话、就是：PushBytes[pubkey]CheckSig这样两条指令。当你访问你的账户的时候，比如用你的账户给别人转账，就会调用这个合约来验证。这个合约的意义是用你的公钥和交易数据 和交易签名进行验证。只有你签名的合约才能动你的账户地址ScriptHash地址ScriptHash就是地址脚本取了个Hash一次sha256，一次ripemd160地址地址和WIF很相似，不过他是ScriptHash 加了盐，加了验证功能，然后base58编码简化版的图是怎么回事因为私钥和WIF可以互相转换，通常我们在讲到私钥的时候，WIF也是私钥，私钥也是私钥，不会分那么清楚。因为地址ScriptHash 和 地址字符串可以互相转换，通常我们在讲到地址的时候，也不会分那么清楚另外因为地址脚本大多数用户根本接触不到，在和一般用户谈论这个话题的时候也可以省略掉所以这个关系图可以简化如下原文转自：https://www.cnblogs.com/crazy…

聚合算法执行原理在 SQL 中，聚合操作对一组值执行计算，并返回单个值。TiDB 实现了 2 种聚合算法：Hash Aggregation 和 Stream Aggregation。我们首先以 AVG 函数为例（案例参考 Stack Overflow），简述这两种算法的执行原理。假设表 t 如下：列 a列 b191-82-7261524SQL: select avg(b) from t group by a, 要求将表 t 的数据按照 a 的值分组，对每一组的 b 值计算平均值。不管 Hash 还是 Stream 聚合，在 AVG 函数的计算过程中，我们都需要维护 2 个中间结果变量 sum 和 count。Hash 和 Stream 聚合算法的执行原理如下。Hash Aggregate 的执行原理在 Hash Aggregate 的计算过程中，我们需要维护一个 Hash 表，Hash 表的键为聚合计算的 Group-By 列，值为聚合函数的中间结果 sum 和 count。在本例中，键为 列 a 的值，值为 sum(b) 和 count(b)。计算过程中，只需要根据每行输入数据计算出键，在 Hash 表中找到对应值进行更新即可。对本例的执行过程模拟如下。输入数据 a bHash 表 [key] (sum, count)1 9[1] (9, 1)1 -8[1] (1, 2)2 -7[1] (1, 2) [2] (-7, 1)2 6[1] (1, 2) [2] (-1, 2)1 5[1] (6, 3) [2] (-1, 2)2 4[1] (6, 3) [2] (3, 3)输入数据输入完后，扫描 Hash 表并计算，便可以得到最终结果：Hash 表avg(b)[1] (6, 3)2[2] (3, 3)1Stream Aggregation 的执行原理Stream Aggregate 的计算需要保证输入数据按照 Group-By 列有序。在计算过程中，每当读到一个新的 Group 的值或所有数据输入完成时，便对前一个 Group 的聚合最终结果进行计算。对于本例，我们首先对输入数据按照 a 列进行排序。排序后，本例执行过程模拟如下。输入数据是否为新 Group 或所有数据输入完成(sum, count)avg(b)1 9是(1, 9)前一个 Group 为空，不进行计算1 -8否(2, 1) 1 5否(3, 6) 2 -7是(1, -7)22 6否(2, -1) 2 4否(3, 3) 是 1因为 Stream Aggregate 的输入数据需要保证同一个 Group 的数据连续输入，所以 Stream Aggregate 处理完一个 Group 的数据后可以立刻向上返回结果，不用像 Hash Aggregate 一样需要处理完所有数据后才能正确的对外返回结果。当上层算子只需要计算部分结果时，比如 Limit，当获取到需要的行数后，可以提前中断 Stream Aggregate 后续的无用计算。当 Group-By 列上存在索引时，由索引读入数据可以保证输入数据按照 Group-By 列有序，此时同一个 Group 的数据连续输入 Stream Aggregate 算子，可以避免额外的排序操作。TiDB 聚合函数的计算模式由于分布式计算的需要，TiDB 对于聚合函数的计算阶段进行划分，相应定义了 5 种计算模式：CompleteMode，FinalMode，Partial1Mode，Partial2Mode，DedupMode。不同的计算模式下，所处理的输入值和输出值会有所差异，如下表所示：AggFunctionMode输入值输出值CompleteMode原始数据最终结果FinalMode中间结果最终结果Partial1Mode原始数据中间结果Partial2Mode中间结果进一步聚合的中间结果DedupMode原始数据去重后的原始数据以上文提到的 select avg(b) from t group by a 为例，通过对计算阶段进行划分，可以有多种不同的计算模式的组合，如：CompleteMode此时 AVG 函数的整个计算过程只有一个阶段，如图所示：Partial1Mode –> FinalMode此时我们将 AVG 函数的计算过程拆成两个阶段进行，如图所示：除了上面的两个例子外，还可能有如下的几种计算方式：聚合被下推到 TiKV 上进行计算（Partial1Mode），并返回经过预聚合的中间结果。为了充分利用 TiDB server 所在机器的 CPU 和内存资源，加快 TiDB 层的聚合计算，TiDB 层的聚合函数计算可以这样进行：Partial2Mode –> FinalMode。当聚合函数需要对参数进行去重，也就是包含 DISTINCT 属性，且聚合算子因为一些原因不能下推到 TiKV 时，TiDB 层的聚合函数计算可以这样进行：DedupMode –> Partial1Mode –> FinalMode。聚合函数分为几个阶段执行， 每个阶段对应的模式是什么，是否要下推到 TiKV，使用 Hash 还是 Stream 聚合算子等都由优化器根据数据分布、估算的计算代价等来决定。TiDB 并行 Hash Aggregation 的实现如何构建 Hash Aggregation 执行器构建逻辑执行计划 时，会调用 NewAggFuncDesc 将聚合函数的元信息封装为一个 AggFuncDesc。 其中 AggFuncDesc.RetTp 由 AggFuncDesc.typeInfer 根据聚合函数类型及参数类型推导而来；AggFuncDesc.Mode 统一初始化为 CompleteMode。构建物理执行计划时，PhysicalHashAgg 和 PhysicalStreamAgg 的 attach2Task 方法会根据当前 task 的类型尝试进行下推聚合计算，如果 task 类型满足下推的基本要求，比如 copTask，接着会调用 newPartialAggregate 尝试将聚合算子拆成 TiKV 上执行的 Partial 算子和 TiDB 上执行的 Final 算子，其中 AggFuncToPBExpr 函数用来判断某个聚合函数是否可以下推。若聚合函数可以下推，则会在 TiKV 中进行预聚合并返回中间结果，因此需要将 TiDB 层执行的 Final 聚合算子的 AggFuncDesc.Mode 修改为 FinalMode，并将其 AggFuncDesc.Args 修改为 TiKV 预聚合后返回的中间结果，TiKV 层的 Partial 聚合算子的 AggFuncDesc 也需要作出对应的修改，这里不再详述。若聚合函数不可以下推，则 AggFuncDesc.Mode 保持不变。构建 HashAgg 执行器时，首先检查当前 HashAgg 算子是否可以并行执行。目前当且仅当两种情况下 HashAgg 不可以并行执行：存在某个聚合函数参数为 DISTINCT 时。TiDB 暂未实现对 DedupMode 的支持，因此对于含有 DISTINCT 的情况目前仅能单线程执行。系统变量 tidb_hashagg_partial_concurrency 和 tidb_hashagg_final_concurrency 被同时设置为 1 时。这两个系统变量分别用来控制 Hash Aggregation 并行计算时候，TiDB 层聚合计算 partial 和 final 阶段 worker 的并发数。当它们都被设置为 1 时，选择单线程执行。若 HashAgg 算子可以并行执行，使用 AggFuncDesc.Split 根据 AggFuncDesc.Mode 将 TiDB 层的聚合算子的计算拆分为 partial 和 final 两个阶段，并分别生成对应的 AggFuncDesc，设为 partialAggDesc 和 finalAggDesc。若 AggFuncDesc.Mode == CompleteMode，则将 TiDB 层的计算阶段拆分为 Partial1Mode –> FinalMode；若 AggFuncDesc.Mode == FinalMode，则将 TiDB 层的计算阶段拆分为 Partial2Mode –> FinalMode。进一步的，我们可以根据 partialAggDesc 和 finalAggDesc 分别 构造出对应的执行函数。并行 Hash Aggregation 执行过程详述TiDB 的并行 Hash Aggregation 算子执行过程中的主要线程有：Main Thead，Data Fetcher，Partial Worker，和 Final Worker：Main Thread 一个：启动 Input Reader，Partial Workers 及 Final Workers等待 Final Worker 的执行结果并返回Data Fetcher 一个：按 batch 读取子节点数据并分发给 Partial WorkerPartial Worker 多个：读取 Data Fetcher 发送来的数据，并做预聚合将预聚合结果根据 Group 值 shuffle 给对应的 Final WorkerFinal Worker 多个：读取 PartialWorker 发送来的数据，计算最终结果，发送给 Main ThreadHash Aggregation 的执行阶段可分为如下图所示的 5 步：启动 Data Fetcher，Partial Workers 及 Final Workers。这部分工作由 prepare4Parallel 函数完成。该函数会启动一个 Data Fetcher，多个 Partial Worker 以及 多个 Final Worker。Partial Worker 和 Final Worker 的数量可以分别通过 tidb_hashgg_partial_concurrency 和 tidb_hashagg_final_concurrency 系统变量进行控制，这两个系统变量的默认值都为 4。DataFetcher 读取子节点的数据并分发给 Partial Workers。这部分工作由 fetchChildData 函数完成。Partial Workers 预聚合计算，及根据 Group Key shuffle 给对应的 Final Workers。这部分工作由 HashAggPartialWorker.run 函数完成。该函数调用 updatePartialResult 函数对 DataFetcher 发来数据执行 预聚合计算，并将预聚合结果存储到 partialResultMap 中。其中 partialResultMap 的 key 为根据 Group-By 的值 encode 的结果，value 为 PartialResult 类型的数组，数组中的每个元素表示该下标处的聚合函数在对应 Group 中的预聚合结果。shuffleIntermData 函数完成根据 Group 值 shuffle 给对应的 Final Worker。Final Worker 计算最终结果，发送给 Main Thread。这部分工作由 HashAggFinalWorker.run 函数完成。该函数调用 consumeIntermData 函数 接收 PartialWorkers 发送来的预聚合结果，进而 合并 得到最终结果。getFinalResult 函数完成发送最终结果给 Main Thread。Main Thread 接收最终结果并返回。TiDB 并行 Hash Aggregation 的性能提升此处以 TPC-H query-17 为例，测试并行 Hash Aggregation 相较于单线程计算时的性能提升。引入并行 Hash Aggregation 前，它的计算瓶颈在 HashAgg_35。该查询执行计划如下：在 TiDB 中，使用 EXPLAIN ANALYZE 可以获取 SQL 的执行统计信息。因篇幅原因此处仅贴出 TPC-H query-17 部分算子的 EXPLAIN ANALYZE 结果。HashAgg 单线程计算时：查询总执行时间 23 分 24 秒，其中 HashAgg 执行时间约 17 分 9 秒。HashAgg 并行计算时（此时 TiDB 层 Partial 和 Final 阶段的 worker 数量都设置为 16）：总查询时间 8 分 37 秒，其中 HashAgg 执行时间约 1 分 4 秒。并行计算时，Hash Aggregation 的计算速度提升约 16 倍。 ...

摘要算法简介Python的hashlib提供了常见的摘要算法，如MD5，SHA1等等。什么是摘要算法呢？摘要算法又称哈希算法、散列算法。它通过一个函数，把任意长度的数据转换为一个长度固定的数据串（通常用16进制的字符串表示）。举个例子，你写了一篇文章，内容是一个字符串’how to use python hashlib - by Michael’，并附上这篇文章的摘要是'2d73d4f15c0db7f5ecb321b6a65e5d6d’。如果有人篡改了你的文章，并发表为’how to use python hashlib - by Bob’，你可以一下子指出Bob篡改了你的文章，因为根据’how to use python hashlib - by Bob’计算出的摘要不同于原始文章的摘要。可见，摘要算法就是通过摘要函数f()对任意长度的数据data计算出固定长度的摘要digest，目的是为了发现原始数据是否被人篡改过。摘要算法之所以能指出数据是否被篡改过，就是因为摘要函数是一个单向函数，计算f(data)很容易，但通过digest反推data却非常困难。而且，对原始数据做一个bit的修改，都会导致计算出的摘要完全不同。我们以常见的摘要算法MD5为例，计算出一个字符串的MD5值：import hashlibmd5 = hashlib.md5()md5.update(‘how to use md5 in python hashlib?’.encode(“utf8”))print(md5.hexdigest())计算结果如下：d26a53750bc40b38b65a520292f69306如果数据量很大，可以分块多次调用update()，最后计算的结果是一样的：md5 = hashlib.md5()md5.update(‘how to use md5 in ‘.encode(“utf8”))md5.update(‘python hashlib?’.encode(“utf8”))print(md5.hexdigest())试试改动一个字母，看看计算的结果是否完全不同。MD5是最常见的摘要算法，速度很快，生成结果是固定的128 bit字节，通常用一个32位的16进制字符串表示。另一种常见的摘要算法是SHA1，调用SHA1和调用MD5完全类似：import hashlibsha1 = hashlib.sha1()sha1.update(‘how to use sha1 in ‘.encode(“utf8”))sha1.update(‘python hashlib?’.encode(“utf8”))print(sha1.hexdigest())SHA1的结果是160 bit字节，通常用一个40位的16进制字符串表示。比SHA1更安全的算法是SHA256和SHA512，不过越安全的算法越慢，而且摘要长度更长。有没有可能两个不同的数据通过某个摘要算法得到了相同的摘要？完全有可能，因为任何摘要算法都是把无限多的数据集合映射到一个有限的集合中。这种情况称为碰撞，比如Bob试图根据你的摘要反推出一篇文章’how to learn hashlib in python - by Bob’，并且这篇文章的摘要恰好和你的文章完全一致，这种情况也并非不可能出现，但是非常非常困难。摘要算法应用摘要算法能应用到什么地方？举个常用例子：任何允许用户登录的网站都会存储用户登录的用户名和口令。如何存储用户名和口令呢？方法是存到数据库表中：name | password——–+———-michael | 123456bob | abc999alice | alice2008如果以明文保存用户口令，如果数据库泄露，所有用户的口令就落入黑客的手里。此外，网站运维人员是可以访问数据库的，也就是能获取到所有用户的口令。正确的保存口令的方式是不存储用户的明文口令，而是存储用户口令的摘要，比如MD5：username | password———+———————————michael | e10adc3949ba59abbe56e057f20f883ebob | 878ef96e86145580c38c87f0410ad153alice | 99b1c2188db85afee403b1536010c2c9当用户登录时，首先计算用户输入的明文口令的MD5，然后和数据库存储的MD5对比，如果一致，说明口令输入正确，如果不一致，口令肯定错误。练习：根据用户输入的口令，计算出存储在数据库中的MD5口令：def calc_md5(password):pass存储MD5的好处是即使运维人员能访问数据库，也无法获知用户的明文口令。练习：设计一个验证用户登录的函数，根据用户输入的口令是否正确，返回True或False：db = { ‘michael’: ’e10adc3949ba59abbe56e057f20f883e’, ‘bob’: ‘878ef96e86145580c38c87f0410ad153’, ‘alice’: ‘99b1c2188db85afee403b1536010c2c9’}def login(user, password): pass采用MD5存储口令是否就一定安全呢？也不一定。假设你是一个黑客，已经拿到了存储MD5口令的数据库，如何通过MD5反推用户的明文口令呢？暴力破解费事费力，真正的黑客不会这么干。考虑这么个情况，很多用户喜欢用123456，888888，password这些简单的口令，于是，黑客可以事先计算出这些常用口令的MD5值，得到一个反推表：’e10adc3949ba59abbe56e057f20f883e’: ‘123456’‘21218cca77804d2ba1922c33e0151105’: ‘888888’‘5f4dcc3b5aa765d61d8327deb882cf99’: ‘password’这样，无需破解，只需要对比数据库的MD5，黑客就获得了使用常用口令的用户账号。对于用户来讲，当然不要使用过于简单的口令。但是，我们能否在程序设计上对简单口令加强保护呢？由于常用口令的MD5值很容易被计算出来，所以，要确保存储的用户口令不是那些已经被计算出来的常用口令的MD5，这一方法通过对原始口令加一个复杂字符串来实现，俗称“加盐”：def calc_md5(password): return get_md5(password + ’the-Salt’)经过Salt处理的MD5口令，只要Salt不被黑客知道，即使用户输入简单口令，也很难通过MD5反推明文口令。但是如果有两个用户都使用了相同的简单口令比如123456，在数据库中，将存储两条相同的MD5值，这说明这两个用户的口令是一样的。有没有办法让使用相同口令的用户存储不同的MD5呢？如果假定用户无法修改登录名，就可以通过把登录名作为Salt的一部分来计算MD5，从而实现相同口令的用户也存储不同的MD5。练习：根据用户输入的登录名和口令模拟用户注册，计算更安全的MD5：db = {}def register(username, password): db[username] = get_md5(password + username + ’the-Salt’)然后，根据修改后的MD5算法实现用户登录的验证：def login(username, password): pass 小结摘要算法在很多地方都有广泛的应用。要注意摘要算法不是加密算法，不能用于加密（因为无法通过摘要反推明文），只能用于防篡改，但是它的单向计算特性决定了可以在不存储明文口令的情况下验证用户口令。 ...

前言区块链太复杂，那我们就讲点简单的。用JS来构建你自己的区块链系统，寥寥几行代码就可以说明区块链的底层数据结构，POW挖矿思想和交易过程等。当然了，真实的场景远远远比这复杂。本文的目的仅限于让大家初步了解，初步认识区块链。文章内容主要参考视频：使用Javascript建立区块链（https://www.youtube.com/playlist?list=PLzvRQMJ9HDiTqZmbtFisdXFxul5k0F-Q4）感谢原作者，本文在原视频基础上做了修改补充，并加入了个人理解。认识区块链区块链顾名思义是由区块连接而成的链，因此最基本的数据结构是块。每个块都含有时间戳，数据，散列，previousHash等信息。其中数据用来存储数据，previousHash是前一个区块的哈希值示意如下：哈希是对区块信息的摘要存储，哈希的好处是任意长度的信息经过哈希都可以映射成固定长度的字符串，如可用SHA256：calculateHash() { return SHA256(this.previousHash + this.timestamp + JSON.stringify(this.data)).toString();}块的数据结构块的最基本数据结构如下：class Block { constructor(timestamp, data, previousHash = ‘’) { this.timestamp = timestamp; this.data = data; this.previousHash = previousHash; //对hash的计算必须放在最后，保证所有数据赋值正确后再计算 this.hash = this.calculateHash(); } calculateHash() { return SHA256(this.previousHash + this.timestamp + JSON.stringify(this.data)).toString(); }}BlockChain的数据结构多个区块链接而成BlockChain，显然可用用数组或链表来表示，如：class BlockChain { constructor() { this.chain = []; }}创世区块正所谓万物始于一，区块链的第一个区块总是需要人为来手动创建，这个区块的previousHash为空，如：createGenesisBlock() { return new Block(“2018-11-11 00:00:00”, “Genesis block of simple chain”, “”);}区块链的构造方法也应改为：class BlockChain { constructor() { this.chain = [this.createGenesisBlock()]; }}添加区块每新加一个区块，必须保证与原有区块链连接起来，即：class BlockChain { getLatestBlock() { return this.chain[this.chain.length - 1]; } addBlock(newBlock) { //新区块的前一个hash值是现有区块链的最后一个区块的hash值； newBlock.previousHash = this.getLatestBlock().hash; //重新计算新区块的hash值（因为指定了previousHash)； newBlock.hash = newBlock.calculateHash(); //把新区块加入到链中； this.chain.push(newBlock); } …}校验区块链区块链数据结构的核心是保证前后链接，无法篡改，但是如果有人真的篡改了某个区块，我们该如何校验发现呢？最笨也是最自然是想法就是遍历所有情况，逐一校验，如：isChainValid() { //遍历所有区块 for (let i = 1; i < this.chain.length; i++) { const currentBlock = this.chain[i]; const previousBlock = this.chain[i - 1]; //重新计算当前区块的hash值，若发现hash值对不上，说明该区块有数据被篡改，hash值未重新计算 if (currentBlock.hash !== currentBlock.calculateHash()) { console.error(“hash not equal: " + JSON.stringify(currentBlock)); return false; } //判断当前区块的previousHash是否真的等于前一个区块的hash，若不等，说明前一个区块被篡改，虽然hash值被重新计算正确，但是后续区块的hash值并未重新计算，导致整个链断裂 if (currentBlock.previousHash !== previousBlock.calculateHash) { console.error(“previous hash not right: " + JSON.stringify(currentBlock)); return false; } } return true;}跑吧跑起来看看，即：let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(JSON.stringify(simpleChain, null, 4));console.log(“is the chain valid? " + simpleChain.isChainValid());结果如下：ali-186590cc4a7f:simple-chain shanyao$ node main_1.js { “chain”: [ { “timestamp”: “2018-11-11 00:00:00”, “data”: “Genesis block of simple chain”, “previousHash”: “”, “hash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89” }, { “timestamp”: “2018-11-11 00:00:01”, “data”: { “amount”: 10 }, “previousHash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”, “hash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529” }, { “timestamp”: “2018-11-11 00:00:02”, “data”: { “amount”: 20 }, “previousHash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”, “hash”: “274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34” } ]}is the chain valid? true注意看其中的previousHash与哈希，确实是当前区块的previousHash指向前一个区块的哈希值。篡改下试试都说区块链不可篡改，是真的吗让我们篡改第2个区块试试，如？let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(“is the chain valid? " + simpleChain.isChainValid());//将第2个区块的数据，由10改为15simpleChain.chain[1].data = {amount: 15};console.log(“is the chain still valid? " + simpleChain.isChainValid());console.log(JSON.stringify(simpleChain, null, 4));结果如下：ali-186590cc4a7f:simple-chain shanyao$ node main_1.js is the chain valid? truehash not equal: {“timestamp”:“2018-11-11 00:00:01”,“data”:{“amount”:15},“previousHash”:“fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”,“hash”:“150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”}is the chain still valid? false{ “chain”: [ { “timestamp”: “2018-11-11 00:00:00”, “data”: “Genesis block of simple chain”, “previousHash”: “”, “hash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89” }, { “timestamp”: “2018-11-11 00:00:01”, “data”: { “amount”: 15 }, “previousHash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”, “hash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529” }, { “timestamp”: “2018-11-11 00:00:02”, “data”: { “amount”: 20 }, “previousHash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”, “hash”: “274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34” } ]}显然，篡改了数据之后，哈希值并未重新计算，导致该区块的哈希值对不上。再篡改下试试那么，如果我们聪明点，篡改后把哈希值也重新计算会如何？let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(“is the chain valid? " + simpleChain.isChainValid());//篡改后重新计算hash值simpleChain.chain[1].data = {amount: 15};simpleChain.chain[1].hash = simpleChain.chain[1].calculateHash();console.log(“is the chain still valid? " + simpleChain.isChainValid());console.log(JSON.stringify(simpleChain, null, 4));结果如下：ali-186590cc4a7f:simple-chain shanyao$ node main_1.js is the chain valid? trueprevious hash not right: {“timestamp”:“2018-11-11 00:00:02”,“data”:{“amount”:20},“previousHash”:“150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”,“hash”:“274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34”}is the chain still valid? false{ “chain”: [ { “timestamp”: “2018-11-11 00:00:00”, “data”: “Genesis block of simple chain”, “previousHash”: “”, “hash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89” }, { “timestamp”: “2018-11-11 00:00:01”, “data”: { “amount”: 15 }, “previousHash”: “fd56967ff621a4090ff71ce88fdd456547d1c92d2e93766b7e8791f7a5f91f89”, “hash”: “74d139274fb692495b7c805dd5822faa0c5b5e6058b6beef96e87e18ab83a6b1” }, { “timestamp”: “2018-11-11 00:00:02”, “data”: { “amount”: 20 }, “previousHash”: “150b196268a0152e9f0e719ac131a722472a809f49bd507965029a78c7400529”, “hash”: “274a7a13ed20118e8cb745654934a7e24a4d59333ba17dfbf5d4cfe0fa8a6e34” } ]}显然，第3个区块的previousHash并未指向第2个区块的哈希值。是真的无法篡改吗其实并不是，如果我们再聪明一点，把后续区块的哈希值也重新计算一下，不就OK了吗？确实如此，如：let simpleChain = new BlockChain();simpleChain.addBlock(new Block(“2018-11-11 00:00:01”, {amount: 10}));simpleChain.addBlock(new Block(“2018-11-11 00:00:02”, {amount: 20}));console.log(“is the chain valid? " + simpleChain.isChainValid());//篡改第2个区块simpleChain.chain[1].data = {amount: 15};simpleChain.chain[1].hash = simpleChain.chain[1].calculateHash();//并把第3个区块也重新计算simpleChain.chain[2].previousHash = simpleChain.chain[1].hash;simpleChain.chain[2].hash = simpleChain.chain[2].calculateHash();console.log(“is the chain still valid? " + simpleChain.isChainValid());console.log(JSON.stringify(simpleChain, null, 4本文作者：扁鹊他大哥阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...

接口定义type Hash interface { // 嵌入了 io.Writer 接口 // 向执行中的 hash 加入更多数据 // hash 函数的 Write 方法永远不会返回 error io.Writer // 把当前 hash 追加到 b 的后面 // 不会改变当前 hash 状态 Sum(b []byte) []byte // 重置 hash 到初始化状态 Reset() // 返回 hash 结果返回的字节数 Size() int // BlockSize 返回 hash 的基础块大小 // 为了提高效率 // Write 方法传入的字节数最好是 blick size 的倍数 BlockSize() int}// 结果为 32bit hash 函数接口type Hash32 interface { Hash Sum32() uint32}// 结果为 64bit hash 函数接口type Hash64 interface { Hash Sum64() uint64}Go 的 hash 包里有几种 hash 算法实现，分别是 adler32，crc32/64，fnv。fnvfnv 是一种简单可靠的 hash 算法。它的结果长度有多种，fnv.go 中也提供了多种长度的算法实现。fnv 核心算法很简单：先初始化 hash，然后循环 乘以素数 prime32，再与每位 byte 进行异或运算。const offset32 = 2166136261const prime32 = 16777619type sum32 uint32func (s *sum32) Reset() { *s = offset32 }func (s *sum32) Size() int { return 4 }func (s *sum32) BlockSize() int { return 1 }func (s *sum32) Write(data []byte) (int, error) { hash := *s for _, c := range data { hash *= prime32 hash ^= sum32(c) } *s = hash return len(data), nil}func (s *sum32) Sum32() uint32 { return uint32(*s) }adler - 可靠、快速的 hash 算法Adler-32通过求解两个16位的数值A、B实现，并将结果连结成一个32位整数.A就是字符串中每个字节的和，而B是A在相加时每一步的阶段值之和。在Adler-32开始运行时，A初始化为1，B初始化为0，最后的校验和要模上65521(小于2的16次方的最小素数)。type digest uint32func (d *digest) Reset() { *d = 1 }func (d *digest) Write(p []byte) (nn int, err error) { *d = update(*d, p) return len(p), nil}const ( // 比 65536 小的最大素数 mod = 65521 // nmax is the largest n such that // 255 * n * (n+1) / 2 + (n+1) * (mod-1) <= 2^32-1. // It is mentioned in RFC 1950 (search for “5552”). nmax = 5552)// Add p to the running checksum d.func update(d digest, p []byte) digest { s1, s2 := uint32(d&0xffff), uint32(d>>16) for len(p) > 0 { var q []byte // 每次处理数据量为 nmax // 处理完之后再 % mod // 防止溢出，且尽可能少的执行 mod 运算 if len(p) > nmax { p, q = p[:nmax], p[nmax:] } // 底下这两个循环我不明白为啥不合成一个？？？ // 有明白的可以告知一声 for len(p) >= 4 { s1 += uint32(p[0]) s2 += s1 s1 += uint32(p[1]) s2 += s1 s1 += uint32(p[2]) s2 += s1 s1 += uint32(p[3]) s2 += s1 p = p[4:] } for _, x := range p { s1 += uint32(x) s2 += s1 } s1 %= mod s2 %= mod p = q } // 把 s2 s1 再合成一个 uint32 return digest(s2<<16 | s1)}crc32CRC为校验和的一种，是两个字节数据流采用二进制除法（没有进位，使用XOR来代替减法）相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示；除数是一个长度为 n + 1 的预定义（短）的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上 n 个 0。对于 crc32 来说，IEEE 标准下的除数是 0xedb88320。除法运算效率比较低，所以生产环境一般使用的是查表法。（这块儿都是数学推导，没找到资料，也没看懂。）以上是 hash 包中提供的几种 hash 算法。除此之外，crypto 包里提供了一些其他的算法也实现了 hash 接口，比如 md5，sha1，sha256等。md5（消息摘要算法，经常有同学把 md5 错当成加密算法）是一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值。md5已被证实无法防止碰撞，已经不算是很安全的算法了，因此不适用于安全性认证，如SSL公开密钥认证或是数字签名等用途。对于需要高度安全性的数据，一般建议改用其他算法，比如 sha256。素数hash 算法中常用中间值对一个素数取模作为 hash 值，这是为什么呢？一个好的散列函数要尽可能减少冲突。如果对合数取模，那么所有该函数的因子的倍数冲突的概率会增大，而质数的因子只有1和它本身，所以对于特定倍数的数字来说，会有更好的散列效果。比如：假设 mod 是 6，对于 2 的倍数 2、4、6、8、10、12 的 hash 值是 2、4、0、2、4、0，对于 3 的倍数 3、6、9、12 的 hash 值是 3、0、3、0。假设 mod 是 7，对于 2、4、6、8、10、12 的 hash 值是 2、4、6、1、3、5，对于 3 的倍数 3、6、9、12 的 hash 值是 3、6、2、5。可以看出，如果 mod 是质数的话会得到更好的散列效果。 ...