更多互联网新鲜资讯、工作奇淫技巧关注原创【飞鱼在浪屿】（日更新）

简介：关于如何使用C编程语言实现简单哈希表数据结构的说明。简要演示了线性和二进制搜索，然后设计并实现了一个哈希表。目标是证明哈希表的内部结构并不可怕，但在一定的约束下，很容易从头开始构建。

最近，写了一个简单的程序，该程序对各种语言中的单词频率进行计数，但C在其标准库中没有哈希表数据结构。

当意识到这一点时，可以做很多事情：使用线性搜索，使用二进制搜索，获取其他人的哈希表实现或编写自己的哈希表。或切换到更丰富的语言。我们将快速看一下线性和二进制搜索，然后学习如何编写自己的哈希表。这在C语言中通常是必需的，但如果在使用另一种语言时需要自定义哈希表，它也很有用。

线性搜索

最简单的选择是使用线性搜索来扫描数组。如果只有几个项目，这实际上不是一个坏策略–在使用字符串的简单比较中，它比哈希表查找最多约7个项目的速度要快（但是除非程序对性能非常敏感，否则可能就可以了）最多20或30个项目）。线性搜索还允许将新项目追加到数组的末尾。使用这种类型的搜索，正在比较num_keys / 2个项目的平均值。

假设要在bob以下数组中搜索键（每个项都是具有关联的整数值的字符串键）：

只需从开头（foo索引0）开始，然后比较每个键。如果key与要查找的匹配，就完成了。如果不是，则移至下一个插槽。搜索bob需要五个步骤（索引0到4）。

这是C语言中的算法（假设每个数组项都是字符串键和整数值）：

typedef struct {
    char* key;
    int value;
} item;

item* linear_search(item* items, size_t size, const char* key) {
    for (size_t i=0; ivalue);
    return 0;
}

二进制搜索

另一种简单的方法是将项目放在按键排序的数组中，并使用二进制搜索来减少比较次数。这就是在纸质词典中查找内容的方式。

C甚至bsearch在其标准库中都有一个功能。二进制搜索即使对于数百个项目也相当快（尽管不如哈希表那么快），因为只比较log（num_keys）个项目的平均值。但是，由于数组需要保持排序，因此不能在不复制其余部分的情况下插入项目，因此插入仍然需要平均num_keys / 2个操作。

假设再次查找bob（在此预先排序的数组中）：

使用二进制搜索时，从中间（buzz）开始，如果其中的键大于要查找的键，则使用下半部分重复该过程。如果更大，将以较高的一半重复该过程。在这种情况下，它导致三个步骤，分别在索引3、1、2处，然后我们有了它。这是3个步骤，而不是5个步骤，拥有的项目越多，线性搜索的改进就会（呈指数增长）越好。

这是在C中（使用和不使用bsearch）的处理方式。该item结构的定义与上面相同。

int cmp(const void* a, const void* b) {
    item* item_a = (item*)a;
    item* item_b = (item*)b;
    return strcmp(item_a->key, item_b->key);
}

item* binary_search(item* items, size_t size, const char* key) {
    if (size + size < size) {
        return NULL; // size too big; avoid overflow
    }
    size_t low = 0;
    size_t high = size;
    while (low < high) {
        size_t mid = (low + high) / 2;
        int c = strcmp(items[mid].key, key);
        if (c == 0) {
            return &items[mid];
        }
        if (c < 0) {
            low = mid + 1; // eliminate low half of array
        } else {
            high = mid;    // eliminate high half of array
        }
    }
    // Entire array has been eliminated, key not found.
    return NULL;
}

int main(void) {
    item items[] = {
        {"bar", 42}, {"bazz", 36}, {"bob", 11}, {"buzz", 7},
        {"foo", 10}, {"jane", 100}, {"x", 200}};
    size_t num_items = sizeof(items) / sizeof(item);

    item key = {"bob", 0};
    item* found = bsearch(&key, items, num_items, sizeof(item), cmp);
    if (found == NULL) {
        return 1;
    }
    printf("bsearch: value of 'bob' is %d\n", found->value);

    found = binary_search(items, num_items, "bob");
    if (found == NULL) {
        return 1;
    }
    printf("binary_search: value of 'bob' is %d\n", found->value);
    return 0;
}

