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 19:59:32 +0000
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <87r3ffa2mz.fsf@bsb.me.uk>
References: <81196e67-2d91-4168-9064-dd505f2b358e@googlegroups.com> <874mcbbj8v.fsf@bsb.me.uk> <4ff2abe7-9e40-4107-9d37-f227fab27b43@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="32177"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+qzN0KsG/KDEiN59JCho1wnHEMYyLjFYk="
Cancel-Lock: sha1:oOBppOlU5uO9fOkU5iJmHBpFAvY= sha1:6/QcC7utegRBqP8/i/vJsMEzN78=
X-BSB-Auth: 1.88b2f37e4cc8be977062.20160312195932GMT.87r3ffa2mz.fsf@bsb.me.uk
Xref: csiph.com comp.programming:6349

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

> W dniu sobota, 12 marca 2016 20:15:30 UTC+1 użytkownik Ben Bacarisse napisał:
<snip>
>> These may seem a bit dated since I read them quite some time ago, but I
>> think my favourite books on programming are the pair of collected CACM
>> columns by Jon Bentely: "Programming Pearls" and "More Programming
>> Pearls".  I see there is a new edition of the first with new
>> material...
>
> well indeed this seems good compact style writting - i readed the
> first piece on counting words
>
> links here
> https://tfetimes.com/wp-content/uploads/2015/04/ProgrammingPearls2nd.pdf
>
> can somebody explain me - is this hashing in c version perfect one? i
> mean it counts with no mistakes? if so why?

The program in the book makes no mistakes because the table does not
rely only on the hash function.

> (i know the idea of
> hashing but its inperfection always keeps me away - is there reliable
> way of perfect hashing on cases like that?

Perfect hashing is a technical term for something rarely seen.  When you
want to do a lot of lookups from a fixed set of keys very fast, you can
construct a function that maps the set of n keys to the numbers 0 to n-1
in such a way that every key maps to a distinct number (i.e. the
function is a bijection).  This is called a perfect hash function.

Normal hashing works by handling the collisions, so the case where two
keys hash to the same value does not produce an error.  There are many
ways to do this.  The Bentley book uses a linked list, I think.

-- 
Ben.