Re: Extendible Hashing question

>> I noticed that they were using a technique where by they reverse
the bits of the hash value when making an address to index into the directory ... I don't see why reversing the bits should make a difference <<

The idea is that things you actually hash on tend to be in a sorted order of some kind -- sequential numbers or alpha strings that have a small set of common prefixes. Reversing a bit string or a byte gives you more variety in the "front" of the bit string and in some hardware, it is a single machine level operation.

If you want to get an idea of how this heuristic works, take a list of names, use a simple hash of some kind (first two letters or whatever), then reverse them and repeat the hash and finally grab the n-th letter in the middle and pivot the name around it (i.e. 'abcdef' => 'cdefba') and hash again. With names, the last one will be better; names tend to begin with the same few letters or words and end with common postfixes; the variety is in the middle. Received on Mon Jun 03 2002 - 15:29:00 CEST