Path: csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.programming
Subject: Re: whats good to read on programming
Date: Sat, 12 Mar 2016 20:23:54 +0000
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <87fuvva1id.fsf@bsb.me.uk>
References: <81196e67-2d91-4168-9064-dd505f2b358e@googlegroups.com> <874mcbbj8v.fsf@bsb.me.uk> <4ff2abe7-9e40-4107-9d37-f227fab27b43@googlegroups.com> <87r3ffa2mz.fsf@bsb.me.uk> <b85aff37-78f2-4216-b8e0-80c0bcf8ac6b@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="6111"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19qVH7ottYZ45nRrIy5HpODumQaE/J0w3Q="
Cancel-Lock: sha1:24B16OTf7fJui/zHl4QPz3Y+HLY= sha1:8o2ICxRa0RBH018DPNyqvvji364=
X-BSB-Auth: 1.196e9420a115a2a3a8c3.20160312202354GMT.87fuvva1id.fsf@bsb.me.uk
Xref: csiph.com comp.programming:6354

fir <profesor.fir@gmail.com> writes:

<snip>
> here it is
>
>>>Even by our loose definition of ``word'', the Bible has only 29,131
>>> distinct words. We'll follow the old lore of using
> a prime number near that for our hash table size, and the popular multiplier of 31:
> #define NHASH 29989
> #define MULT 31
> nodeptr bin[NHASH];
> Our hash function maps a string to a positive integer less than NHASH:
>
> unsigned int hash(char *p)
>  unsigned int h = 0
>  for ( ; *p; p++)
>  h = MULT * h + *p
>  return h % NHASH
>
> Using unsigned integers ensures that h remains positive<<
>
> is this a perfect hashing - i mean separate words will point to
> separate array entries? this is unclear to me

The answer depends on the words.  It's possible that it is perfect for
some very specific edition of Bible (wven changing one hyphenated word
might make the difference between it being perfect and not) but I doubt
it very much.

But that's a technical quibble.  The code assumes that it isn't and
handles the expected cases where hash(a) == hash(b) but a != b.  The
code should work (albeit a bit slower) if the table were were smaller
than the total number of words.

(You might consider editing the quoted material in your replies.)

-- 
Ben.