我没啥优点，除了爱收集资料，总觉得有一天我会用的。
推荐博客：matrix67,基本原创 必备：从头到尾彻底解析Hash表算法 文本相似度计算-JaccardSimilarity和哈希签名函数
Hash
Hash基本概念
哈希表（Hash table，也叫散列表），是根据key而直接进行访问的数据结构。也就是说，它通过把key映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 哈希表的做法其实很简单，就是把key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。 而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码，这些编码值叫做HASH值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。 数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：
元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的： 1，除法散列法 最直观的一种，上图使用的就是这种散列法，公式： index = value % 16 2，平方散列法 求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式： index = (value * value) » 28 （右移，除以2^28。记法：左移变大，是乘。右移变小，是除。） 如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。 3，斐波那契（Fibonacci）散列法 平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。 （1），对于16位整数而言，这个乘数是40503。 （2），对于32位整数而言，这个乘数是2654435769。 （3），对于64位整数而言，这个乘数是11400714819323198485。 这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列 ### 拓展
- 堆排序
参看：白话经典算法系列之七-堆与堆排序: 注意博主代码有错误！
- 排序
白话经典算法系列之一 冒泡排序的三种实现 白话经典算法系列之二 直接插入排序的三种实现 白话经典算法系列之三 希尔排序的实现 白话经典算法系列之四 直接选择排序及交换二个数据的正确实现 白话经典算法系列之五 归并排序的实现 白话经典算法系列之六 快速排序 快速搞定 白话经典算法系列之七 堆与堆排序 话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇
衡量文本相似度的几种手段：
参看：基于余弦定理的相似度计算 （1）最长公共子串（基于词条空间） （2）最长公共子序列（基于权值空间、词条空间） （3）最少编辑距离法（基于词条空间） （4）汉明距离（基于权值空间） （5）余弦值（基于权值空间）
文本相似度计算-JaccardSimilarity和哈希签名函数
应用于： - 过滤相似度很高的新闻，或者网页去重 - 考试防作弊系统 - 论文抄袭检查 方法： 衡量文本相似度计算的方法很多，主要来说有两种，一是余弦定律，二是JaccardSimilarity方法。
k-shingle算法——统计文本中词语
简单的说，该算法就是从头挨个扫描文本，然后依次把k个字符保存起来，比如有个文本，内容是abcdefg,k设为2，那得到的词语就是ab,bc,cd,de,ef,fg。
将词汇进行hash
使用特征矩阵描述相似度
计算hash签名矩阵
jaccardSim
JaccardSimilarity说起来非常简单，容易实现，实际上就是两个集合的交集除以两个集合的并集，所得的就是两个集合的相似度。 数学表达式是： `|S ∩ T|/|S ∪ T|`
基本的计算方法就是如此，而两个集合分别表示的是两个文本，集合中的元素实际上就是文本中出现的词语啦，我们需要做的就是把两个文本中的词语统计出来，然后按照上面的公式算一下就行了。