How to implement a Hash Table in C

[ravi]

Hi
can anybody tell me that which ds will be best suited to implement a
hash table in C/C++

thanx. in advanced

[CBFalconer]

Malcolm McLean wrote:

"Richard Heathfield" <rj*@see.sig.in validwrote in message

.... snip ...

>

>His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable() function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>

--
Posted via a free Usenet account from http://www.teranews.com

[Malcolm McLean]

"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...

Malcolm McLean wrote:

>"Richard Heathfield" <rj*@see.sig.in validwrote in message

... snip ...

>>

>>His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable() function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

It's hard to read. Purely syntactical. The indirection operator happens to
be the same as a multiply. All functions take parentheses, except sizeof,
which is a function in the sense that matters - it retuns a value based on
its argument, but not of course in terms of generated code. So you've got
two quirks in one expression.

In compiler terms t is better, of course, because if you change ptr's type
the call will automatically update. But that's an overly narrow
understanding of maintainability which doesn't address the real issue.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Malcolm McLean]

"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...

Flash Gordon wrote:

>Malcolm McLean wrote, On 18/08/07 10:58:

... snip ...

>>

>>Criticisms have been made, some of them indisuptable bug reports,

For which you have not published an errata so that your audience
know about them.

For contrast, look at my hashlib. It was published complete with
the test suite and test programs that evaluated it during and after
development. I have had two and a half bug reports since the
initial publication, and no more for years.

And there was one I found in Dann's recommended text, admittedly in a code
fragment, and one in Ben Pfaff's circular buffer. Two in my two hash
tables, though one could be described as a feature. So assuming
Poisson-distributed bugs, we're doing about equally. However I am blamed.

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

[Richard Heathfield]

Malcolm McLean said:

>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...

>>

<snip>

>"ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

It's hard to read.

Does anyone else here apart from Malcolm have difficulty reading it?
Hands up please.

<snip>

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[santosh]

Richard Heathfield wrote:

Malcolm McLean said:

>>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******* ********@yahoo. com...

>>>

<snip>

>>"ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

It's hard to read.

Does anyone else here apart from Malcolm have difficulty reading it?
Hands up please.

To be honest this construct threw me the first time I encountered it, which
is of course in clc, but it hasn't bothered me in the slightest after I
looked it up in the FAQ.

C's expressions have to be understood with C's rules and quirks in mind, not
by comparing them to mathematical expressions. I suppose someone new to C
will find it a bit strange, but then this is true for almost all
programming languages. There's a reason they are not classified under the
natural languages class.

[Flash Gordon]

CBFalconer wrote, On 18/08/07 19:40:

Malcolm McLean wrote:

>"Richard Heathfield" <rj*@see.sig.in validwrote in message

... snip ...

>>His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable() function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

Unless you need enough space for two objects ;-)

Unsurprisingly, I agree with you on this.
--
Flash Gordon

[Keith Thompson]

"Malcolm McLean" <re*******@btin ternet.comwrite s:

"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...

>Malcolm McLean wrote:

>>"Richard Heathfield" <rj*@see.sig.in validwrote in message

... snip ...

>>>
His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable( ) function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

It's hard to read. Purely syntactical. The indirection operator
happens to be the same as a multiply. All functions take parentheses,
except sizeof, which is a function in the sense that matters - it
retuns a value based on its argument, but not of course in terms of
generated code. So you've got two quirks in one expression.

No, sizeof is not a function. It's a unary operator, just like "-",
"*", and "&". (If "sizeof" is a function in some abstract sense, then
so is "-", but C doesn't call them functions.) The confusion is
probably caused by the fact that it's the only operator whose symbol
look like an identifier rather than punctuation.

Pretend that 'sizeof' had been spelled '$', and you'll see what I mean.

But if you find
ptr = malloc(sizeof *ptr);
too confusing because it looks too much like a multiplication, you can
write
ptr = malloc(sizeof(* ptr));
applying the operator to a parenthesized expression.

In compiler terms t is better, of course, because if you change ptr's
type the call will automatically update. But that's an overly narrow
understanding of maintainability which doesn't address the real issue.

The real issue is that the clc-approved form (a) is perfectly
understandable once it's explained (something you could do in your
book if you chose), and (b) makes maintenance easier, because you
don't have to keep the target type and the size expression
synchronized manually (with no warning from the compiler if you get it
wrong).

