哈希算法,SHA256,哈希函数,加密哈希,哈希预测/哈希算法是博彩游戏公平性的核心，本文详细解析 SHA256 哈希函数的运作原理，并提供如何通过哈希技术进行博彩预测的方法！

　　假设某大学有10000名同学，每个人的学号是由学院-年级-班级-序号组成，例如学号为16140113表示是16系，14级1班的13号。为了快速查找到13号的成绩信息，可以建立一张表，但是不能用学号作为下标，学号的数值实在太大。因此将学号除以1100100取余，即得到编号作为该表的下标，那么，要查找学号为16140113的成绩的时候，只要直接访问表下标为13的数据即可。这就能够在O(1)时间复杂度内完成成绩查找。实际上这里就用到了散列的思想。

　　理想散列表（哈希表）是一个包含关键字的具有固定大小的数组，它能够以常数时间执行插入，删除和查找操作。

　　每个关键字被映射到0到数组大小N-1范围，并且放到合适的位置，这个映射规则就叫散列函数/哈希(hash)函数。

　　理想情况下，两个不同的关键字映射到不同的单元，然而由于数组单元有限，关键字范围可能远超数组单元，因此就会出现两个关键字散列到同一个值得时候，这就是散列冲突。

　　注：那些元素间任何排序信息的操作将不会得到有效的支持，因此，诸如FindMin、FindMax以及线性时间将排过序的整个表进行打印的操作都是散列所不支持的。

　　如果数据是固定不变的，那么静态哈希较为实用。由于这些键固定不变，而且可以提前为静态哈希算法所获知，因此目录中的主要页面数量也会保持稳定。

　　动态哈希表通常是在发生冲突后slot数量翻倍增长，而增长后毕竟哈希函数也变了，所以还要把旧slot里的元素重新放置。这种简单的动态哈希(dynamic hash)算法便是SGI版的STL中hash_map的实现。

　　如果数据不固定，那么静态哈希的性能就比较低。这种类型的数据适合采用动态哈希技术来处理。

　　假设有一个大小为7的表，现在，要将13，18，19，50，20散列到表中。主要操作步骤：

　　计算20 % 7得到6，因此将20放到下标为6的位置，但是此时6的位置已经被占用了，因此就产生了散列冲突。

　　将数据散列之后，如何从表中查找呢？例如，查找数值为50的数据位置，只需要计算50 % 7，得到下标1，访问下标1的位置即可。但是如果考虑散列冲突，就没有那么简单了。

　　我们可以取关键字的某个线性函数值为散列地址，即f(key)=a*key+b（通过关键字的加减乘除等运算计算地址）。

　　这种方法简单均匀，但是我们需要事先知道关键字的分布情况，适合查找表比较小且连续的情况，比如按照年月日进行计算。

　　数字分析法通常适合处理关键字位数比较大的情况，例如我们现在要存储某家公司员工登记表，如用手机号作为关键字，那么我们发现抽样后面的四位数字作为散列地址是不错的选择。

　　折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长后几位作为散列地址。

　　除留余数法为最常用的构造散列函数方法，对于散列表长为m的散列函数计算公式为：

　　这里的random是随机函数，当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

　　分离链接法/链地址法的做法是将同一个值的关键字（即哈希结果相同）保存在同一个单链表中。这种方法的特点是需要另外分配新的单元来存储散列到同一个位置的数据。例如，对于前面：

　　如果再要插入元素20，则在下标为6的位置存储表头，而表的内容是13和20。

　　若选定的哈希表长度为m，则可将哈希表定义为一个长度为m的指针数组t[0…m-1]，指针数组中的每个指针指向哈希函数结果相同的单链表。

　　插入值：将元素value插入哈希表，若元素value的哈希函数值为hash_key，将value对应的节点的头插法的方式插入到以t[hash_key]为头指针的单链表中（采用头插法插入每次都是插入到头指针的next，这样不需要遍历链表，也不需要设置尾指针NULL，插入复杂度为O(1)）。

