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

[pete]

Malcolm McLean wrote:

>
"Eric Sosman" <es*****@ieee-dot-org.invalidwrot e in message
news:o4******** *************** *******@comcast .com...

pete wrote:

I recall Eric Sosman advising me that in the case of loops,
it's probably better to write something like while((ptr = malloc(N *
sizeof *ptr) != NULL) {
/**/
}

I hope I didn't advise exactly that! (Hint: count
the parentheses.

That's th snag, isn't it. Just add a tiny bit of visual complexity and
people make errors in the expression. Not just once but twice.

Do you really want to exhaust the computer's memory? If not, the loop must
not terminate at the while() in normal flow control.
It should be

while( allocationsleft otodo() )
{
ptr = malloc(N * sizeof *ptr);
if(!ptr)
/* oh dear. take emergency action */
/* normal code */
}

The context of Eric's original advice,
was not allocation, as it is here.
The topic that I mean to address was:
assignment within a loop controling expression versus
splitting the assignment into a separate line.

--
pete

[Philip Potter]

Richard Heathfield wrote:

Malcolm McLean said:

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

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

Like others have said, I found it confusing at first, but once I had
seen it once that was all I needed. It *is* different and idiomatic and
uncommon, but it doesn't take much to learn what it means and why it is
helpful.

Compare it to other language features such as pointers, unions, and
setjmp/longjmp, which take longer to learn and longer still to use well.
Having seen this construct once, one can use it successfully.

Phil

--
Philip Potter pgp <atdoc.ic.ac. uk

[Philip Potter]

Malcolm McLean wrote:

>
"Ben Bacarisse" <be********@bsb .me.ukwrote in message
news:87******** ****@bsb.me.uk. ..

>Yes, he does. I missed that. Quadratic probing is usually explained
as inspecting

h(k, i) = h(k) + c1 * i + c2 * i * i

for i = 0, 1 and so on. When c2 == 0 you have linear probing. I have
never seen the term used in the way MM uses it. Squaring the hash
looks like a bad idea, at least on the surface. I wonder if he has
any data about the advantages and disadvantages of doing so.

I've misunderstood the algorithm and invented something better. (I
think). I'm using the square of the hash value modulus table size as an
increment. So effectively it's secondary hashing and not quadratic
probing at all.

I honestly can't believe you just said this. Hashing functions and
algorithms, like random number generators, are not to be guessed at, and
intuitively inspected for quality. If you're going to say "I think I've
invented something better" you ought to have some sort of evidence to
back this up!

Phil

--
Philip Potter pgp <atdoc.ic.ac. uk

[websnarf]

On Aug 18, 7:50 am, "Malcolm McLean" <regniz...@btin ternet.comwrote :

"Ben Bacarisse" <ben.use...@bsb .me.ukwrote in message

Yes, he does. I missed that. Quadratic probing is usually explained
as inspecting

h(k, i) = h(k) + c1 * i + c2 * i * i

for i = 0, 1 and so on. When c2 == 0 you have linear probing. I have
never seen the term used in the way MM uses it. Squaring the hash
looks like a bad idea, at least on the surface. I wonder if he has
any data about the advantages and disadvantages of doing so.

I've misunderstood the algorithm and invented something better. (I think).
I'm using the square of the hash value modulus table size as an increment.
So effectively it's secondary hashing and not quadratic probing at all.

As pointed out by Philip Potter, you can't be so cavalier about such
things. If the index is 0 or 1, then squaring it is going to give you
0 and 1 as the new index all the time. Furthermore, depending on the
table size, you can get all sorts of "short cycles". For example 2*2
== 4 (mod 7) and 4*4 == 16 == 2 (mod 7). So 2 and 4 just cycle back
and forth in a table of sized 7.

While that analysis from academia (specifically Knuth, but others
reproduce it) is not very generally applicable to *real world* hashing
(i.e., hashing keys/objects which are *not* integers) under their
assumptions this analysis is fairly thorough. Also the quadratic
probing technique has the advantage that you can compute the offsets
quickly using finite differences. (Your self-squaring technique,
requires the multiplier anyways, which has only very recently become
fast in all CPUs.)

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

[CBFalconer]