注意：在中binary_search，最好避免预先进行“超出一半尺寸的检查”。也就是将mid计算更改为low + (high-low)/2。

哈希表

哈希表有很多不同的类型，可以做很多不同的优化。但是，如果将简单的哈希函数与所谓的“线性探测”一起使用，则可以非常轻松地创建一个体面的哈希表。

哈希表是一种容器数据结构，可让快速查找键（通常是字符串）以找到其对应的值（任何数据类型）。在幕后，它们是由键的哈希函数索引的数组。

哈希函数将密钥转换为随机数，并且必须始终在给定相同密钥的情况下返回相同的数字。例如，使用哈希函数（64位FNV-1a），上述键的哈希值如下：

之所以显示哈希模16的原因是因为我们将从一个16个元素的数组开始，所以我们需要将哈希限制为该数组中元素的数量–模运算除以16并得出余数，将数组索引限制为0到15。

当在哈希表中插入一个值时，以16为模，计算其哈希值，并将其用作数组索引。因此，与大小为16的阵列，我们就插入bar在索引10中，bazz在图8，bob在图4，等等。让我们将所有项目插入哈希表数组中（除了x–我们将在下面进行介绍）：

要查找值，我们只需获取array[hash(key) % 16]。如果数组大小是2的幂，则可以使用array[hash(key) & 15]。注意元素的顺序不再有意义。

但是，如果两个键散列为相同的值（在模16之后），该怎么办？根据哈希函数和数组的大小，这很常见。例如，当我们尝试添加x到上面的数组时，其哈希模16为7。但是我们已经foo在索引7处，因此发生冲突。

有多种处理冲突的方法。一般上，将创建一个一定大小的哈希数组，如果发生冲突，则将使用链接列表来存储哈希到相同索引的值。但是，链表通常在添加项目时需要额外的内存分配，遍历它们意味着查找分散在内存中的指针，这在现代CPU上相对较慢。

处理碰撞的一种更简单，更快捷的方法是线性探测：如果我们要插入一个项目，但是已经有一个项目，只需移至下一个插槽。如果下一个插槽也已满，请再次移动，直到找到一个空插槽，如果命中阵列的末尾，则环绕到开头。（有其他探测方法，而不仅仅是移动到下一个插槽，但这超出了本文的范围。）该技术比链接列表快很多，因为CPU缓存可能已经获取了下一个项目。

添加“冲突” x（值为200）后，哈希表数组如下所示。我们首先尝试索引7，但是该索引为hold foo，所以我们移至索引8，但是该索引为hold bazz，因此我们再次移至索引9，该索引为空，因此将其插入到此处：

当哈希表太满时，需要分配一个更大的数组并将这些项移到上方。当哈希表中的项目数已达到数组的大小时，这是绝对必需的，但是通常您希望在哈希表的一半或四分之三满时执行此操作。如果没有足够早地调整其大小，则冲突将变得越来越普遍，并且查找和插入操作的速度将越来越慢。如果等到快满了，基本上就回到了线性搜索。

有了良好的哈希函数，这种哈希表平均每次查找需要进行一次操作，再加上对密钥进行哈希的时间（但通常，密钥是相对较短的字符串）。

API设计

首先，考虑一下我们想要的API：需要一种创建和销毁哈希表，获取给定键值，为给定键设置值，获取项数以及对项进行迭代的方法。目标不是最大效率的API，而是一个相当容易实现的API。

经过几次迭代，确定了以下函数和结构：

// Hash table structure: create with ht_create, free with ht_destroy.
typedef struct ht ht;

// Create hash table and return pointer to it, or NULL if out of memory.
ht* ht_create(void);

// Free memory allocated for hash table, including allocated keys.
void ht_destroy(ht* table);

// Get item with given key (NUL-terminated) from hash table. Return
// value (which was set with ht_set), or NULL if key not found.
void* ht_get(ht* table, const char* key);

// Set item with given key (NUL-terminated) to value (which must not
// be NULL). If not already present in table, key is copied to newly
// allocated memory (keys are freed automatically when ht_destroy is
// called). Return address of copied key, or NULL if out of memory.
const char* ht_set(ht* table, const char* key, void* value);

