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

[websnarf]

On Aug 18, 11:37 am, CBFalconer <cbfalco...@yah oo.comwrote:

websn...@gmail. com wrote:

CBFalconer <cbfalco...@yah oo.comwrote:

Richard Harter wrote:

... snip ...

>[...] that always using the same probe increment in a
power of two table size also has bad properties. His
solution is to use the unused bits of the full hash to
select an increment size from a table of primes.

That is dangerous. The purpose of the multiple hash is to
have different search patterns for different objects that
have the same primary hash pattern.

No, its to have a different search pattern for different object
that have the same primary hash *INDEX* (i.e., post masking).
This is obvious since, for any good hash function, index
collisions will be many many times more common than full hash
function collisions.

Mathematically speaking, on average a single 32-bit (good) hash
function collision will occur roughly when 65536 entries appear,
while a hash index collision will occur roughly when the square
root of the table size number of entries occur (so for a 9
million entry table, that's just 3000 entries).

No, you are ignoring the size of the hash table itself. For
example, the starting size for hashlib is 17, so no more than 17
hash values (modulo 17) are useful. This changes as the table
enlarges itself.

Huh? Well of course I am ignoring small hash tables -- *ALL*
solutions are basically equivalent for small enough hash tables. The
problem is only interesting when there is a performance impact, which
will happen as the hash table holds thousands of entries.

I think you are misreading my language (I am exercising serious
restraint here) a hash function collision is not the same as a hash
index collision. This distinction matters for completely optimized
hash table implementations .

This avoids clustering, and tends to keep
the search chain short. The very iffy thing in hashlib is
the reduction of the range of the secondary hash, which
encourages light clustering in nearly empty tables.

You are ignoring the fact that skip values of 2, 4 and 6, for
example, for indexes starting on even offsets near each other
will tend to collide with each other as the table fills up.

Same skip-value, and commensurate offset collisions must be
minimized by increasing the chance they miss each other. This
happens most easily if the skip values are predominantly
co-prime, which is easiest to construct when they are simply
taken from a list of prime numbers.

Again, you are ignoring the effect of varying table size.

I am not. I am concerned with asymptotic size of hash tables which
are large enough to matter (a few thousand entries) otherwise the
problem is too small to be concerned with the details about (you just
need to make sure it works).

Perhaps you don't understand the basic mathematics. If you increase
the size of the table, the probability that two randomly chosen skip
values will not be coprime does *NOT* tend towards zero. The number
of pathological cases increases with the increase in table size. Thus
a strategy that just picks random skip values via another hash or
whatever, does not directly address the inherent inter-collision
problem.

You need to pick coprime (between each other) skip values if you use
linear probing. The most sensible way of doing this is to choose from
a set of primes.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Chris Dollin]

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.

I'll put my hand up, just to say "Not me sir! Easy peasy sir!
Fits neatly on the eyeball and can be checked without context!
Win win, sir!"

Of course anyone who's using a remotely syntax-colouring editor
won't think that `sizeof` is an ordinary left operand of a
multiplication; nor will anyone who already knows what `sizeof`
means.

It would be really nice to have empirical evidence either way,
of course, since we're well into anecdotage here.

--
Aged Aged Hedgehog
"Who do you serve, and who do you trust?" /Crusade/

[Malcolm McLean]

"Flash Gordon" <sp**@flash-gordon.me.ukwro te in message
news:62******** ****@news.flash-gordon.me.uk...

>>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 objection to

ptr = malloc(sizeof *ptr);

is purely syntactical. As Keith said, if sizeof were spelt $ and given
normal operator rules for whitespace

ptr = malloc($*ptr);

would be OK. The * wouldn't look like multiplication of an identifier.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Malcolm McLean]

"Flash Gordon" <sp**@flash-gordon.me.ukwro te in message
news:md******** ****@news.flash-gordon.me.uk...

You should also get your book reviewed somewhere like comp-programming
where the algorithms side will get properly reviewed, instead of the C
issues people concentrate on here.

That will happen.
The practical problem is that people focus on little things like ] instead
of ) for a close, or a missing check for null, because they are unambiguous.
However they are relatively easy to fix. The more serious criticisms come
out later - the car park maybe isn't the best metaphor for a hash table.
So it's best to get C language issues and size_t wars out of the way first.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Richard Harter]

On Fri, 17 Aug 2007 13:32:51 -0400, CBFalconer
<cb********@yah oo.comwrote:

>Richard Harter wrote:

>Eric Sosman <es*****@ieee-dot-org.invalidwrot e:

>>James Dow Allen wrote:

[...]
Speaking of Falconer, his method (linear probing with second
hash value used for probe increment) *requires* (even more so
than quadratic probing, see upthread) prime table size.

Well, not exactly: It requires only that the increment
between probes be relatively prime to the table size. A prime
table size makes this criterion easy to satisfy, but it's not
the only way. A table size equal to a power of two, for example,
works just fine if the probe increment is odd. (Degenerate
special case: pure linear probing with an increment of unity
works with any table size at all, prime or composite.)

In a thread in comp.programmin g (IIRCC) Paul Hsieh pointed out
that always using the same probe increment in a power of two
table size also has bad properties. His solution is to use the
unused bits of the full hash to select an increment size from a
table of primes.

That is dangerous. The purpose of the multiple hash is to have
different search patterns for different objects that have the same
primary hash pattern. This avoids clustering, and tends to keep
the search chain short. The very iffy thing in hashlib is the
reduction of the range of the secondary hash, which encourages
light clustering in nearly empty tables. The system attempts to
maintain tables at between 44 and 88% of capacity.

Also, I want the table action to be independent of the hash
functions (apart from speed), so the functions are computed every
time needed. The system functions with all the hash functions
replaced by the constant 1 (unity) (tested in the test suite) at a
considerable speed penalty. So the action is hash function
independent, but the speed is highly dependent.

Here is a little clue: Discussions of hash tables are not
confined to your particular implementation.

>
The system is intended to isolate all these decisions in the hash
table code, so the user need not worry about them. Similarly the
algorithms for table expansion, etc. The result is a storage and
retrieval black box.

[Kelsey Bjarnason]

On Sun, 19 Aug 2007 09:06:23 +0100, Malcolm McLean wrote:

"Flash Gordon" <sp**@flash-gordon.me.ukwro te in message
news:62******** ****@news.flash-gordon.me.uk...

>>>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 objection to

ptr = malloc(sizeof *ptr);

is purely syntactical.

It is? Why? Is there a syntax error in the code?

[Kelsey Bjarnason]

On Sat, 18 Aug 2007 21:14:44 +0000, 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?

This is one of those things which, like migrating to x++ from x = x + 1,
simply takes getting used to. It is idiomatic in what one might term
"good C code", not to mention around here, but a rank newbie - i.e.
someone who should not be reading MM's book in the first place - might not
grok it immediately.

Once grokked, however, it is a perfectly sensible way to do the job, for
the usual reasons.

[Kelsey Bjarnason]

[snips]

On Sat, 18 Aug 2007 22:08:12 +0100, Malcolm McLean wrote:

>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.

Do you see Dann or Ben using ints when size_t is the correct tool to be
used, defending this on the basis that they don't want to code in C and
that, in effect, C should be changed to suit their weird - and objectively
wrong - views?

No, you don't. They have bugs. You have concept failures *plus* bugs.
All non-trivial code has bugs. Code written by people who don't know what
they're doing has bugs *plus* assorted other issues. You never did, for
example, explain the magic values used by squnch, or what magic occurs
when it is passed length values of -1, -137 or -32767. Nor did you
explain how to make it work on a perfectly legitimately-sized buffer
too large to have its size specified by a signed int.

Their code has bugs, so does yours. Yours adds in umpteen different sorts
of unpredictabilit y and confusion, without justification.

[Keith Thompson]

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

"Flash Gordon" <sp**@flash-gordon.me.ukwro te in message
news:62******** ****@news.flash-gordon.me.uk...

>>>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 objection to

ptr = malloc(sizeof *ptr);

is purely syntactical. As Keith said, if sizeof were spelt $ and given
normal operator rules for whitespace

ptr = malloc($*ptr);

would be OK. The * wouldn't look like multiplication of an identifier.

As I said, if you really think it's such a problem, you *can* put
partentheses around the operand:

ptr = malloc(sizeof(* ptr));

Do you have any objection, "syntactica l" or otherwise, to that form?

--
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"

[Malcolm McLean]

"Keith Thompson" <ks***@mib.orgw rote in message
news:ln******** ****@nuthaus.mi b.org...

As I said, if you really think it's such a problem, you *can* put
partentheses around the operand:

ptr = malloc(sizeof(* ptr));

Do you have any objection, "syntactica l" or otherwise, to that form?

I prefer it. It is not uncommon to malloc more than one data item.

so ptr = malloc( N * sizeof *ptr);

if less clear than
ptr = malloc(N * sizeof(*ptr));

unless you are one of those people who likes to put the test in the line

if( ptr = malloc(N * sizeof(*ptr)) );

then some compilers like

if( (ptr = malloc(N * sizeof(*ptr))) )

at which point we've broken the rule of three and lost readbility.

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