哈希表—理论与实践

作者：Mihalis Tsoukalos
发表于 2015 年 10 月 12 日

我第一次听说哈希表是在攻读理学学士学位期间选修了编译器课程之后。 事实是，那时我无法完全理解和欣赏它们的用处。 既然我现在对哈希表有了更多的了解，我决定写一篇关于哈希表的文章，以便其他人也能看到它们的重要性。

哈希表可以使用任何编程语言实现，包括 Awk。 然而，与其他关键选择相比，编程语言的选择并不是最重要的。 哈希表用于编译器、数据库、缓存、关联数组等等。 哈希表是计算机科学中最重要的数据结构之一。

问题

本文用作示例的问题是找出在一个文本文件中出现的单词在另一个文本文件中出现了多少次。 本文中的所有程序都使用一个文本文件（《傲慢与偏见》）来填充哈希表。 另一个文本文件（《汤姆·索亚历险记》）将用于测试哈希表的性能。 您可以从古腾堡计划下载这两个文本文件。

以下输出显示了每个文件包含的单词数


$ wc AofTS.txt
    9206   73845  421884 AofTS.txt
$ wc PandP.txt
   13426  124589  717573 PandP.txt

如您所见，这两个文本文件都相对较大，这对于基准测试来说是好事。 您的实际哈希表可能没有那么大。 为了删除各种控制字符以及标点符号和数字，对这两个文本文件进行了进一步处理


$ strings PandP.txt > temp.INPUT
$ awk '{for (i = 1; i <= NF; i++) print $i}' temp.INPUT > new.INPUT
$ cat new.INPUT |  tr -cd '![a-zA-Z]\n' > INPUT
$ strings AofTS.txt > temp.CHECK
$ awk '{for (i = 1; i <= NF; i++) print $i}' temp.CHECK > new.CHECK
$ cat new.CHECK |  tr -cd '![a-zA-Z]\n' > empty.CHECK
$ sed '/!/d' empty.CHECK > temp.CHECK
$ sed '/^\s*$/d' temp.CHECK > CHECK

简化这两个文件的原因是某些控制字符导致 C 程序崩溃。 由于本文的目的是展示哈希表，因此我决定简化输入，而不是花时间试图找出问题并修改 C 代码。

在使用第一个文件 (INPUT) 作为输入构建哈希表之后，第二个文件 (CHECK) 将用于测试哈希表。 这将是哈希表的实际用途。

理论

让我从哈希表的定义开始。 哈希表是一种数据结构，用于存储一个或多个键值对。 哈希表可以存储任何类型的键。

哈希表使用哈希函数来计算桶或槽数组的索引，从中可以找到正确的值。 理想情况下，哈希函数会将每个键分配给一个唯一的桶。 不幸的是，这种情况很少发生。 在实践中，多个键将哈希到同一个桶。 哈希表最重要的特征是桶的数量。 哈希函数使用桶的数量。 第二个最重要的特征是使用的哈希函数。 哈希函数最关键的特性是它应该产生哈希值的均匀分布。

你可以说现在的搜索时间是 O(n/k)，其中 n 是键的数量，k 是哈希数组的大小。 虽然改进看起来很小，但您应该意识到，对于具有 20 个桶的哈希数组，搜索时间现在小了 20 倍。

哈希函数必须行为一致，并且为相同的键输出相同的哈希值，这一点很重要。 当两个键哈希到相同的索引时，就会发生冲突——这并不是一种不寻常的情况。 有许多方法可以处理冲突。

一个好的解决方案是使用单独的链表。 哈希表是指针数组，每个指针都指向下一个具有相同哈希值的键。 当发生冲突时，键将在恒定时间内插入到链表的头部。 现在的问题是，当您必须搜索给定键的哈希值时，您将必须搜索整个链表以查找此键。 在最坏的情况下，您可能需要遍历整个链表——这是链表应该适度小的主要原因，从而要求大量的桶。

您可以想象，解决冲突涉及某种线性搜索； 因此，您需要一个哈希函数，尽可能地减少冲突。 用于解决冲突的其他技术包括开放寻址、罗宾汉哈希和 2 选择哈希。

