HASH GAME - Online Skill Game GET 300

　　Hash1．基本概念哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表。这种方法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H（k），H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H（k）的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H（k），从而达到按关键字直接存取元素的目的。2. 常用的构造散列函数的方法散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。散列表的常用构造方法有：（1）直接定址法：取关键字或关键字的某个线性函数值为散列地址。即H（key）=key或H（key） = a*key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H（key）中已经有值了，就往下一个找，直到H（key）中没有值了，就放进去。（2）数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。（3）平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。（4）折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加（5）随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。（6）除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H（key） = keyMOD p，p=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。3．处理冲突的方法当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即k1≠k2，但H（k1）=H（k2），这种现象称为冲突，此时称k1和k2为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。以下是集中常见的冲突检测方法：（1）开放寻址法：这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=（H（key）+di）% mi=1，2，…，n其中H（key）为哈希函数，m为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：线二次探测再散列：di=12，-12，22，-22，…，k2，-k2（ k=m/2 ）随机探测再散列：di=伪随机数序列线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。（2）再哈希法：这种方法是同时构造多个不同的哈希函数：Hi=RHi（key）i=1，2，…，k当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。（3）链地址法（拉链法）：这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。拉链法的优点与开放定址法相比，拉链法有如下几个优点：1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；3）开放定址法为减少冲突，要求装填因子α（装填因子=表中的记录数/哈希表的长度）较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元（即开放地址）都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。拉链法的缺点拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。（4）建立一个公共溢出区：这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。假设哈希函数的值域为[0，m-1]，则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。4. 散列表查找性能分析散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：（1）散列函数是否均匀；（2）处理冲突的方法；（3）散列表的装填因子。散列表的装填因子定义为：α= 填入表中的元素个数/散列表的长度。α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。5. Linux内核哈希应用Linux内核源码具有简洁、高效和高复用性的特点，无论是Linux的链表应用还是hash表的应用中都能很好的体现。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。例如常规链表与内核链表的区别：Struct list_node {int num;Char name[10];Struct innode_list *next;Struct innode_list *prev;}Struct list_head {Struct list_head *next, *prev;}Struct list_node {int num;Char name[10];Struct list_head list;}从上面的比较可见一斑，值得一提的是Linux对hash的应用也一改常态，下面即Linux hash的简单介绍。源码在include/linux/list.h中，数据结构定义放在了include/linux/types.h中。Hash最重要的是选择适当的Hash函数，从而平均的分配关键字在桶中的位置，从而优化查找插入和删除所用的时间。然而任何Hash函数都会出现冲突问题。内核采用的解决哈希冲突的方法是：拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针（struct hlist_head name）组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α（装填的元素个数/数组长度）可以大于 1，但一般均取α≤1。当然，用拉链法解决hash冲突也是有缺点的，指针需要额外的空间。Linux 中的hlist（哈希表）和list是不相同的，在list中每个结点都是一样的，不管头结点还是其它结点，使用同一个结构体表示，但是在hlist中，头结点使用的是struct hlist_head来表示的，而对于其它结点使用的是strcuct hlist_node这个数据结果来表示的。还有list是双向循环链表，而hlist不是双向循环链表。因为hlist头结点中没有prev变量。Linux hlist表头及节点定义：struct hlist_head{struct hlist_node *first;}struct hlist_node {struct hlist_node *next,**pprev;}Linuxhlist的部分接口介绍函数原型功能说明参数说明返回值说明static iniline void INIT_HLIST_NODE(struct hlist_node *h)哈希表结点初始化h:为哈希表结点static inline int hlist_empty(const struct hlist_head *h)判断哈希链表是否为空h:指向哈希链表的头结点1：空0：非空static inline int hlist_unhashed(const struct hlist_node *h)判断结点是否已经存在hash表中h:指向哈希链表的结点1：空0：非空static inline void hlist_del(struct hlist_node *n)将一个结点从哈希链表中