c - 哈希表 : how to achieve 0(1)?

Question

上下文:

我在阅读 Pomakis 的哈希表实现时出现了一个问题。 Hash lookup

我经常使用 Startpage 来查找更多信息，但仍然一头雾水。

问题:

因为它使用链表来检索 key ，怎么可能得到 0(1) 的时间复杂度？

问题:

结构:

typedef struct KeyValuePair_struct {
    const void *key;
    void *value;
    struct KeyValuePair_struct *next;
} KeyValuePair;

对我来说，它看起来像一个链表。如果我错了，请纠正我。

void *HashTableGet(const HashTable *hashTable, const void *key) {
    long hashValue = hashTable->hashFunction(key) % hashTable->numOfBuckets;
    KeyValuePair *pair = hashTable->bucketArray[hashValue];

    while (pair != NULL && hashTable->keycmp(key, pair->key) != 0)
        pair = pair->next;

    return (pair == NULL)? NULL : pair->value;
}

我到处都读到要获得 key ，我们必须从结构链的开头迭代到正确的结构，因为我们事先不知道下一个结构的地址。

<=> 动态分配。

所以我不明白这一点:后一段代码似乎从链的开头开始迭代，但作者说它是 O(1)(他可能是对的，我的假设肯定是错误的它是 0(n) )。

我知道我错过了什么。但是什么？

谢谢

Answer 1

函数 HashTableGet() 会先从数组中获取它的 KeyValuePair

KeyValuePair *pair = hashTable->bucketArray[hashValue];

这个操作是O(1)

下一个指针仅在添加新的 KeyValuePair 时不同的键产生相同的哈希值的情况下使用。然后下一个指针用于将 KeyValuePair 存储在列表中。

检索时，如果键与第一个 KeyValuePair 键不匹配，则需要搜索整个列表。

while (pair != NULL && hashTable->keycmp(key, pair->key) != 0)
    pair = pair->next;