哈希表擅长以下方面

  • 在具有“正确”桶数的哈希表中，每次查找的平均成本与表中存储的元素数量无关。

  • 当可以预先预测最大条目数时，哈希表尤其高效，这样可以一次分配最佳大小的桶数组，并且永远不会调整大小。

  • 如果键值对的集合是固定的并且是预先知道的（因此不允许插入和删除），您可以通过仔细选择哈希函数、桶表大小和内部数据结构来降低平均查找成本。

哈希表也有一些缺点

  • 它们不擅长保存排序数据。 如果您希望数据排序，则使用哈希表效率不高。

  • 当条目数非常小时，哈希表效果不佳，因为尽管哈希表上的操作平均需要恒定时间，但好的哈希函数的成本可能远高于顺序列表或搜索树的查找算法的内部循环。

  • 对于某些字符串处理应用程序（例如拼写检查），哈希表可能不如树或有限自动机有效。

  • 虽然每次操作的平均成本是恒定的并且相当小，但单次操作的成本可能相当高。 特别是，如果哈希表使用动态调整大小，则偶尔插入或删除键可能需要与条目数成比例的时间。 这在您希望快速获得结果的应用程序中可能是一个严重的缺点。

  • 当存在许多冲突时，哈希表会变得非常低效。

正如我确信您所理解的那样，并非每个问题都可以通过哈希表得到同样好的解决。 在决定使用什么之前，您应该始终考虑和检查所有选项。

图 1 显示了一个简单的哈希表，其中显示了键和值。 哈希函数是模 10 函数； 因此，需要十个桶，因为模 10 计算只能产生十个结果。 只有十个桶被认为不是很好，特别是如果值的数量增长很大，但对于说明目的来说还可以。

图 1. 简单的哈希表

总而言之，哈希表应遵循以下原则

  • 不要有太多桶，只需满足需要即可。

  • 哈希函数最好尽可能多地考虑键提供的信息。 这不是一件容易的事。

  • 哈希函数必须能够将相似的键哈希为不同的哈希值。

  • 每个桶应具有相同数量的键，或者至少尽可能接近相等（这是一个非常理想的属性）。

  • 遵循一些原则将使冲突不太可能发生。 首先，您应该使用素数个桶。 其次，数组的大小越大，发生冲突的可能性就越小。 最后，您应该确保哈希函数足够智能，可以尽可能均匀地分布其返回值。

删除、插入和查找

哈希表的主要操作是插入、删除和查找。 您可以使用哈希值来确定将键存储在哈希表中的位置。 稍后，您可以使用相同的哈希函数来确定在哈希表中搜索给定键的位置。

一旦哈希表被填充，搜索就与执行插入操作相同。 您对要搜索的数据进行哈希处理，转到数组中的该位置，向下查看从该位置开始的列表，并查看要查找的内容是否在列表中。 步数为 O(1)。 哈希表的最坏情况搜索时间为 O(n)，当所有键都存储在同一个桶中时可能会发生这种情况。 然而，这种情况发生的概率非常小，以至于最佳情况和平均情况都被认为是 O(1)。

您可以在 Internet 上或关于该主题的几本书中找到许多哈希表实现。 棘手的部分是使用正确数量的桶并选择一个有效的哈希函数，该函数将值尽可能均匀地分布。 分布不均匀肯定会增加冲突的数量和解决冲突的成本。

C 实现

第一个实现将存储在名为 ht1.c 的文件中。 该实现使用单独的链表，因为单独的链表是一个合理的选择。 为了简单起见，输入和输出文件名都硬编码在程序内部。 完成输入并构建哈希表后，程序开始逐字读取第二个文件，并开始检查是否可以在哈希表中找到单词。

列表 1 显示了 ht1.c 文件的完整 C 代码。

列表 1. ht1.c 

#include 
#include 
#include 
#include 

#define TABLESIZE 5

// Linked List
typedef struct node
{
  char *data;
  struct node *next;
} node;

// A Hash Function: the returned hash value will be the 
// ASCII value of the first character of the string
// modulo the size of the table.
unsigned int hash(const char *str, int tablesize)
{
    int value;

    // Get the first letter of the string
    value = toupper(str[0]) - 'A';

    return value % tablesize;
}

static int lookup(node *table[], const char *key)
{
    unsigned index = hash(key, TABLESIZE);
    const node *it = table[index];

    // Try to find if a matching key in the list exists
    while(it != NULL && strcmp(it->data, key) != 0)
    {
        it = it->next;
    }
    return it != NULL;
}

