Question

说了这么多散列表查找的思想，我们就来看看查找的实现代码。

8.12.1　散列表查找算法实现

首先是需要定义一个散列表的结构以及一些相关的常数。其中HashTable就是散列表结构。结构当中的elem为一个动态数组。

#define SUCCESS 1
#define UNSUCCESS 0
/* 定义散列表长为数组的长度 */
#define HASHSIZE 12    
#define NULLKEY -32768
typedef struct
{
    /* 数据元素存储基址，动态分配数组 */
    int *elem;         
    /* 当前数据元素个数 */
    int count;         
} HashTable;
/* 散列表表长，全局变量 */
int m = 0;             

有了结构的定义，我们可以对散列表进行初始化。

/* 初始化散列表 */
Status InitHashTable(HashTable *H)
{
    int i;
    m = HASHSIZE;
    H->count = m;
    H->elem = (int *)malloc(m * sizeof(int));
    for (i = 0; i < m; i++)
        H->elem[i] = NULLKEY;
    return OK;
}

为了插入时计算地址，我们需要定义散列函数，散列函数可以根据不同情况更改算法。

/* 散列函数 */
int Hash(int key)
{
    /* 除留余数法 */
    return key % m; 
}

初始化完成后，我们可以对散列表进行插入操作。假设我们插入的关键字集合就是前面的{12,67,56,16,25,37,22,29,15,47,48,34}。

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

代码中插入关键字时，首先算出散列地址，如果当前地址不为空关键字，则说明有冲突。此时我们应用开放定址法的线性探测进行重新寻址，此处也可更改为链地址法等其他解决冲突的办法。

散列表存在后，我们在需要时就可以通过散列表查找要的记录。

/* 散列表查找关键字 */
Status SearchHash(HashTable H, int key, int *addr)
{
    /* 求散列地址 */
    *addr = Hash(key);              
    /* 如果不为空，则冲突 */
    while (H.elem[*addr] != key)    
    {
        /* 开放定址法的线性探测 */
        *addr = (*addr + 1) % m;    
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
        {                           
            /* 如果循环回到原点 */
            /* 则说明关键字不存在 */
            return UNSUCCESS;       
        }
    }
    return SUCCESS;
}

查找的代码与插入的代码非常类似，只需做一个不存在关键字的判断而已。

8.12.2　散列表查找性能分析

最后，我们对散列表查找的性能作一个简单分析。如果没有冲突，散列查找是我们本章介绍的所有查找中效率最高的，因为它的时间复杂度为O(1)。可惜，我说的只是“如果”，没有冲突的散列只是一种理想，在实际的应用中，冲突是不可避免的。那么散列查找的平均查找长度取决于哪些因素呢？

1．散列函数是否均匀

散列函数的好坏直接影响着出现冲突的频繁程度，不过，由于不同的散列函数对同一组随机的关键字，产生冲突的可能性是相同的，因此我们可以不考虑它对平均查找长度的影响。

2．处理冲突的方法

相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。

3．散列表的装填因子

所谓的装填因子α=填入表中的记录个数/散列表长度。α标志着散列表的装满的程度。当填入表中的记录越多，α就越大，产生冲突的可能性就越大。比如我们前面的例子，如图8-11-5所示，如果你的散列表长度是12，而填入表中的记录个数为11，那么此时的装填因子α=11/12=0.9167，再填入最后一个关键字产生冲突的可能性就非常之大。也就是说，散列表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。

不管记录个数n有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内，此时我们散列查找的时间复杂度就真的是O(1)了。为了做到这一点，通常我们都是将散列表的空间设置得比查找集合大，此时虽然是浪费了一定的空间，但换来的是查找效率的大大提升，总的来说，还是非常值得的。