Re: How to implement a Hash Table in C


"Ben Bacarisse" <ben.usenet@xxxxxxxxx> wrote in message news:87y7ghh2v3.fsf@xxxxxxxxxxxx
"Malcolm McLean" <regniztar@xxxxxxxxxxxxxx> writes:

"Ben Bacarisse" <ben.usenet@xxxxxxxxx> wrote in message
news:87fy2q9s77.fsf@xxxxxxxxxxxx
"Malcolm McLean" <regniztar@xxxxxxxxxxxxxx> writes:

"ravi" <dceravigupta@xxxxxxxxx> wrote in message
news:1186820007.247243.115940@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hi
can anybody tell me that which ds will be best suited to implement a
hash table in C/C++

thanx. in advanced

Which ds?
You can read all about hash tables in my book, Basic Algorithms. The
hash tables chapter is free.

I think it should be pointed out that your hash table is not like
most. Most hash tables are dynamic structures that can grow as data
are added. Yours is fixed. The interface should have a clear warning
that the table fails (silently) if an attempt is made to add an item
beyond the initial capacity.

The point I made before (that the function loop indefinitely when the
table becomes full) is still true, but I now see that the add function
will silently fail long before that point is reached. If this limit
is by design, I think the text should make that limitation very clear.

I think your understanding of hash tables might need to be raised a
notch.

If you are going to be like that...

<snip>
It is odd (and probably very confusing to a beginner) that the add
function seems to return a success/fail indication, but that it does
not use it to signal this disastrous case.

The "disastrous case" can't happen. The fixed allocator will run out
of memory and return null when capity is reached. Please avoid this
sort of hyperbole.

OK. Less hyperbole. Your code exhibits undefined behaviour. You
'dereference' a null pointer. On my system I get a segmentation
violation before hash_add gets any say in the matter. If or when you
find the error, you will say it is a detail, a typo, whatever. I
don't think you worry about details like this.

Obviously if you say things like "the function will not return at all when the table is full" you cannot understand that a hash table (to be pedantic, one without "perfect hashing") cannot be more than about 88% full before the algorithm becomes pathological. In fact I pass in a "capacity" argument which is half table size.
I think you need to read the chapter again, as a pupil rather than as a critic.

As for the derefencing null pointer, that will happen if the constructor fails, and return NULL. That is standard behaviour throughout the book. If objects cannot be created, the constructing function returns a null pointer to show they have failed.
I couldn't see another. The code has been tested, but only on two systems (a UNIX mainframe and Windows) so that doesn't mean no errors remain, and of course typographical errors do creep in in the process of reformatting for print - I wish I had a tool to format source code automatically but I don't. The normal thing when you an error such as dereference of a null is to say "your code derererences a null" rather than to talk airly about "catastropic behaviour" in an arrogant manner.

Do you care, for example, that your statement:

The test for primality is interesting. The only absolutely sure way
of determining whether a number is prime, as far as is known, is to
attempt to divide by all prime numbers below or equal to its square
root.

is not true? Probably not. I will try, in future, to leave you alone.

You mean randomised primality testing? It's not absolutely sure.
I am no mathematician, maybe you could tell us your method?

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

.

Relevant Pages

  • Re: Config::General Failing test in ActivePerl
    ... > Test 8 is writing a hash to a file, and reloading it, and seeing if it ... It fails where a multi-line string is written out. ...
    (comp.lang.perl.modules)
  • Re: Ping Platy and other chair lovers
    ... playing silly buggers. ... creating a torrent, I figured out what I was meant to do, but now it always fails when trying to hash the files. ...
    (uk.rec.motorcycles)
  • Re: CryptSignHash
    ... When the peer gets the signed hash and decrypts it using RSA functions ... it fails to verify the hash. ...
    (microsoft.public.platformsdk.security)
  • Re: complex data structure
    ... > How do I access the hash key value pairs? ... This fails at runtime: ... is really the structure you want (scalar references to array references ... I also assume that your *original* data structure was a hash ...
    (comp.lang.perl)
  • Re: complex data structure
    ... > How do I access the hash key value pairs? ... This fails at runtime: ... is really the structure you want (scalar references to array references ... I also assume that your *original* data structure was a hash ...
    (comp.lang.perl.misc)