what is "extensible hash table" and how to implement it? 
Author Message
 what is "extensible hash table" and how to implement it?

I am trying to do a project which need a so-called "extensible hash table"
data struture. I really have no idea of what it is and how it can be
implemented. Could any one give me some tips?
Thx a lot!!

Anyone can tell me where is the proper group to post this question if not
here?



Fri, 23 Aug 2002 03:00:00 GMT  
 what is "extensible hash table" and how to implement it?

Quote:

>I am trying to do a project which need a so-called "extensible hash table"
>data struture. I really have no idea of what it is and how it can be
>implemented. Could any one give me some tips?

If you have no idea what it is, why would you want to implement it instead of
one of the many other structures you don't know about? How do you know
that your project needs it? ;)

I have an off-the-shelf implementation of extendible hashing in ANSI C.
http://users.footprints.net/~kaz/kazlib.html



Fri, 23 Aug 2002 03:00:00 GMT  
 what is "extensible hash table" and how to implement it?


Quote:
> I am trying to do a project which need a so-called "extensible hash table"
> data struture. I really have no idea of what it is and how it can be
> implemented. Could any one give me some tips?
> Thx a lot!!

> Anyone can tell me where is the proper group to post this question if not
> here?

comp.programming is more appropriate for algorithmic questions. We deal with
language issues here.

However I'll give you a brief run-down anyway. The idea of a hash table is
that you take a string or other long key, reduce it to a small number, and
use that number as an index into a table where the data is stored.

The function to reduce your key to a small integer is called the hash
function. A simple hash function would simply AND out the first few bits of
the key. For various reasons this isn't a very good approach, and so more
complex hash functions use modulus operators, sum the bytes, etc to try to
get a good distribution of values for keys.

The big problem with has tables is collisions - two keys map to the same
index. The simplest strategy is *linear probing* - search the table until you
find the first empty slot. This causes problems when entries are deleted -
simply setting the entry to NULL might make it impossible to find later
inserts.

The other problem is that the hash table cannot get too full. Obviously if
all but one of the slots were occupied you could have to search the entire
table to find a free place to put your data - not very efficient. Usually the
load factor of the hash table is kept to under fifty percent.

If the amount of data exceeds fifty percent of the data size you have to
*rehash*. This means mallocing a bigger table, finding new hash values for
each entry (since the hash value is always 0 - MAX-1 you have to change your
hash function slightly), and finally deleting the old entry.

If you make an attempt at this algorithm in C people here will be happy to
correct it for you.

Sent via Deja.com http://www.deja.com/
Before you buy.



Fri, 23 Aug 2002 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Hash tables with "unsigned long" keys

2. I am going to study "C"

3. implementing "ls eli*"

4. implementing "complete" comparison

5. Implement a "var.Add(...)"?

6. implementing "trace" in c

7. Question on implementing "repeat...until keypress"?

8. Rules for "implements" in VB

9. "Implement Connection Point..." option is missing

10. implement a "kill" with signals

11. How to implement "autometic statement completion"?

12. Implementing "cp" shell command

 

 
Powered by phpBB® Forum Software