Aha...I see. Is that how hash-tables works?

( Yes, it's my old c=64, I still remember all the opcodes for it, and code on it sometimes, it's great! :) )
Posted on 2003-04-10 02:41:58 by david
A hash table is usually an array (sometimes flexible in size, "dynarray" or "vector" or whatever you want to call it) of linked lists.

My idea (which isn't perfected - haven't thought of how to do reasonable implementation of insert/delete of arbitrary nodes) would be a linked list of arrays of nodes :). And it isn't anything new either, lots of people have been playing around with various optimizations of linked lists.
Posted on 2003-04-10 02:50:44 by f0dder
There are at least three different ways to implement hash tables.

1) Array of structures.
The hash value is an index to the first slot (array entry) to be checked. A search ends either on a match or an open slot. The search can be as simple as an ordinary linear search, or it can use a more complex scheme for selecting the next slot.

The advantage is there is no overhead for pointers. The disadvantages include creating a fixed size table, and performance almost as bad as raw linear search when the table is nearly full.

2) Array of linked lists.
The hash value is an index to an array entry, which is a pointer to a linked list. If the list doesn't have a matching entry, a new entry can be added to the list.

The advantages include: comparing only entries with the same hash value, table size is limited by whatever memory management system you use.

3) Array of linked bucket lists.
Same as #2, except each list item is not a single entry, but a "bucket" or array of entries. When adding a new entry, if a bucket is full, a new bucket is created and attached to the bucket list before adding the new entry.

The main advantage is that it clusters together entries with the same hash value, possibly improving cache performance.
Posted on 2003-04-10 15:29:31 by tenkey