Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6354

Re: whats good to read on programming

Show all headers | View raw

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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 08:58 -0800
  Re: whats good to read on programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 19:15 +0000
    Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 11:36 -0800
      Re: whats good to read on programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 19:59 +0000
        Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 12:07 -0800
          Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 12:19 -0800
            Re: whats good to read on programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 20:26 +0000
              Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 12:32 -0800
          Re: whats good to read on programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 20:23 +0000
    Re: whats good to read on programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 20:05 +0000
      Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 12:13 -0800
      Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 12:29 -0800
      Re: whats good to read on programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-12 22:06 +0000
        Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 15:56 -0800
    Re: whats good to read on programming Kaz Kylheku <330-706-9395@kylheku.com> - 2016-03-13 02:08 +0000
      Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-13 00:10 -0800
        Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-13 00:19 -0800
    Re: whats good to read on programming "Osmium" <r124c4u102@comcast.net> - 2016-03-13 11:24 -0600
      Re: whats good to read on programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-03-13 23:51 +0000
  Re: whats good to read on programming Mark Carroll <mtbc@bcs.org> - 2016-03-12 19:45 +0000
    Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 11:57 -0800
    Re: whats good to read on programming fir <profesor.fir@gmail.com> - 2016-03-12 11:59 -0800
    Re: whats good to read on programming Robert Wessel <robertwessel2@yahoo.com> - 2016-03-12 14:35 -0600
  Re: whats good to read on programming Randy Howard <rhoward.mx@EverybodyUsesIt.com> - 2016-03-12 14:35 -0600
  Re: whats good to read on programming Jacob Sparre Andersen <sparre@nbi.dk> - 2016-03-13 15:47 +0100

csiph-web