int insert(node *table[], char *key)
{
    if( !lookup(table, key) )
    {
        // Find the desired linked list
        unsigned index = hash(key, TABLESIZE);
        node *new_node = malloc(sizeof *new_node);

        if(new_node == NULL)
            return 0;

        new_node->data = malloc(strlen(key)+1);

        if(new_node->data == NULL)
            return 0;

        // Add the new key and link to the front of the list
        strcpy(new_node->data, key);
        new_node->next = table[index];
        table[index] = new_node;
        return 1;
    }
    return 0;
}

// Populate Hash Table
// First parameter: The hash table variable
// Second parameter: The name of the text file with the words
int populate_hash(node *table[], FILE *file)
{
    char word[50];
    char c;

    do {
        c = fscanf(file, "%s", word);
        // IMPORTANT: remove newline character
        size_t ln = strlen(word) - 1;
        if (word[ln] == '\n')
            word[ln] = '\0';

        insert(table, word);
    } while (c != EOF);

    return 1;
}

int main(int argc, char **argv)
{
    char word[50];
    char c;
    int found = 0;

    // Initialize the hash table
    node *table[TABLESIZE] = {0};

    FILE *INPUT;
    INPUT = fopen("INPUT", "r");
    // Populate hash table
    populate_hash(table, INPUT);
    fclose(INPUT);
    printf("The hash table is ready!\n");

    int line = 0;
    FILE *CHECK;
    CHECK = fopen("CHECK", "r");

    do {
        c = fscanf(CHECK, "%s", word);

        // IMPORTANT: remove newline character
        size_t ln = strlen(word) - 1;
        if (word[ln] == '\n')
            word[ln] = '\0';

        line++;
        if( lookup(table, word) )
        {
            found++;
        }
    } while (c != EOF);

    printf("Found %d words in the hash table!\n", found);

    fclose(CHECK);
    return 0;
}
更好的 C 实现

第二个实现将存储在名为 ht2.c 的文件中。 此实现也使用单独的链表。 大部分 C 代码与 ht1.c 中的代码相同，只是哈希函数不同。 修改后的哈希函数的 C 代码如下


int hash(char *str, int tablesize)
{
    int sum = 0;

    // Is it a valid string?
        if(str == NULL)
    {
        return -1;
    }

        // Calculate the sum of all characters in the string
        for( ; *str; str++)
    {
        sum += *str;
    }

        // Return the sum mod the table size
        return (sum % tablesize);
}

此哈希函数比另一个哈希函数做得更好的是，它考虑了字符串的所有字母，而不仅仅是第一个字母。 因此，生成的数字（对应于键在哈希表中的位置）更大，这使得能够利用具有更多桶的哈希表。

基准测试

所提供的基准测试远非准确或科学。 它们只是指示什么更好、什么有效、什么无效等等。 请记住，找到最佳哈希表大小并不总是容易的。

所有程序都按如下方式编译


$ gcc -Wall program.c -o program

可靠的 time 命令在使用四种不同的哈希表大小执行 ht1 后，产生了以下输出


$ grep define ht1.c
#define TABLESIZE 101
$ time ./ht1
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.401s
user    0m0.395s
sys         0m0.004s
$ grep define ht1.c
#define TABLESIZE 10
$ time ./ht1
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.794s
user    0m0.788s
sys         0m0.004s
$ grep define ht1.c
#define TABLESIZE 1001
$ time ./ht1
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.410s
user    0m0.404s
sys         0m0.004s
$ grep define ht1.c
#define TABLESIZE 5
$ time ./ht1
The hash table is ready!
Found 59843 words in the hash table!

real    0m1.454s
user    0m1.447s
sys         0m0.004s

图 2 显示了 ht1.c 程序的 TABLESIZE 变量的四个不同值的执行时间图。 ht1.c 的糟糕之处在于，使用 101 个桶的哈希表的性能几乎与使用 1,001 个桶的哈希表的性能相同！

图 2. ht1.c 程序的 TABLESIZE 变量的四个不同值的执行时间图

接下来，这是执行 ht2.c 程序的結果