Malcolm McLean wrote:

>

.... snip ...

>
while( allocationsleft otodo() )
{
ptr = malloc(N * sizeof *ptr);
if(!ptr)
/* oh dear. take emergency action */
/* normal code */
}

Simpler, more readable, and more direct, is:

while (allocationslef totodo()) {
if (!(ptr = malloc(N * sizeof *ptr))) {
/* oh dear. take emergency action */
}
else {
/* all well, take normal action */
}
}

which also allows eliding of the else to allow for 'emergency
action' making 'normal action' feasable. Note that the key event
is the success or failure of the malloc, and the structure makes
that evident. There is no searching to discover what the state of
ptr represents.

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

[CBFalconer]

Keith Thompson wrote:

Ed Jensen <ej*****@visi.c omwrites:

>Keith Thompson <ks***@mib.orgw rote:

.... snip ...

>>>
if ((ptr = malloc(N * sizeof *ptr) != NULL) ...

I'd probably just put the test on a separate line.

Good idea, since your one liner would fail to compile.

D'oh! Thanks for the correction:

if ((ptr = malloc(N * sizeof *ptr)) != NULL) ...

However this is a non-critical typo, since the compiler will always
catch it. The nuisance is when there are multiple such and the
compiler stops on the first error.

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

<we******@gmail .comwrote in message
news:11******** *************@q 4g2000prc.googl egroups.com...

On Aug 18, 7:50 am, "Malcolm McLean" <regniz...@btin ternet.comwrote :

>"Ben Bacarisse" <ben.use...@bsb .me.ukwrote in message

Yes, he does. I missed that. Quadratic probing is usually explained
as inspecting

h(k, i) = h(k) + c1 * i + c2 * i * i

for i = 0, 1 and so on. When c2 == 0 you have linear probing. I have
never seen the term used in the way MM uses it. Squaring the hash
looks like a bad idea, at least on the surface. I wonder if he has
any data about the advantages and disadvantages of doing so.

I've misunderstood the algorithm and invented something better. (I
think).
I'm using the square of the hash value modulus table size as an
increment.
So effectively it's secondary hashing and not quadratic probing at all.

As pointed out by Philip Potter, you can't be so cavalier about such
things. If the index is 0 or 1, then squaring it is going to give you
0 and 1 as the new index all the time. Furthermore, depending on the
table size, you can get all sorts of "short cycles". For example 2*2
== 4 (mod 7) and 4*4 == 16 == 2 (mod 7). So 2 and 4 just cycle back
and forth in a table of sized 7.

It doesn't work like that.
The index returned from the hash is squared, made modulus table size, and
used as a linear probe increment. It's effectively secondary hashing where
function 2 is hash 1, squared. It does a reasonable job of busting clusters,
since apart from the first few keys are scattered all over the place.
However I should square the hash, not the index, to get a truly distributed
secondary hash. As it is collisions will create chains of collisions.
It was an accident, anyway.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[websnarf]

On Aug 20, 1:15 pm, "Malcolm McLean" <regniz...@btin ternet.comwrote :

<websn...@gmail .comwrote in message
news:11******** *************@q 4g2000prc.googl egroups.com...

On Aug 18, 7:50 am, "Malcolm McLean" <regniz...@btin ternet.comwrote :

"Ben Bacarisse" <ben.use...@bsb .me.ukwrote in message
Yes, he does. I missed that. Quadratic probing is usually explained
as inspecting

h(k, i) = h(k) + c1 * i + c2 * i * i

for i = 0, 1 and so on. When c2 == 0 you have linear probing. I have
never seen the term used in the way MM uses it. Squaring the hash
looks like a bad idea, at least on the surface. I wonder if he has
any data about the advantages and disadvantages of doing so.

I've misunderstood the algorithm and invented something better. (I
think). I'm using the square of the hash value modulus table size as an
increment. So effectively it's secondary hashing and not quadratic probing
at all.

As pointed out by Philip Potter, you can't be so cavalier about such
things. If the index is 0 or 1, then squaring it is going to give you
0 and 1 as the new index all the time. Furthermore, depending on the
table size, you can get all sorts of "short cycles". For example 2*2
== 4 (mod 7) and 4*4 == 16 == 2 (mod 7). So 2 and 4 just cycle back
and forth in a table of sized 7.