// Return number of items in hash table.
size_t ht_length(ht* table);

// Hash table iterator: create with ht_iterator, iterate with ht_next.
typedef struct {
    const char* key;  // current key
    void* value;      // current value

    // Don't use these fields directly.
    ht* _table;       // reference to hash table being iterated
    size_t _index;    // current index into ht._entries
} hti;

// Return new hash table iterator (for use with ht_next).
hti ht_iterator(ht* table);

// Move iterator to next item in hash table, update iterator's key
// and value to current item, and return true. If there are no more
// items, return false. Don't call ht_set during iteration.
bool ht_next(hti* it);

有关此API设计的一些注意事项：

• 为简单起见，我们使用C样式的NUL终止的字符串。我知道有更有效的字符串处理方法，但这符合C的标准库。
• 该ht_set函数分配并复制密钥（如果是第一次插入）。通常，不想让caller使用方担心这一点，也不必确保密钥记忆仍然存在。请注意，ht_set将返回指向重复键的指针。这主要用作“内存不足”错误信号-失败时返回NULL。
• 但是，ht_set不复制该值。调用方要确保值指针在哈希表的生命周期内有效。
• 值不能为NULL。这使ht_get稍微简单一些，因为不必区分NULL值和根本没有设置的值。
• 该ht_length函数不是严格必需的，因为可以通过迭代表来找到长度。但是，这有点痛苦（并且很慢），所以具有很有用ht_length。
• 可以通过多种方式进行迭代。在C语言中，将显式迭代器类型与while循环一起使用似乎很简单自然（请参见下面的示例）。从返回的值ht_iterator是一个值，而不是指针，两者都是为了提高效率，因此调用方不必释放任何东西。
• 没有ht_remove从哈希表中删除项目的方法。对于线性探测，删除是一件棘手的事情（由于留下了“空洞”），但是在使用哈希表时，我通常不需要删除项目。

演示程序

下面是一个简单的程序（demo.c），演示了如何使用API?的所有功能。它计算标准输入中唯一的，以空格分隔的单词的频率，并打印结果（以任意顺序显示，因为哈希表的迭代顺序未定义）。它以打印唯一单词的总数结束。

// Example:
// $ echo 'foo bar the bar bar bar the' | ./demo
// foo 1
// bar 4
// the 2
// 3

void exit_nomem(void) {
    fprintf(stderr, "out of memory\n");
    exit(1);
}

int main(void) {
    ht* counts = ht_create();
    if (counts == NULL) {
        exit_nomem();
    }

    // Read next word from stdin (at most 100 chars long).
    char word[101];
    while (scanf("%100s", word) != EOF) {
        // Look up word.
        void* value = ht_get(counts, word);
        if (value != NULL) {
            // Already exists, increment int that value points to.
            int* pcount = (int*)value;
            (*pcount)++;
            continue;
        }

        // Word not found, allocate space for new int and set to 1.
        int* pcount = malloc(sizeof(int));
        if (pcount == NULL) {
            exit_nomem();
        }
        *pcount = 1;
        if (ht_set(counts, word, pcount) == NULL) {
            exit_nomem();
        }
    }

    // Print out words and frequencies, freeing values as we go.
    hti it = ht_iterator(counts);
    while (ht_next(&it)) {
        printf("%s %d\n", it.key, *(int*)it.value);
        free(it.value);
    }

    // Show the number of unique words.
    printf("%d\n", (int)ht_length(counts));

    ht_destroy(counts);
    return 0;
}

创建并销毁

分配新的哈希表非常简单。我们从初始数组容量16（存储在中capacity）开始，这意味着它最多可以容纳8个项目，然后再进行扩展。有两种分配，一种分配用于哈希表结构本身，另一种分配给entrys数组。请注意，我们calloc用于entrys数组，以确保所有键以NULL开头，这意味着所有插槽均为空。

该ht_destroy函数释放了该内存，但也释放了沿途分配的重复键的内存（更多内容请参见下文）。

// Hash table entry (slot may be filled or empty).
typedef struct {
    const char* key;  // key is NULL if this slot is empty
    void* value;
} ht_entry;

