Re: How to implement a Hash Table in C
- From: "Malcolm McLean" <regniztar@xxxxxxxxxxxxxx>
- Date: Sun, 12 Aug 2007 08:02:44 +0100
"Ben Bacarisse" <ben.usenet@xxxxxxxxx> wrote in message news:87y7ghh2v3.fsf@xxxxxxxxxxxx
"Malcolm McLean" <regniztar@xxxxxxxxxxxxxx> writes: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.
"Ben Bacarisse" <ben.usenet@xxxxxxxxx> wrote in message
"Malcolm McLean" <regniztar@xxxxxxxxxxxxxx> writes:I think your understanding of hash tables might need to be raised a
"ravi" <dceravigupta@xxxxxxxxx> wrote in message
can anybody tell me that which ds will be best suited to implement a
hash table in C/C++
thanx. in advanced
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.
If you are going to be like that...
<snip>It is odd (and probably very confusing to a beginner) that the addThe "disastrous case" can't happen. The fixed allocator will run out
function seems to return a success/fail indication, but that it does
not use it to signal this disastrous case.
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.
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.
You mean randomised primality testing? It's not absolutely sure.
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
is not true? Probably not. I will try, in future, to leave you alone.
I am no mathematician, maybe you could tell us your method?
Free games and programming goodies.
- Prev by Date: Re: critique my program!
- Next by Date: Re: Big arrays (confusion over FAQ 6.14)
- Previous by thread: Re: How to implement a Hash Table in C
- Next by thread: Re: How to implement a Hash Table in C