散列、散列函数、冲突处理_某散列表长度为100,散列函数

1、散列：理想的散列表数据结构只不过是一个包含有关键字的具有固定大小的数组。典型情况下，一个关键字就是带有相关值的字符串。

2、散列的基本思想：以关键字key为自变量，通过一个确定的函数 h（散列函数），计算出对应的函数值h(key)，作为数据对象的存储地址。

3、冲突：可能不同的关键字会映射到同一个散列地址上， 即h(keyi) = h(keyj)（当keyi ≠keyj），称为“冲突(Collision)”。

4、散列函数：是一个将关键字和散列地址对应的函数。
！！！散列函数一般要考虑的两个因素：（1）、计算简单以便提高转换速度。（2）、关键词对应的地址分布均匀，尽量减少冲突。

5、关键词有数字关键词和字符关键词，数字关键词的散列函数构造：
（1）、直接地址法：取关键词的某个线性函数值为散列的地址。
即：f(key) = a × key + b

！！！例：如果我们现在要统计的是80后出生年份的人口数，那么我们对出生年份这个关键字可以用年份减去1980来作为地址。
此时f (key) = key-1980。

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合査找表较小且连续的情况。由于这样的限制，在现实应用中，直接定址法虽然简单，但却并不常用。

（2）、数字分析法：分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址
比如：取11位手机号码key的后4位作为地址：散列函数为：h(key) = atoi(key+7)

（3）、折叠法：
把关键词分割成位数相同的几个部分，然后叠加

如： 56793542
542
793
+ 056
———
1391
h(56793542) = 391
折叠法的目的是使数字关键词中的每一个数字都对结果有影响，使结果更加随机，以至于地址分布更加均匀。

（4）、平方取中法

如： 56793542
56793542
x 56793542
—————————
3225506412905764
h(56793542) = 641
取中间的四位
平方取中法的目的：根折叠法是一样的，都是让结果受更多位数的影响。

（5）、除留余数法：此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为：f( key ) = key mod p ( p ≤ m )。
mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

例：

不过这也是存在冲突的可能的，因为12 = 2×6 = 3×4。如果关键字中有像18(3×6)、30(5×6)、42(7×6)等数字，它们的余数都为6，这就和78所对应的下标位置冲突了。

！！！如何合理选取p值
使用除留余数法的一个经验是，若散列表表长为m，通常p为小于或等于表长（最好接近m)的最大质数或不包含小于20质因子的合数。

这句话怎么理解呢？
我再举个例子：某散列表的长度为100，散列函数H(k)=k%P,则P通常情况下最好选择哪个呢？A、91 B、93 C、97 D、99
实践证明，当P取小于哈希表长的最大质数时，产生的哈希函数较好。我选97，因为它是离长度值最近的最大质数。

6、字符关键词的散列函数构造
（1）、一个简单的散列函数：ASCII码加和法
对字符型关键词key定义散列函数如下：
h(key) = (Σkey[i]) mod TableSize

typedef unsigned int Index;
Index hash(const char *key,int size)
{
    unsigned int hashval;
    while(*key != '\0')
    {
        hashval += *key++;
    }
    return hashval % size;
}
1
2
3
4
5
6
7
8
9
10

冲突严重：a3、b2、c1；eat、 tea；

（2）、简单的改进——前3个字符移位法
h(key)=(key[0]*27*27 + key[1]*27 + key[2])mod TableSize

typedef unsigned int Index;
Index hash(const char *key,int size)
{

    return  (key[0]*27*27+key[1]*27+key[2]) % size;
}
1
2
3
4
5
6

仍然冲突：string、 street、strong、structure等等；
空间浪费：3000/263 ≈ 30%

（3）、好的散列函数——移位法
涉及关键词所有n个字符，并且分布得很好：
h(key) = (求和 key[n-i-1] *32^i )mod TableSize
例如：h(“abcde”)=‘a’*324+’b’*323+’c’*322+’d’*32+’e’
这种计算方法乘法次数太多，速度慢，提高速度的方法：

Index Hash ( const char *Key, int TableSize )
{
 unsigned int h = 0; /* 散列函数值，初始化为0 */
 while ( *Key != ‘\0’) /* 位移映射 */
 h = ( h << 5 ) + *Key++;
 return h % TableSize;
}
1
2
3
4
5
6
7

这个跟上面公式是一样的，但是乘法次数明显少很多，计算速度更快。

7、解决冲突的方法：
（1）、开放地址法：一旦产生了冲突（该地址已有其它元素），就按某 种规则去寻找另一空地址。

 若发生了第 i 次冲突，试探的下一个地址将增加di，基本公式是：
hi(key) = (h(key)+di) mod TableSize ( 1≤ i < TableSize )

！！！di 决定了不同的解决冲突方案：线性探测（di = i）、平方探测（di = i*i）、双散列（di = i*h2(key)）。

例：我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。 我们用散列函数f(key) = key mod l2。
当计算前S个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入：
计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置。
接下来22,29,15,47都没有冲突，正常的存入。
到了 key=48，我们计算得到f(48) = 0，与12所在的0位置冲突了，我们f(48) = (f(48)+1) mod 12 = 1，此时又与25所在的位置冲突。于是f(48) = (f(48)+2) mod 12=2，还是冲突……一直到 f(48) = (f(48)+6) mod 12 = 6时，才有空位，赶快存入。存入完的结果：

从这个例子我们也看到，我们在解决冲突的时候，还会碰到如48和37这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是査找效率都会大大降低。
（2）、分离链接法：将所有关键字为同义词的记录存储在一个单链中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

对于关键字集合{12,67,56,16,25,37, 22,29,15,47,48,34}，我们用前面同样的12为除数，进行除留余数法：

此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。很不错的解决思路。

分离拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。

拉链法的优势与缺点

与开放定址法相比，拉链法有如下几个优点：
（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
（2）、由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
（3）、开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
（4）、在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元（即开放地址）都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

拉链法的缺点：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。