// Hash table structure: create with ht_create, free with ht_destroy.
struct ht {
    ht_entry* entries;  // hash slots
    size_t capacity;    // size of _entries array
    size_t length;      // number of items in hash table
};

#define INITIAL_CAPACITY 16  // must not be zero

ht* ht_create(void) {
    // Allocate space for hash table struct.
    ht* table = malloc(sizeof(ht));
    if (table == NULL) {
        return NULL;
    }
    table->length = 0;
    table->capacity = INITIAL_CAPACITY;

    // Allocate (zero'd) space for entry buckets.
    table->entries = calloc(table->capacity, sizeof(ht_entry));
    if (table->entries == NULL) {
        free(table); // error, free table before we return!
        return NULL;
    }
    return table;
}

void ht_destroy(ht* table) {
    // First free allocated keys.
    for (size_t i = 0; i < table->capacity; i++) {
        if (table->entries[i].key != NULL) {
            free((void*)table->entries[i].key);
        }
    }

    // Then free entries array and table itself.
    free(table->entries);
    free(table);
}

散列函数

接下来，我们定义哈希函数，它是FNV-1a哈希算法的直接C实现。请注意，FNV不是随机的或加密的哈希函数，因此攻击者有可能创建具有很多冲突的密钥，并导致查找速度变慢–为此，Python放弃了FNV。但是，对于我们的用例，FNV是简单而快速的。

就算法而言，FNV-1a只是使用“偏移量”常量开始哈希，对于字符串中的每个字节，对哈希与该字节进行XOR运算，然后将其乘以一个大质数。偏移量和质数由具有博士学位的人员精心选择。

我们使用的是64位版本，因为现在大多数计算机都是64位的。特别是如果我们有一个非常大的哈希表，它似乎比使用32位版本更好。

#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL

// Return 64-bit FNV-1a hash for key (NUL-terminated). See description:
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
static uint64_t _hash(const char* key) {
    uint64_t hash = FNV_OFFSET;
    for (const char* p = key; *p; p++) {
        hash ^= (uint64_t)(unsigned char)(*p);
        hash *= FNV_PRIME;
    }
    return hash;
}

在这里，不做详细的分析，但其中包括一个小的统计程序，该程序可以打印根据输入中的唯一单词创建的哈希表的平均探测长度。我们使用FNV-1A散列算法似乎五十万英语单词的列表（平均探针长度1.40）上正常运行，并且还搭配了五十万非常相似键像一个列表效果很好word1，word2等（平均探针长度1.38）。

有趣的是，当尝试FNV-1算法（如FNV-1a，但在XOR之前完成乘法运算）时，英语单词的平均探针长度仍然为1.43，但类似的键却表现很差–平均探针长度为5.02。因此，在我的快速测试中，FNV-1a无疑是赢家。

get

接下来让我们看一下该ht_get函数。首先，它通过capacity（与entrys数组的大小）取模来计算哈希，这是通过与进行ANDing来完成的capacity - 1。因为为简单起见，我们确保数组大小始终为2的幂。

然后循环，直到找到一个空插槽，在这种情况下，我们没有找到key。对于每个非空插槽，我们用于strcmp检查该插槽上的密钥是否是我们要寻找的密钥（除非发生冲突，否则它将是第一个密钥）。如果没有，我们将沿着一个插槽移动。

void* ht_get(ht* table, const char* key) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(table->capacity - 1));

    // Loop till we find an empty entry.
    while (table->entries[index].key != NULL) {
        if (strcmp(key, table->entries[index].key) == 0) {
            // Found key, return value.
            return table->entries[index].value;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= table->capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }
    return NULL;
}

set

该ht_set函数稍微复杂一点，因为如果元素太多，则必须扩展表。在我们的实现中，每当容量达到一半时，我们会将容量加倍。这有点浪费内存，但是却使事情变得非常简单。

首先，ht_set功能。它只是在必要时扩展表格，然后插入以下项目：

const char* ht_set(ht* table, const char* key, void* value) {
    assert(value != NULL);
    if (value == NULL) {
        return NULL;
    }

    // If length will exceed half of current capacity, expand it.
    if (table->length >= table->capacity / 2) {
        if (!ht_expand(table)) {
            return NULL;
        }
    }

    // Set entry and update length.
    return ht_set_entry(table->entries, table->capacity, key, value,
                        &table->length);
}