It doesn't work like that.
The index returned from the hash is squared, made modulus table size, and
used as a linear probe increment.

Well, 0*0 == 0, so you still have a problem. Also this does nothing
special about the general problems that linear probes have then.

Ok, so lets think about this again using the examples I showed above.
Table size of 7, on offsets 2 and 4. If you land on offset 2, then
you will skip in steps of 4. If you land of offset 4 you will go in
steps of 2. In both cases, 2+4 = 4+2 = 6, so they both collide with
their first probe. Furthermore, 2+4+4 = 3 (mod 7) and 4+2+2+2 = 3
(mod 7) so again they collide. Sorry but no, this is a terrible
strategy.

[...] It's effectively secondary hashing where
function 2 is hash 1, squared. It does a reasonable job of busting clusters,
since apart from the first few keys are scattered all over the place.

This is not analysis. Try doing some math, or collecting real data to
back up your claim. I am almost certain that this is actually an
unusually *BAD* strategy -- even worse than CBFalconer's "just hash it
again, and mask it down to a quarter the size" kind of strategy.

However I should square the hash, not the index, to get a truly distributed
secondary hash. As it is collisions will create chains of collisions.
It was an accident, anyway.

Well this fixes one anomaly (the same chain sequence always coming out
of the same slot) bit it does not settle the other standard numeric
collision anomaly (stepping on each other just due to a lack of
coprimality of the two chains).

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

[Ben Bacarisse]

we******@gmail. com writes:

On Aug 18, 7:50 am, "Malcolm McLean" <regniz...@btin ternet.comwrote :

>"Ben Bacarisse" <ben.use...@bsb .me.ukwrote in message

Yes, he does. I missed that. Quadratic probing is usually explained
as inspecting

h(k, i) = h(k) + c1 * i + c2 * i * i

for i = 0, 1 and so on. When c2 == 0 you have linear probing. I have
never seen the term used in the way MM uses it. Squaring the hash
looks like a bad idea, at least on the surface. I wonder if he has
any data about the advantages and disadvantages of doing so.

I've misunderstood the algorithm and invented something better. (I think).
I'm using the square of the hash value modulus table size as an increment.
So effectively it's secondary hashing and not quadratic probing at all.

As pointed out by Philip Potter, you can't be so cavalier about such
things.

Quite.

If the index is 0 or 1, then squaring it is going to give you
0 and 1 as the new index all the time. Furthermore, depending on the
table size, you can get all sorts of "short cycles". For example 2*2
== 4 (mod 7) and 4*4 == 16 == 2 (mod 7). So 2 and 4 just cycle back
and forth in a table of sized 7.

That is not what is done. I don't know if what he does is better or
worse than that, but it is in effect using (idx * idx) % size as an
_increment_ (with 0 mapped to 1) -- similar to basic linear probing.
The % size is pointless (since the he repeats the reduction to do the
index operation after adding the increment) and I specifically say idx
rather hash because what gets used is the index that has caused the
collision, not the full hash of the key.

As I understand it, most linear probing schemes that use an increment
other than 1, choose one based on the full hash (or even another hash)
so as to avoid generating the same sequence of probes for all elements
that map a particular initial index.

Of course, there may be some curious reason why this form of linear
probing *is* a good idea in practice, but it certainly looks bad on
paper and it most definitely is *not* quadratic probing as promised in
the text.

--
Ben.

[CBFalconer]

Julienne Walker wrote:

"Malcolm McLean" <regniz...@btin ternet.comwrote :

>>>However can you point to a better introductory web page on hash
tables? That's the real test.

>><snip>

>>Personally, I like this:
http://eternallyconfuzzled.com/tuts/..._tut_hashtable....
When the twisted minds of Julienne Walker and The EC Team get
together and write a book, I will buy a copy for sure.

It is a good description. The writing is rather dry and my car
park metaphor is more interesting.

Piggybacking. Take a look at my hashlib.zip, written in purely
standard C and totally portable. GPL licenced. See:

<http://cbfalconer.home .att.net/download/>

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