查找算法之散列表网站首页 技术交流

查找算法之散列表

终究还是散了 2024-06-28 12:01:02

简介查找算法之散列表

一.说明

刚好复习数据结构，前面几篇博客我们知道了顺序查找、二分查找、分块查找、树形查找（二叉排序树、平衡二叉树、红黑树、B树和B+树），这一篇博客介绍常用查找算法中的最后一个算法——散列表（哈希查找）。

同时，刚好参加的新星计划：数据结构与算法通道在周末结束，这一篇博客也是本周的学习任务。

二.散列表的基本概念

1.名词解释

散列表（Hash table）是一种基于哈希表实现的数据结构，它通过将给定的键值映射到一个特定的索引位置来存储和查找数据元素。散列表通常使用数组作为底层数据结构，并且需要一个可靠的散列函数来计算每个键对应的索引位置。

散列函数（Hash function）是一种将任意长度的输入数据映射到固定长度输出的函数。散列函数通常用于计算散列表中元素的索引位置，它将每个键值转换为一个唯一的整数值，这个整数值可以作为该元素在散列表中的索引。散列函数的设计非常重要，因为它直接影响散列表的性能和效率。一个好的散列函数应当尽可能避免哈希碰撞，即不同的键值映射到相同的索引位置。

哈希冲突（Hash collision）指的是两个或多个键值被散列到了相同的索引位置。由于散列表的大小是有限的，因此哈希冲突是不可避免的。当发生哈希冲突时，我们需要采取一些方法来解决它，以确保散列表的正确性和效率。常见的解决哈希冲突的方法包括链式存储法和开放地址法等。

同义词（Synonyms）是指具有相同或相似含义的单词。在散列表中，不同的键值可能被映射到相同的索引位置，这些键值即为同义词。解决同义词问题的方法之一是使用拉链法进行链式存储，在相同的散列值下将多个数据元素连接成一个链表，以避免发生冲突。

2.百度补充

散列表（Hash table）是一种常见的数据结构，它具有快速插入、查找和删除元素的能力。散列表通过将每个元素映射到一个唯一的索引位置来实现这些操作，这个索引位置可以称为哈希值或散列值。

散列表包含一个固定大小的数组，通常被初始化为空。当要插入一个元素时，首先需要计算该元素的哈希值，并将其作为数组索引来存储该元素。如果两个元素具有相同的哈希值，则会发生哈希冲突，解决哈希冲突的方法包括使用链式存储或开放地址法等。

在查询一个元素时，我们首先计算该元素的哈希值，并在数组中检查该位置是否存在元素。如果该位置为空，则表示该元素不存在于散列表中；否则，需要进行进一步的比较来确定该元素是否是所需的元素。

散列表是一种高效的数据结构，在大多数情况下，它的插入、查找和删除操作的时间复杂度都是 O(1)。但是，由于哈希冲突的存在，最坏情况下的时间复杂度可能会退化到 O(n)，因此合理的哈希函数设计和处理哈希冲突的方法非常重要。

3.个人补充

散列表 == 哈希表

散列函数 == 哈希函数

散列查找 == 哈希查找

它们是在不同编程语言的不同称呼而已，其实本质上是一个概念。

三.散列函数的构造方法

1.设计注意事项

设计散列函数时需要注意以下几个点：

均匀性：散列函数应该将输入的数据均匀地散布到整个哈希表中，这样可以使得每个桶中的元素数量尽可能平衡，避免出现某些桶特别拥挤而导致性能急剧下降的情况。
碰撞率：碰撞是指两个不同的键映射到了同一个散列表位置的情况。散列函数的设计应该尽可能减少碰撞的发生。一般来说，可以采用开放寻址法或者链式哈希表来解决碰撞问题。但是过多的碰撞也会影响哈希表的性能，因此需要在散列函数设计中尽量避免碰撞。
易计算：散列函数的计算速度应该足够快，否则会影响哈希表的性能。不同类型的数据可能需要使用不同的散列函数实现。
抗攻击：散列函数应该能够有效地防止故意构造的输入数据，如恶意攻击者故意制造出大量的碰撞，使得哈希表的性能急剧下降。
随机性：散列函数应该尽可能地随机，这样可以降低攻击者进行散列冲突攻击的难度。随机性可以通过在散列函数中使用随机数或者加盐等方式实现。

