哈希表(HashTable)

1. 哈希表综述：
哈希表(Hash Table)也叫散列表，是根据关键码值直接访问
就是一个把关键码映射到表中的一个位置来访问记录的过程
这个映射函数叫做哈希函数，用hash()表示，存放记录的数组叫做哈希表(一个数组)
哈希表是一种高效的数据结构，主要体现在数据的查找上，几乎可以看成常数时间
例如：对于排序算法，最低时间复杂度为O(nlogn),但是对于一些特殊情况可以更快，现有N个整数(N>10000)范围为0-10000，如何排序？
建立一个数组int num[10000],初始化为0，num[i]表示有多少个数等于i
这样每读入一个数x，num[x]++，最后num[0]-num[10000]依次取出这些数，复杂度为O(n)，
这个思想就是hash：将每个对象对应道一个关键值，然后按关键值归类

2. 哈希表的冲突
处理哈希冲突的方法有：开散列和闭散列
1、开散列：也叫拉链法
通俗的说，就是既然元素a和元素b都该放在里面只好挤一挤了，即每个位置存放所有该存放在里面的元素。但是怎么把很多元素放在一个位置呢？只要在位置上放一个链表表头就可以了，该链表里包含所有放在该位置的元素，在实际应用中，往往不把链表做成传统的使用动态内存的结构，而是自己维护一个大数组，给链表元素分配数组下标，这样又方便又节省时间空间
2、闭散列法：也叫开放地址法：
通俗的讲，就是，既然a可以霸占b的位置，b也可以霸占c的位置，不严格按照关键值的hash码来选择位置，而是在位置被占用时按照某种方法另选一个位置，哈希表是将某个对象对应道一个关键值上，可是，不同的对象可能对应道一个相同的关键值，这就叫做哈希冲突。哈希表的大小一般选取p(p为小于表长的最大素数)，如果出现两个不同的数对应到同一关键值，例如0和p
注意：可以降哈希表的每一个位置做成一个链表，插入到链表即可，这叫开放散列法
重要：进行哈希查找的时候，先找到每个对象对应的关键值，如果这个关键值有多个对象对应，然后，在沿着这个关键值的链表依次查找对象

3. 哈希表的插入和查找
哈希表的插入和查找几乎是一样的即：
1、计算哈希函数值，得到对应位置 hash(k)
2、从hash(k)开始，使用(如果需要)冲突解决策略定位包含关键字K的记录
3、如果需要插入，把数据插入即可
如果冲突可以忽略不计，两种操作的时间复杂度为O(1)

哈希函数的选取
怎样选取好的hash函数才可以使计算不过雨复杂，冲突又比较小呢？对于这个问题，只有一些经验上的解决方式
对于数值
1、直接取余数(一般选取M作为除数，M最好是个质数)
2、平法取中，即计算关键字平方，再取中间r位形成一个大小为2^r的表
分析：方法1容易产生分布不均匀的情况
方法2好得多，因为几乎所有位都对结果产生了影响，使得计算量大，一般也很少使用
对于字符串
1、折叠法：把所有字符的ACSII码加起来
2、采用ELFHash()函数(它用于Unix的可执行链接格式，ELF中)
ELFHash()函数是一个很有用的Hash函数。对长短字符串都有效

unsigned int ELFHash(char *str)  
{
    unsigned int hash = 0;  
    unsigned int x = 0;  

    while (*str)  
    {
        //hash左移4位，把当前字符ASCII存入hash低四位
        hash = (hash << 4) + (*str++); 
        if ((x = hash & 0xF0000000L) != 0)  
        {
            //如果最高的四位不为0，则说明字符多余7个，现在正在存第7个字符
            //如果不处理，再加下一个字符时，第一个字符会被移出，因此要有如下处理。  
            //该处理，如果最高位为0，就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位  
            //因为1-4位刚刚存储了新加入到字符，所以不能>>28  
            hash ^= (x >> 24);  
            //上面这行代码并不会对X有影响，本身X和hash的高4位相同，下面这行代码&~即对28-31(高4位)位清零。  
            hash &= ~x;  
        }  
    }  
    //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)  
    return (hash & 0x7FFFFFFF);  
} 

4. 哈希表应用：
题意概述：
输入几组对应的字符串，其中一个是English，另一个是Foreign Language，开始输入“字典”，然后根据Foreign Language查询字典，如果没有输出eh

C++ Code：

#include <iostream>
#include <cstring>

#define MOD 10003       //槽数，最好是素数 
using namespace std;

//定义哈希表的每个节点
struct node
{
    int pos;    //存储每个字符串在自己数组中的位置
    struct node* next; 
};
node* hash[MOD] = {NULL};
//定义字符串
char word[10000][11];
//定义对应字符串所属字符串
char belong[10000][11]; 

//Unix系统字符串ELFHash散列函数 
int ELFHash(char* key)
{
    unsigned long h = 0, g;
    int i=0;
    while (key[i])
    {
        h = h<<4 + key[i]++;
        g = h & 0XF0000000L;
        if (g)
        {
            h ^= g >> 24;
        }
        h &= ~g;
    }
    return h%MOD;
}

int main()
{
    int index = 0;
    int hashkey = 0;
    node* p = NULL;
    //创建字典,str里面既包含了word，也包含了belong，中间用空格分开 
    char str[50];
    gets(str); 
    while (strcmp(str, "end") != 0)
    {
        //截取word
        int i;
        for (i=0; str[i]!=' '; ++i)
            word[index][i] = str[i];
        word[index][i++] = '\0'; 
        //截取belong
        strcpy(belong[index], str+i); 
        hashkey = ELFHash(belong[index]);

        //这里是处理哈希冲突，采用开散列法，也叫拉链法 
        //采用头插 
        p = new node;
        p->pos = index;
        p->next = hash[hashkey];
        hash[hashkey] = p;

        ++index;

        //继续输入字符串
        gets(str);
    }

    //查询
    cin >> str;
    hashkey = ELFHash(str);
    p = hash[hashkey];
    //处理冲突 
    while (NULL != p)
    {
        //找到 
        if (strcmp(belong[p->pos], str) == 0)
            break;
        p = p->next;
    }
    if (NULL == p)
        cout << "eh" << endl;
    else
        cout << word[p->pos] << endl; 

    return 0;
}