How are same hash vs same key handled?

Question

This question is not specific to any programming language, I am more interested in a generic logic.

Generally, associative maps take a key and map it to a value. As far as I know, implementations require the keys to be unique otherwise values get overwritten. Alright.

So let us assume that the above is done by some hash implementation. What if two DIFFERENT keys get the same hash value? I am thinking of this in the form of an underlying array whose indices are in a result of hash on said keys. It could be possible that more than one unique key gets mapped to the same value yes? If so, how does such an implementation handle this? How is handling same hash different from handling same key? Since same key results in overwriting and same hash HAS to retain the value.
I understand hashing with collision, so I know chaining and probing. Do implementations iterate over the current values which are hashed to a particular index and determine if the key is the same?
While I was searching for the answer I came across these links:
1. What happens when a duplicate key is put into a HashMap?
2. HashMap with multiple values under the same key
They don't answer my question however. How do we distinguish between same hash vs same key?

score 3 · Answer 1 · answered Jul 04 '17 at 06:53

You can not tell what a key is from the index, so no you can not iterate over the values to find any information about the keys. You will either have to guarantee 0 collisions or store the information that was hashed to give the index.

If you only have values stored in your structure, there is no way to tell if they have the same key or just the same hash. You will need to store the key along with the value to know.

score 3 · Accepted Answer · answered Jul 04 '17 at 07:05

By comparing the keys. If you look at object-oriented implementations of hash maps, you'll find that they usually require two methods to be implemented on the key type:

bool equal(Key key1, Key key2);
int hash(Key key);

If only the hash function can be given and no equality function, that restricts the hash map to be based on the language's default equality. This is not always desirable as sometimes keys need to be compared with a different equality function. For example, if the keys are strings, an application may need to do a case-insensitive comparison, and then it would pass a hash function that converts to lowercase before hashing, and an equal function that ignores case.

The hash map stores the key alongside each corresponding value. (Usually, that's a pointer to the key object that was originally stored.) Any lookup into the hash map has to make a key comparison after finding a matching hash, to verify that the key actually matches.

For example, for a very simple hash map that stores a list in each bucket, the list would be a list of (key, value) pairs, and any lookup compares the keys of each list entry until it finds a match. In pseudocode:

Array<List<Pair<Key, Value>>> buckets;
Value lookup(Key k_sought) {
    int h = hash(k_sought);
    List<Pair<Key, Value>> bucket = buckets[h];
    for (kv in bucket) {
        Key k_found = kv.0;
        Value v_found = kv.1;
        if (equal(k_sought, k_found)) {
            return v_found;
        }
    }
    throw Not_found;
}

How are same hash vs same key handled?

2 Answers2