You're right that 'ptr = malloc(sizeof *ptr)' is not common. That's a
pity, because it's *better* than the alternatives, and you have an
opportunity to help teach that.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Flash Gordon]

Malcolm McLean wrote, On 18/08/07 22:02:

>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...

>Malcolm McLean wrote:

>>"Richard Heathfield" <rj*@see.sig.in validwrote in message

... snip ...

>>>
His malloc is not ideal - answer = malloc(sizeof *answer); would
be preferable. He repeats this mistake later in the (poorly named)
hashtable( ) function.

Too hard to read. malloc( sizeof *ptr) is a bad clc ism that you
will seldom see in another environment. The reader has to perform
a mental dereference which makes it harder to see if the size of
correct.

Nonsense. "ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

It's hard to read.

A lot of newbies here don't find it hard once it is pointed out to them.

Purely syntactical.

Only if you consider "ptr = malloc(sizeof(t ype))" to be purely syntactical.

The indirection operator happens
to be the same as a multiply.

I very much doubt that people would mistake it for being multiplication
in this usage.

All functions take parentheses, except
sizeof, which is a function in the sense that matters - it retuns a
value based on its argument, but not of course in terms of generated
code.

It is only a function in the same sense that a unary minus is a
function. It has one operand and yields a result. The lack of
parenthesis in the "clc recommended" form if anything make it clearer it
is not a function.

So you've got two quirks in one expression.

You have more quirks than that.

In compiler terms t is better, of course, because if you change ptr's
type the call will automatically update. But that's an overly narrow
understanding of maintainability which doesn't address the real issue.

Most of the regulars here have a good few years of experience in
maintaining code written by themselves and others. I personally also
have experience of passing code on (not C code) to be maintained by
others and still being around myself to here what their issues are. So I
think many of us have reason to believe we *do* understand what the
maintainability issues are, and many of us disagree with you on this.
--
Flash Gordon

[pete]

Richard Heathfield wrote:

>
Malcolm McLean said (in reply to me):

malloc( sizeof *ptr) is a bad clc ism

No, it's a good clc-ism.

(ptr = malloc(N * sizeof *ptr)) is an absolutely great expression;
I use it much.

that you will seldom see in another environment.

Right. As Sturgeon says, at least 90% of everything is crud, so you'd
expect to find malloc(sizeof *ptr) in only 10% of cases (or fewer).
That doesn't mean it's bad. It just means most people haven't come
across it yet.

The reader has to perform a mental dereference which makes it harder
to see if the size of correct.

If the reader has to perform a mental dereference, he (or she) doesn't
understand sizeof. No dereferencing occurs, because sizeof does not
evaluate its argument. Furthermore, the size is *bound* to be correct
for any object pointer type.

For strings, I frequently call malloc this way:
char *string = malloc(length + 1);

--
pete

[Richard]

Richard Heathfield <rj*@see.sig.in validwrites:

Malcolm McLean said:

>>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******* ********@yahoo. com...

>>>

<snip>

>>"ptr = malloc(sizeof *ptr);" is automatically the right
size. No checking of any form is required.

It's hard to read.

Does anyone else here apart from Malcolm have difficulty reading it?
Hands up please.

<snip>

IMO, It is fairly uncommon to see

(sizeof *p)

in legacy code bases and is at odds with "normal" C operators as was
well described by Keith in another post in this thread. I think MM has
a point.

The people reading his algorithms shouldn't need to be C experts to
understand his code.

But don't let that stop you taking another opportunity to proclaim your
genius.