数据结构(23)-散列表查找

2020-05-20 本文已影响0人 xxxxxxxx_123

定义

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 $f$ ，使得每一个关键字 $key$ 对应一个存储位置 $f(key)$ 。

        存储位置 = $f(关键字)$

查找的时候，直接根据这个确定的对应关系找到存储位置。我们把这种对应关系 $f$ 称为散列函数，也称为哈希(Hash)函数。

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间成为散列表或者哈希表(Hash Table)。关键字对应的记录存储位置称之为散列地址或者哈希地址。

当 $key1 ≠ key2$ ，却存在 $f(key1) = f(key2)$ ，这种情况称之为散列冲突，或哈希冲突。

散列表查找步骤

整个散列过程其实就是两步：

在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
当查找记录时，通过同样的散列函数计算记录的散列地址，然后按照此地址访问对应的记录。

所以说，散列技术既是一种存储方法，也是一种查找方法。由于散列的记录之间不存在逻辑关系，只是有关键的关联，所以散列主要是面向查找的存储结构。

散列技术最适合的求解问题就是查找与给定值相等的记录。散列表不适用与一个关键字对应多条记录的查找；也不适用于范围查找。

散列函数的构造

什么才算是好的散列函数呢？原则有二：

计算简单。
散列地址分布均匀。这样既可保证存储空间的有效利用，并能减少处理冲突所耗费的时间。

下面，我们就来看看常见的散列函数构造方法

直接定址法

使用关键字的某个线性函数为散列地址：

$f(key) = a * key + b$ (a，b均为常数)

适合查找表比较小且连续的情况。

数字分析法

如果关键字是位数较多的数字，比如说手机号码，那么极有可能前7位都是相同的，我们可以把后四位抽取出来作为散列地址。如果这个地址还是会出现冲突，可以对抽取出来的数字进行反转、左移、右移、或者前面得加等方式形成一个散列函数。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布，即可使用该方法。

平方取中法

平方取中法，就是假设关键字是123，它的平方是15129，取中间3位就是512。一般适用于不知道关键字的分布，而且位数又不是很大的情况。

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数不够也可），然后将这几部分叠加求和，并按照散列表表长，取后几位作为散列地址。比如关键字是9876543210，散列表长为3位，我们可以将其分为4组987 | 654 | 321 | 0，叠加求和987+654+321+0=1962，再取后3位为962。折叠法适合关键字位数较多的情况。

除留余数法

对于散列表长度为 $m$ 的散列函数为：

 $f(key) = key mod p(p <= m)$ (mod)是取模的意思

从公式可以看出，此函数的关键就是选择合适的 $p$ 。根据前人的经验来看，通常 $p$ 取小于或等于表长（最好接近表长）的最小质数或者不包含小于20质因子的合数。

随机数法

选择一个随机数，取关键字的随机函数值作为它的散列地址。
$f(key) = random(key)$

适用于关键字的长度不等的情况。

总之，选择散列函数，可以从以下条件入手：

计算散列地址
关键字的长度
散列表的大小
关键字的分布情况
记录查找的频率

处理散列冲突

开放定址法

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

    $f_i(key) = (f(key) + d_i) MOD m (d_i = 1,2,...m-1)$

比如，关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15，47，48，34}，表长为12，我们可以使用散列函数 $f(key) = key MOD 12$ 。计算前5个数的时候，都没有冲突，可以直接存入：12对应0，25对应1，16对应4，67对应7，56对应8。然后当我们计算37的时候，发现37也对应1，而此时1的位置已经存储了25，这就发生了冲突。此时，我们就需要使用上面的公式， $f(37) = (f(37) + 1) MOD 12 = 2$ ，将37对应2。依次类推，出现冲突就更新 $d_i$ 的值。等到48的时候， $f(48) = 0$ 冲突，于是 $f(48) = (f(48) + 1) MOD 12 = 1$ ，还是冲突，一直到 $f(48) = (f(48) + 6) MOD 12 = 6$ ，此时才有空位，赶快存入。

再散列函数法

再散列函数法，就是准备多个散列函数，发生冲突的时候，就换一个散列函数就行计算。

链地址法

链地址法，将出现冲突的关键字存在一个链表中。如下图所示：

散列链地址法.png

这样出现冲突，我们只需要给单链表增加结点即可。链地址法的问题就是遍历链表会带来性能损耗。

公共溢出区法

专门增加一个溢出表，用来存储冲突的关键字。

公共溢出区.png

在查找时，对给定值通过散列函数计算出散列地址之后，先与基本表的相应位置进行对比，如果相等则查找成功；如果不相等，则到溢出表中顺序查找。

散列表的查找实现

#define T_ERROR -1
#define T_OK 1
#define HASH_TABLE_LENTH 12
#define NULL_ELEMENT -32768
typedef int TStatus;

typedef struct {
    int *contents;
    int count;
}HashTable;

TStatus initHashTable(HashTable *ht) {
    ht->count = HASH_TABLE_LENTH;
    ht->contents = (int *)malloc(HASH_TABLE_LENTH * sizeof(int));
    for (int i = 0; i < HASH_TABLE_LENTH; i++) {
        ht->contents[i] = NULL_ELEMENT;
    }
    return T_OK;
}

// 散列函数: 除留余数法
int hash(int key) {
    return key % HASH_TABLE_LENTH;
}

// 向散列表插入关键字
void insertHash(HashTable *ht, int key) {
    int hashAddress = hash(key);
    
    /// 不为空 则说明有冲突
    while (ht->contents[hashAddress] != NULL_ELEMENT) {
        // 开放定址法线性探测
        hashAddress = (hashAddress + 1) % HASH_TABLE_LENTH;
    }
    
    /// 有空位 直接插入
    ht->contents[hashAddress] = key;
}

// 从散列表中查找
TStatus searchHash(HashTable ht, int key, int *hashAddress) {
    *hashAddress = hash(key);
    // 通过散列地址循环查找散列表
    while (ht.contents[*hashAddress] != key) {
        *hashAddress = (*hashAddress + 1) % HASH_TABLE_LENTH;
        if (ht.contents[*hashAddress] == NULL_ELEMENT || *hashAddress == hash(key)) {
            // 将整个散列表循环了一遍还是未找到 说明关键字不存在
            return T_ERROR;
        }
    }
    return T_OK;
}

通过代码可以看出，如果没有冲突的话，散列表查找的时间复杂度为 $O(1)$ 。

参考文献

大话数据结构