Comparing hash table implementations [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

Chained Hash Tables vs. Open-Addressed Hash Tables

In general I have seen two implementations of hash tables. The first is implemented as two arrays, one containing the keys, the other the values. The second has a single array, and then a linked list containing key-value objects.

What are the advantages and disadvantages 开发者_运维技巧of one implementation over the other? Both look equally good to me with regard to collision handling and put/get operations.

---

There's quite a nice write up on Wikipedia. The keywords you are looking for are open addressing (sometimes called closed hashing) vs closed addressing (sometimes called open hashing).

---

As johna says, we call The first example open addressing, while the latter is chaining.

The main drawback of open addressing is that by using your hashtable array for storing values, if many collisions occur, you will overflow the bucket array, and then have an expensive resizing. Also, this data structure is a little unclear.

With chaining, or pointers to linked lists, you will never overflow the array, though the linked lists could grow deep. This; however, is a consistent and predictable flow of data, and an easier concept.