From: Hans-Bernhard Broeker <broeker AT physik DOT rwth-aachen DOT de>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Hash function
Date: 5 Feb 2001 14:18:43 GMT
Organization: Aachen University of Technology (RWTH)
Lines: 29
Message-ID: <95mco3$qda$1@nets3.rz.RWTH-Aachen.DE>
References: <95cfee$m9h$1 AT venus DOT telepac DOT pt>
NNTP-Posting-Host: acp3bf.physik.rwth-aachen.de
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: nets3.rz.RWTH-Aachen.DE 981382723 27050 137.226.32.75 (5 Feb 2001 14:18:43 GMT)
X-Complaints-To: abuse AT rwth-aachen DOT de
NNTP-Posting-Date: 5 Feb 2001 14:18:43 GMT
Originator: broeker@
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

"Frederico Jerónimo" <DarkRealms AT netcabo DOT pt> wrote:
> Hi all,

>     I have a hash function that given a 20 bit entry (A19-A0) , returns a 11
> bit number composed of the most significant bit (A19), bit A13 and the
> remaining least significant bits (bit A0-A8).

>     Ex : Given 0x8ae29 the function would return 0x629

>     I know this is not a very efficient hash function so I was wondering if
> anyone has any ideas for a better one. Thanks in advance,

Do what the word 'hashing' actually means: take your value into small
pieces, mix those thoroughly, and cook the result down into as many
bits as you need. The more thorough the mixing, the better, usually.
Xor'ing parts of the numbers together, or using a CRC algorithm are
often good first tries. To reduce 20 bits into 11, you could, e.g.:

	elevenbits = (input & (1<<19)) >> 8
	             | (input % (1<<10) ^ ((input >> 10) % (1<<10)))

I.e.: keep A19 as the new A10, and Xor A0..A9 with A10..A19 as the new
bits A0 to A9. That's just one out of a vast range of possible
choices, of course.


-- 
Hans-Bernhard Broeker (broeker AT physik DOT rwth-aachen DOT de)
Even if all the snow were burnt, ashes would remain.