该操作的要点在ht_set_entryhelper函数中（请注意，循环与中的一个非常相似ht_get）。如果plength参数为非NULL，则从中调用它ht_set，因此我们分配并复制密钥并更新长度：

// Internal function to set an entry (without expanding table).
static const char* ht_set_entry(ht_entry* entries, size_t capacity,
        const char* key, void* value, size_t* plength) {
    // AND hash with capacity-1 to ensure it's within entries array.
    uint64_t hash = hash_key(key);
    size_t index = (size_t)(hash & (uint64_t)(capacity - 1));

    // Loop till we find an empty entry.
    while (entries[index].key != NULL) {
        if (strcmp(key, entries[index].key) == 0) {
            // Found key (it already exists), update value.
            entries[index].value = value;
            return entries[index].key;
        }
        // Key wasn't in this slot, move to next (linear probing).
        index++;
        if (index >= capacity) {
            // At end of entries array, wrap around.
            index = 0;
        }
    }

    // Didn't find key, allocate+copy if needed, then insert it.
    if (plength != NULL) {
        key = strdup(key);
        if (key == NULL) {
            return NULL;
        }
        (*plength)++;
    }
    entries[index].key = (char*)key;
    entries[index].value = value;
    return key;
}

怎么样的ht_expand辅助函数？它分配一个新的条目数组，该数组是当前容量的两倍，并ht_set_entry与plengthNULL一起使用来复制条目。即使哈希值相同，索引也会有所不同，因为容量已更改（索引是哈希模数容量）。

// Expand hash table to twice its current size. Return true on success,
// false if out of memory.
static bool ht_expand(ht* table) {
    // Allocate new entries array.
    size_t new_capacity = table->capacity * 2;
    if (new_capacity < table->capacity) {
        return false;  // overflow (capacity would be too big)
    }
    ht_entry* new_entries = calloc(new_capacity, sizeof(ht_entry));
    if (new_entries == NULL) {
        return false;
    }

    // Iterate entries, move all non-empty ones to new table's entries.
    for (size_t i = 0; i < table->capacity; i++) {
        ht_entry entry = table->entries[i];
        if (entry.key != NULL) {
            ht_set_entry(new_entries, new_capacity, entry.key,
                         entry.value, NULL);
        }
    }

    // Free old entries array and update this table's details.
    free(table->entries);
    table->entries = new_entries;
    table->capacity = new_capacity;
    return true;
}

长度和迭代

该ht_length函数很简单–我们在更新过程中更新项目数_length，因此只需返回以下内容：

size_t ht_length(ht* table) {
    return table->length;
}

迭代是最后一步。要创建迭代器，用户将调用ht_iterator，然后移至下一项，ht_next并在返回时循环调用true。它们的定义方式如下：

hti ht_iterator(ht* table) {
    hti it;
    it._table = table;
    it._index = 0;
    return it;
}

bool ht_next(hti* it) {
    // Loop till we've hit end of entries array.
    ht* table = it->_table;
    while (it->_index < table->capacity) {
        size_t i = it->_index;
        it->_index++;
        if (table->entries[i].key != NULL) {
            // Found next non-empty item, update iterator key and value.
            ht_entry entry = table->entries[i];
            it->key = entry.key;
            it->value = entry.value;
            return true;
        }
    }
    return false;
}

讨论

就是这样– ht.c中的实现只有大约200行代码，包括空行和注释。

正如我所提到的，我想使实现保持简单，并且不太担心性能。但是，与Go的map实现进行的快速性能比较，它的性能相当好-有50万个英语单词，此C版本的查找速度慢了50％，插入速度却快了40％。

说到Go，使用像Go这样的语言编写自定义哈希表甚至更加容易，因为不必担心处理内存分配错误或释放分配的内存。

显然，使用C版本可以做更多的事情。通过进行各种测试，可以专注于安全性和可靠性。可以专注于性能，减少内存分配，对重复的键使用“凹凸分配器”，将短键存储在每个项目结构中，依此类推。可以提高内存使用率，并调整_ht_expand为每次都不使大小增加一倍。或者，可以添加功能，例如项目删除。