How do I search a hash table?

问题:

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.

回答1:

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.

回答2:

I usually prefer to make each entry in the table a struct so I can create a linked list to handle collisions. This reduces collisions significantly. Something like this.

struct hashtable
{
    int key;
    struct hashtable *pList;
};

struct hashtable ht[10];

void Insert(int key);
{
    index = Hash(key);
    if (!ht[index].key)
    {
        ht[index].key = key;
        ht[idnex].pList = 0;
    } 
    else
    {
        struct hashtable *pht;
        pht = ht[index].pList; 
        while (pht->pList)
            pht = pht->pList;
        pht->pList = new struct hashtable;
        pht->pList->key = key;
        pht->pList->pList = 0;
    }
    return;
}

The lookup function would, of course, have to traverse the list if it doesn't find the first entry's key matches. If performance is critical, you could use other strategies for the linked lists such as sorting them and using a binary search.