If hashtable maps two keys to same value in a table, how will I get back my key

Can someone explain this to me, how will I get back my key if hashtable maps two keys to 开发者_开发技巧same value. Although, there is a linked list storing two sequential values, who decides which key to spit out when a common value is used to get the key/element. Thanks for answering my question.

---

Two keys mapping to the same hash value is called a collision. Any collection that uses hashing to store and lookup data must be able to handle collisions. This may be done, for example, with a linked list for each hash that contains multiple items (each collision).

Such a collection also stores the actual key. So if it finds a collision, it can still scan through those items to find the exact match. It just isn't as fast as when there is no collision because of the extra scan.

---

Hashtables are not designed to return the key by using the stored value, but rather the other way around. If you, however, need such functionality - having a bidirectional relation key <-> value - then you have various options:

• Use two hashtables, one that stores key -> value, one that stores the other part of the relation - value -> key
• Use a BiDirectional hashtable implementation (Google has one spec'd here) which supports this by doing the same thing internally

---

a) You are assuming a particular implementation of your hashtable b) This is very much implementation dependent.

Hashtables are for mapping keys -> values. The inverse mapping may not be possible, and as you have identified may not be well behaved.

---

You(or whoever creates the hashtable implementation) decides what to do when you insert a key that already exists.

The 2 common approaces are:

• Fail. Don't insert the new key/value, but indicate that the key already exists.
• Replace the existing key/value and return the old key/value pair.

A 3. option, which I havn't at least seen much in any C/C++ hashtable implementation:

• Retain the original key, but update/replace the new value for this key