$ grep define ht2.c
#define TABLESIZE 19
$ time ./ht2 INPUT CHECK
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.439s
user    0m0.434s
sys     0m0.003s
$ grep define ht2.c
#define TABLESIZE 97
$ time ./ht2 INPUT CHECK
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.116s
user    0m0.111s
sys         0m0.003s
$ grep define ht2.c
#define TABLESIZE 277
$ time ./ht2 INPUT CHECK
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.072s
user    0m0.067s
sys         0m0.003s
$ grep define ht2.c
#define TABLESIZE 997
$ time ./ht2 INPUT CHECK
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.051s
user    0m0.044s
sys         0m0.003s
$ grep define ht2.c
#define TABLESIZE 22397
$ time ./ht2 INPUT CHECK
The hash table is ready!
Found 59843 words in the hash table!

real    0m0.049s
user    0m0.044s
sys     0m0.003s

图 3 显示了 ht2.c 程序中使用的 TABLESIZE 变量的五个不同值的执行时间图。 所有哈希表大小均为素数。 使用素数的原因是它们在模运算中表现更好。 这是因为素数除了 1 和它本身之外没有正除数。 因此，素数与另一个整数的乘积比非素数与另一个整数的乘积具有更少的正除数。

图 3. ht2.c 程序中使用的 TABLESIZE 变量的五个不同值的执行时间图

如您所见，新的哈希函数比 ht1.c 中的哈希函数表现好得多。 因此，使用更多桶大大提高了哈希表的性能。 然而，只要文本文件中的单词是有限的，使用比输入文件中唯一单词数更多的桶是没有意义的。

检查使用两个不同桶数的 ht2 实现中键的分布是有用的。 以下 C 函数打印每个桶中键的数量


void printHashTable(node *table[], const unsigned int tablesize)
{
    node *e;
    int i;
    int length = tablesize;
    printf("Printing a hash table with %d buckets.\n", length);

    for(i = 0; i<length; i++)
    {
        // printf("Bucket: %d\n", i);
        // Get the first node of the linked list
        // for the given bucket.
        e = table[i];

        int n = 0;
        if (e == NULL)
        {
            // printf("Null bucket %d\n", i);
        }
        else
        {
            while( e != NULL )
            {
                n++;
                e = e->next;
            }
        }
        printf("Bucket %d has %d keys\n", i, n);
    }
}

图 4 显示了两个哈希表中每个桶中的键数：一个具有 97 个桶，另一个具有 997 个桶。 具有 997 个桶的哈希表似乎遵循其填充桶的模式，而具有 97 个桶的哈希表分布更均匀。 然而，更大的哈希表在每个桶中具有更少的键数，这正是您真正想要的，因为每个链表中的键越少意味着搜索时间越少。

图 4. 具有不同桶数的两个哈希表中每个桶中的键数

总结

哈希表是计算机科学和编程的重要组成部分。 我希望本文能帮助您理解它们的重要性并阐明一些关于它们的内容。

Mihalis Tsoukalos 是一位 UNIX 管理员和开发人员、DBA 和数学家，他喜欢技术写作。 他是《Go 系统编程》和《精通 Go》的作者。 您可以通过 http://www.mtsoukalos.eu 和 @mactsouk 联系他。

加载 Disqus 评论

近期文章

Stay Ahead of the Game: Essential Tools and Techniques for Linux Server Monitoring
保持领先地位：Linux 服务器监控的必备工具和技术
George Whittaker
Linux Meets AI: Top Machine Learning Frameworks You Need to Know
Linux 遇见 AI：您需要了解的顶级机器学习框架
George Whittaker
Linux Memory Management: Understanding Page Tables, Swapping, and Memory Allocation
Linux 内存管理：理解页表、交换和内存分配
George Whittaker
Mastering Software Package Management with Yum and DNF on CentOS and RHEL
掌握 CentOS 和 RHEL 上 Yum 和 DNF 的软件包管理
George Whittaker
Streamline Your Logs: Exploring Rsyslog for Effective System Log Management on Ubuntu
简化您的日志：探索 Rsyslog 在 Ubuntu 上进行有效的系统日志管理
George Whittaker
Linux Networking Protocols: Understanding TCP/IP, UDP, and ICMP
Linux 网络协议：理解 TCP/IP、UDP 和 ICMP
George Whittaker