　　查找值：若元素value的哈希函数值为hash_key，遍历以t[hash_key]为头指针的单链表，查找链表各个节点的值域是否为value、

　　查找的时候，除了根据计算出来的散列值找到对应位置外，还需要在链表上进行搜索。而在单链表上的查找速度是很慢的。另外散列函数如果设计得好，冲突的概率其实也会很小。

　　分离链接散列算法的缺点是需要指针，由于给新单元分配地址需要时间，因此这就导致算法的速度多少有些减慢，同时算法实际上还需要对另一种数据结构的实现。除了使用链表解决冲突外，开放定址散列法是另外一种用链表解决冲突的方法。在开放定址散列算法系统中，如果有冲突发生，那么就要尝试选择另外的单元，直到找出空的单元为止。因为所有的数据都要置入表内，所以开放定址散列法所需要的表要比分离链接散列算法用表大。一般来说，对于开放定址散列算法来说，装填因子应该低于λ=0.5。

　　开放定址法的思想是，如果冲突发生，就选择另外一个可用/空的位置。只要散列表足够大，空的/可用的散列地址总能找到，并将记录存入。

　　如果此时再要插入20，则20 % 7 = 6，但是6的位置已有元素，因此探测下一个位置（6+1）%7，在这里就是下标为0的位置。因此20的存储位置如下：

　　但这种方式的一个问题是，可能造成一次聚集，因为一旦冲突发生，为了处理冲突就会占用下一个位置，而如果冲突较多时，就会出现数据都聚集在一块区域。这样就会导致任何关键字都需要多次尝试才可能解决冲突。

　　顾名思义，如果说前面的探测函数是f(i)= i % 7，那么平方探测法就是f(i)= (i^2 )% 7。

　　为了避免聚集，在探测时选择跳跃式的探测，即再使用一个散列函数，用来计算探测的位置。

　　在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法，公式：

　　散列表可以认为是具有固定大小的数组，那么如果插入新的数据时散列表已满，或者散列表所剩容量不多该怎么办？这个时候就需要再散列，常见做法是，建立一个是原来两倍大小的散列表，将原来表中的关键字重新散列到新表中。

　　实际应用中真正构造哈希表的还是拉链法，其余方法在冲突和平均复杂度方面不具备优势。

　　分离链接法（separatechaining）是目前工程实践中最好的一种方式。

　　散列表应用很广泛。例如做文件校验或数字签名。当然还有快速查询功能的实现。例如，redis中的字典结构就使用了散列表，使用MurmurHash算法来计算字符串的hash值，并采用拉链法处理冲突，，当散列表的装载因子（关键字个数与散列表大小的比）接近某个大小时，进行再散列。

　　哈希查找，由于哈希算法能够很好的把数据做比较均匀的分布，所以哈希查找的速度要比B+ Tree查找的速度要快。哈希查找的时间复杂度是O(1)，而B+ Tree的时间复杂度是O(h)。当然，B+ Tree的优势是在范围查找，不然也不会成为关系型数据库的基本算法了。

　　SQL Server在做联接(JOIN)的时候，如果两个表都不是很小，而且没有在关联列上排序，就很可能使用哈希联接。哈希联接使用的就是哈希查找，它的性能并不差，但是要注意的一点是，哈希联接需要先构造一个哈希表，而哈希表需要消耗不小的内存空间，如果数据库服务器的内存不足的话，SQL Server就只好使用“优雅的哈希联接”(Grace HASH JOIN)或者递归哈希联接(Recursive Hash Join)，这样性能就会受到影响了。在设计数据库的时候，我们应该注意建立/更新适当的索引和统计信息(STATISTICS)，以便SQL Server可以准确的估计联接的输入大小，以便选择正确的算法。

　　哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。当链表长度超过8时，链表转换为红黑树。

　　HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

　　图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

　　从HashMap的底层结构中我们可以看到，HashMap采用是数组+链表/红黑树的组合来作为底层结构，也就是开放地址法+链地址法的方式来实现HashMap。