Comparing hash table implementations

Question

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.

Please google this. This is a very basic topic in computer science. — Marcin, Mar 13 '11 at 18:05
@Marcin If a good answer does not yet exist on Stack Overflow, then this is a good question that deserves a good answer. — Phrogz, Mar 13 '11 at 18:08
Funnily enough, it's also a duplicate of this question: http://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables . I have very little sympathy for the view that we should entertain general questions on topics that are widely covered. — Marcin, Mar 13 '11 at 18:42

score 3 · Answer 1 · answered Mar 13 '11 at 18:09

3

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).

answered Mar 13 '11 at 18:09

score 2 · Accepted Answer · answered Mar 13 '11 at 18:25

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.

Comparing hash table implementations

2 Answers2