2.除留余数法

这是一种最简单、最常用的方法，假设散列表表长为m，取一个不大于m但最接近m的质数p，利用以下公式把关键字转换成散列地址。

散列函数为 H(key) = key % p

除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任意一个地址，从而尽可能减少冲突的可能性。

适用场景：较为常用，只要关键字是整数即可

3.直接定址法

直接取关键字的某个线性线性函数值为散列地址，散列函数为

H(key) = key 或 H(key) = a*key + b

式中，a和b是常数。这种方法最简单，且不会产生冲突。他适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多、则会造成存储空间的浪费。

适用场景：关键字分布基本连续

4.数字分析法

数字分析法是散列函数构造方法之一，它的基本思想是利用待存记录的关键字中的数字特征来构造散列地址。

具体地说，数字分析法将关键字看做一个r进制数（r通常取10），然后从右往左取出若干个数位，将它们组成一个新的数，再对哈希表长m取模，作为该记录的散列地址。如果不足m位，则在左边补0。

这里需要注意的是，选择哪些数位作为新数的数位，以及新数的长度，都会直接影响到散列的性能。一般来说，应该选择数字分布比较均匀的数位，并且尽可能地选取多的数位才能保证较好的散列效果。

需要注意的是，数字分析法虽然简单易行，但是它对数据的要求比较高，而且也容易受到数据规律的影响，因此其散列性能可能并不理想。在实际应用中，还需要根据具体情况，结合其他散列函数构造方法，综合考虑选取最合适的散列函数。

5.平方取中法

平方取中法是散列函数构造方法之一，它的基本思想是将关键字的平方值取中间几位作为散列地址。

具体地说，假设关键字为n位数字，首先将其平方得到一个2n位的数，然后从中间取出m（通常取m=3或4）位数作为散列地址。如果不足m位，则在左边右边补0，如果超过m位，则截取中间的m位。

这种方法的优点是简单易行，且能够较好地利用关键字的各个位上的信息，提高散列性能。但是需要注意的是，在实际应用中，由于平方操作可能导致结果溢出，因此需要对溢出进行处理，以免影响散列效果。

总的来说，平方取中法是一种比较基础的散列函数构造方法，适用于一些简单的应用场景。在实际应用中，还需要根据具体情况选择其他散列函数构造方法，并综合考虑多个因素，如时间、空间复杂度等，才能构造出最优秀的散列函数。

四.处理冲突的方法

1.拉链法

拉链法（链接法、链地址法）（Chaining）是一种使用哈希表来解决冲突的方法，也称为链接法。在这种方法中，哈希表中每个位置都存储一个链表，如果多个键值映射到同一个位置，则它们将被添加到同一个链表中。

当需要查找一个键时，先计算它的哈希值，然后定位到对应的链表，并在链表中顺序查找。由于哈希表的大小有限，而数据量可能很大，所以在设计时需要考虑好哈希函数的设计，以减少冲突的发生，从而提高查询效率。

当添加一个新的键值对时，也需要先计算其哈希值，然后定位到对应的链表，将其添加到链表的末尾即可。

拉链法虽然处理冲突的效果较好，但它会占用更多的内存空间，因为每个位置都需要维护一个链表。此外，在遍历整个链表时，查询效率可能会受到影响，特别是当链表过长时。

2.开放地址法

开放地址法是一种常见的解决哈希冲突问题的方法。

当使用哈希表时，可能会出现多个键被映射到同一个哈希槽上，这就是哈希冲突。开放地址法的主要思想是在发生冲突时，继续探测下一个哈希槽，直到找到空槽或者已经探测过所有的槽为止。

开放地址法有几种不同的探测方法，包括线性探测、二次探测、双重哈希等。其中，线性探测是最简单、最常用的一种方法，其基本思路是：如果当前哈希槽已经被占用，则依次查看下一个槽，直到找到一个空槽。

