(4)平方取中法
如果关键字中的各位的分布都比较均匀，但关键字的值域比数组的规模大，则可以将关键字平方后，取其结果中间各位作为散列函数值。
由于中间各位和每一位数字有关系，因此均匀分布的可能性较大。
例如：4731 X 4731 = 22 382 361.中间选取几位，依赖于散列表的单元总数。若散列表中有100个单位，选取中间4,5两位，即关键字
4731的地址为82.
(5)折叠法如果关键字相当长，以至于和散列表的单元总数相比大的多，则采取折叠法。如果数字的分布大体上是均匀的，通常选取一个长度后，将关键字按长度分组相加。例如：542 242 241，折叠后542 + 242 + 241 = 1025，抛弃进位，得到散列表的结果为25.
不存在一种万能的散列函数，在任何情况下都是出色的。但是大部分情况下，保留余数法比较好。
实际中选取散列函数需要考虑的因素有：
计算散函数所需时间。
关键字长度。
散列表长度（散列表地址范围）。
关键字分布情况。
记录的查找频率。
3.碰撞的解决在选取散列函数时，由于很难选取一个既均匀分布又简单，同时保证关键字和散列地址一一对应的散列表，所以冲突时不可避免的。如果具有不同关键字的 k 个数据元素的散列地址完全相同，就必须为 k-1个数据元素重新分配存储单元。通常称其为“溢出”的数据元素。
常用的处理冲突的方法有两种：
(1)将溢出的数据元素存放到散列表中没有使用的单元中。
这种方法是“封闭”的，不需要使用额外的存储单元，称为“闭散列表”。具体的实施方案有：线性探针法、二次探测发、再散列法。
线性探针法：在数组中从映射到的位置开始顺序查找空位置，如果需要，从最后一个位置绕回第一个位置。这种方法碰撞可能引起连锁反应，使表中形成一些较长的连续被占用的单元，如：从1---10的地址全部被使用。从而使散列表的性能降低。
二次探测发：不直接检查下一个单元，而是检查远离初始探测点的某一单元，以消除线性探测法中的初始聚集的问题.
再散列法：有两个散列函数H1和H2。H1用来计算探测序列的起始地址，H2用来计算下一个位置的步长。第二个散列函数必须仔细选择。例如，它永远不能计算出0，必须保证所有单元能够探测到。
(2)将映射到同一地址的数据元素分别保存到散列表以外的各自线性表中。
由于地址相同的数据元素个数变化比较大，因此通常采用链表的方式。散列表本身只保存一个指向各自链表中第一个节点的指针。这种方法称为“开散列表"，或拉链法，可以理解为“链表的数组”。
开散列表将具有同一散列地址的数据元素都存储在一个单链表中。在散列表中插入、查找或删除一个元素，就是在对应的单链表中进行的。为了方便操作，将单链表设计为带头结点的单链表。
例如；一个规模为11的开散列表中依次插入关键字17、21、23、60、29、38......,散列函数为
H（Key）= key mod 11，散列表如下：
在开散列表中，插入、删除和查找操作的实现都相当简单。
插入x时，首先计算H(x),将x插入到H(x)指向的单链表的表头。
查找时，也是先计算H(x),然后顺序查找H(x)指向的单链表。
删除操作同样简单，先计算H(x)，然后顺序查找H(x)指向的单链表，
找到x后删除
2018-01-05