查找算法-散列表

• 当存储记录时，通过散列函数计算出记录的散列地址
• 当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

例一：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。
即：f(key) = key

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

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

平方取中法是将关键字平方之后取中间若干位数字作为散列地址。

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

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

f(key) = key mod p(p<=m)

• 事实上，这个方法不仅可以对关键字直接取模，也可以通过折叠、平方取中后再取模。
  例如下表，我们对有12个记录的关键字构造散列表时，就可以用f(key) = key mod 12的方法。

  
  

• p的选择是关键，如果对于这个表格的关键字，p还选择12的话，那得到的情况未免也太糟糕了：

  
  
  

  p的选择很重要，如果我们把p改为11，那结果就另当别论啦：

  
  
  

• 选择一个随机数，取关键字的随机函数值为它的散列地址。

• 即：f(key) = random(key)。

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

  
  
  
  
  

• 所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

• 它的公式是：
  fi(key) = (f(key)+di) MOD m (di=1,2,…,m-1)

• 例：假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},使用除留余数法(m=12)求散列表

  
  

• 可以修改di的取值方式，例如使用平方运算来尽量解决堆积问题：

  • fi(key) = (f(key)+di) MOD m (di=1²,-1²,2²,-2²…,q²,-q²,q<=m/1)

• 还有一种方法是，在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法：

  • fi(key) = (f(key)+di) MOD m (di是由一个随机函数获得的数列)

例：假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},同样使用除留余数法求散列表。

例：假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},同样使用除留余数法求散列表。

#define HASHSIZE 12
#define NULLKEY -32768

typedef struct
{
    int *elem;  // 数据元素的基址，动态分配数组
    int count;  // 当前数据元素的个数
}HashTable;

int InitHashTable(HashTable *H)
{
    H->count = HASHSIZE;
    H->elem = (int *)malloc(HASHSIZE * sizeof(int));
    if( !H->elem )
    {
        return -1;
    }
    for( i=0; i < HASHSIZE; i++ )
    {
        H->elem[i] = NULLKEY;
    }
    return 0;
}

// 使用除留余数法
int Hash(int key)
{
    return key % HASHSIZE;
}

// 插入关键字到散列表
void InsertHash(HashTable *H, int key)
{
    int addr;
    
    addr = Hash(key);
    
    while( H->elem[addr] != NULLKEY )   // 如果不为空，则冲突出现
    {
        addr = (addr + 1) % HASHSIZE;   // 开放定址法的线性探测
    }
    
    H->elem[addr] = key;
}

// 散列表查找关键字
int SearchHash(HashTable H, int key, int *addr)
{
    *addr = Hash(key);
    
    while( H.elem[*addr] != key )
    {
        *addr = (*addr + 1) % HASHSIZE;
        if( H.elem[*addr] == NULLKEY || *addr == Hash(key) )
        {
            return -1;
        }
    }
    
    return 0;
}