例如，假设使用哈希表来存储字符串类型的键，哈希函数为将字符串转换为整数后取余数，当出现冲突时，采用线性探测。当插入键值对时，如果计算出的哈希值已经被占用，则从该位置往后一个一个查找，直到找到一个空槽为止。如果整个哈希表都被查找过了，但仍然没有找到空槽，那么就需要扩容，重新分配内存空间。

虽然开放地址法是一种简单有效的解决哈希冲突的方法，但是它仍然存在一些问题，例如当哈希表中元素过多时，探测时间会变长，甚至可能导致性能下降。因此，在实际应用中，需要根据具体情况选择合适的哈希函数和解决冲突的方法。

五.散列查找及性能分析

散列查找（Hash Lookup）是一种基于哈希表的查找算法。它通过将关键字映射到哈希表的一个位置上，从而加快查找速度。在散列查找中，哈希函数起着关键作用。哈希函数可以将待查找的关键字映射到哈希表中的一个位置上，并且保证不同的关键字映射到不同的位置上。

散列查找的时间复杂度通常为O(1)，因为只需要计算一次哈希值即可在常数时间内访问到对应的数据。但是，在实际应用中，由于哈希冲突的出现，可能会导致查找效率下降。因此，如何解决哈希冲突也是散列查找性能优化的关键。

一些常见的解决哈希冲突的方法包括：链式法、开放地址法等。在使用链式法时，每个哈希槽都保存一个指向链表头结点的指针。如果哈希冲突发生，就将新元素插入到对应槽的链表尾部。在使用开放地址法时，当哈希冲突发生时，可以尝试探测下一个空槽，直到找到合适的位置为止。

在实际应用中，选择合适的哈希函数和解决哈希冲突的方法非常重要。一个好的哈希函数应当具有较低的哈希冲突率，并且能够均匀地将关键字映射到哈希表上。而解决哈希冲突的方法则需要根据具体情况来选取，不同的方法对应着不同的性能表现。

总之，散列查找是一种高效的查找算法，在大规模数据处理中得到了广泛的应用。在实际应用中，通过优化哈希函数和解决哈希冲突的方法，可以进一步提高散列查找的性能。

六.C语言实现散列查找

下面是一个简单的C语言实现散列查找的例子，使用链式法解决哈希冲突：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

// 定义哈希表中的数据结构
typedef struct node {
    char key[20]; // 键值
    int value; // 值
    struct node *next; // 指向下一个节点的指针
} Node;

// 定义哈希表结构体
typedef struct hashtable {
    Node *table[TABLE_SIZE]; // 存储元素的数组
} Hashtable;

// 初始化哈希表
void initHashtable(Hashtable *ht) {
    int i;
    for (i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL;
    }
}

// 计算哈希值
int hash(char *key) {
    int sum, i;
    for (sum = 0, i = 0; key[i] != ''; i++) {
        sum += key[i];
    }
    return sum % TABLE_SIZE;
}

// 向哈希表中插入元素
void insertElement(Hashtable *ht, char *key, int value) {
    int h = hash(key);
    // 创建新节点
    Node *newNode = (Node *) malloc(sizeof(Node));
    strcpy(newNode->key, key);
    newNode->value = value;
    newNode->next = NULL;

    if (ht->table[h] == NULL) { // 如果该位置没有元素，则直接插入
        ht->table[h] = newNode;
    } else { // 如果该位置已经有元素，则使用链式法解决冲突
        Node *p = ht->table[h];
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newNode;
    }
}

// 从哈希表中查找元素
int findElement(Hashtable *ht, char *key) {
    int h = hash(key);
    Node *p = ht->table[h];
    while (p != NULL) {
        if (strcmp(p->key, key) == 0) {
            return p->value;
        }
        p = p->next;
    }
    return -1; // 没有找到
}

// 测试函数
int main() {
    Hashtable ht;
    initHashtable(&ht);

    insertElement(&ht, "apple", 10);
    insertElement(&ht, "banana", 20);
    insertElement(&ht, "orange", 30);

    printf("The value of apple is %d
", findElement(&ht, "apple"));
    printf("The value of banana is %d
", findElement(&ht, "banana"));
    printf("The value of orange is %d
", findElement(&ht, "orange"));

    return 0;
}