如何搜索哈希表? [英] How do I search a hash table?

问题描述

我刚刚开始了解哈希表，并且了解如何插入而不是搜索.这些是我将基于此问题的算法:

哈希键

int Hash (int key) {
    return key % 10;  //table has a max size of 10
}

线性探测以解决碰撞.

假设我用键1、11和21两次调用insert.这将返回所有3个键的插槽1.冲突解决后，该表的插槽1、2和3的值分别为1、11和21.这就是我对插入的理解.

这样做之后，如果我搜索键11和21，我将如何获得插槽2和3?从我阅读的内容来看，搜索散列表实际上应与插入操作相同，只是当到达所需的插槽时，是在该插槽中返回值，而不是在其中插入一些东西.

如果我直接采用此方法并应用相同的算法，则如果我搜索密钥11，我将到达插槽4，因为它将从插槽1开始并继续探查，直到找到一个空插槽.即使它是我想要的，它也不会在插槽2处停止，因为它不为空.

即使使用单独的链接，我也在为此苦苦挣扎.所有这三个键都将存储在插槽1中，但是使用相同的算法进行搜索将返回插槽1，而不是链表中的哪个节点.

解决方案

每个插槽都存储一个键/值对.在搜索每个插槽时，请检查密钥是否等于要搜索的密钥.找到相等的键时，停止搜索并返回值.

通过单独的链接，您可以在列表中进行线性搜索，并对照列表中的每个键检查键.

I've just started learning about hash tables and I understand how to insert but not how to search. These are the algorithms I'll be basing this question off:

Hashing the key

int Hash (int key) {
    return key % 10;  //table has a max size of 10
}

Linear probing for collision resolution.

Suppose I call insert twice with the keys 1, 11, and 21. This would return slot 1 for all 3 keys. After collision resolution the table would have the values 1, 11, and 21 at slots 1, 2, and 3. This is what I assume would happen with my understanding of inserting.

After doing this, how would I get the slots 2 and 3 if I search for the keys 11 and 21? From what I've read searching a hash table should do literally the same thing as inserting except when you arrive at the desired slot, you return the value at that slot instead of inserting something into it.

If I take this literally and apply the same algorithm, if I search for the key 11 I would arrive at slot 4 because it would start at slot 1 and keep probing forward until it finds an empty slot. It wouldn't stop at slot 2 even though it's what I want because it's not empty.

I'm struggling with this even if I use separate chaining. All 3 keys would be stored at slot 1 but using the same algorithm to search would return slot 1, not which node in the linked list.

解决方案

Each slot stores a key/value pair. As you're searching through each slot, check whether the key is equal to the key you're searching for. Stop searching and return the value when you find an equal key.

With separate chaining, you can do a linear search through the list, checking the key against each key in the list.

这篇关于如何搜索哈希表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！