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

October 27, 2015

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)

October 20, 2015

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)

October 13, 2015

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.

stethoscope-small

Read the rest of this entry »


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

October 6, 2015

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.

the-anatomy-lesson-small

Read the rest of this entry »