Three (somewhat) Better Functions (Hash functions, part V)


Last week’s hash functions—the check-sum, Knuth’s, and gray—produced less than optimal results. A function based only on addition, such as the check-sum, cannot possibly produce very large numbers, and therefore fails to distribute item over a very large table. That’s why there’s a confusion step following the combination step, to spread the bits around the (machine-sized) word.

So the confusion step must explicitly shuffle the bits around (although, not necessarily a permutation) and make sure that the most- and least-significant bits gets thrown around. Let’s try a couple of things!

Read the rest of this entry »

Three bad functions (Hash functions, part IV)


Devising a good, fast, simple hash function isn’t easy. At all. It’s quite the challenge, in fact. Unsurprisingly, the first tries will be somewhat disappointing, but that shouldn’t keep you from trying. This week, let’s consider a couple of simple (and not very good) functions.

Read the rest of this entry »

Testing Hash functions (Hash functions, part III)


So, this week, let’s have a look at how we will test hash functions. Testing is necessary since it’s not because your hash function looks random that it is sufficiently random to be used for look-up.


Read the rest of this entry »

The anatomy of hash functions (Hash functions, part II)


Before we go on exploring hash functions for look-up, let’s discuss their basic anatomy. This will give us some vocabulary as well as help us identify what are the important characteristics of good hash functions.


Read the rest of this entry »