10.3. Sample Hash Functions — CS3 Data Structures & Algorithms (2024)

10.3.1.1. Simple Mod Function¶

Consider the following hash function used to hash integers to a tableof sixteen slots.

 int h(int x) { return x % 16; }

 int h(int x) { return x % 16; }

Here “%” is the symbol for the mod function.

Recall that the values 0 to 15 can be represented with four bits(i.e., 0000 to 1111).The value returned by this hash function depends solely onthe least significant four bits of the key.Because these bits are likely to be poorly distributed(as an example, a high percentage of the keys might be even numbers,which means that the low order bit is zero),the result will also be poorly distributed.This example shows that the size of the table \(M\)can have a big effect on the performance of a hash system because the table sizeis typically used as the modulus to ensure that the hashfunction produces a number in the range 0 to \(M-1\).

10.3.1.2. Binning¶

Say we are given keys in the range 0 to 999, and have a hash table ofsize 10.In this case, a possible hash function might simply divide the keyvalue by 100.Thus, all keys in the range 0 to 99 would hash to slot 0, keys 100 to199 would hash to slot 1, and so on.In other words, this hash function “bins” the first 100 keys to thefirst slot, the next 100 keys to the second slot, and so on.

Binning in this way has the problem that it will clustertogether keys if the distribution does not divide evenly on thehigh-order bits.In the above example, if more records have keys in the range 900-999(first digit 9) than have keys in the range 100-199(first digit 1), more records will hash to slot 9 than to slot 1.Likewise, if we pick too big a value for the key range and the actualkey values are all relatively small, then most records will hash toslot 0.A similar, analogous problem arises if we were instead hashing strings basedon the first letter in the string.

In general with binning we store the record with key value \(i\)at array position \(i/X\) for some value \(X\)(using integer division).A problem with Binning is that we have to know the key range so thatwe can figure out what value to use for \(X\).Let’s assume that the keys are all in the range 0 to 999.Then we want to divide key values by 100 so that the result is in therange 0 to 9.There is no particular limit on the key range that binning couldhandle, so long as we know the maximum possible value in advance sothat we can figure out what to divide the key value by.Alternatively, we could also take the result of any binningcomputation and then mod by the table size to be safe.So if we have keys that are bigger than 999 when dividing by 100, wecan still make sure that the result is in the range 0 to 9 with a modby 10 step at the end.

Binning looks at the opposite part of the key value from the modfunction.The mod function, for a power of two, looks at the low-order bits,while binning looks at the high-order bits.Or if you want to think in base 10 instead of base 2, modding by 10 or100 looks at the low-order digits, while binning into an array of size10 or 100 looks at the high-order digits.

As another example, consider hashing a collection of keys whose valuesfollow a normal distribution, as illustrated byFigure 10.3.1.Keys near the mean of the normal distribution are far more likelyto occur than keys near the tails of the distribution.For a given slot, think of where the keys come from within the distribution.Binning would be taking thick slices out of the distribution and assignthose slices to hash table slots.If we use a hash table of size 8, we would divide the key range into 8equal-width slices and assign each slice to a slot in the table.Since a normal distribution is more likely to generate keys fromthe middle slice, the middle slot of the table is most likely to be used.In contrast, if we use the mod function, then we are assigning to any givenslot in the table a series of thin slices in steps of 8.In the normal distribution, some of these slices associated with any givenslot are near the tails, and some are near the center.Thus, each table slot is equally likely (roughly) to get a key value.

10.3.1.3. The Mid-Square Method¶

A good hash function to use with integer key values is themid-square method.The mid-square method squares the key value, and then takes out the middle\(r\) bits of the result, giving a value in the range0 to \(2^{r}-1\).This works well because most or all bits of the key value contribute tothe result.For example, consider records whose keys are 4-digit numbers in base10, as shown in Figure 10.3.2.The goal is to hash these key values to a table of size 100(i.e., a range of 0 to 99).This range is equivalent to two digits in base 10.That is, \(r = 2\).If the input is the number 4567, squaring yields an 8-digit number,20857489.The middle two digits of this result are 57.All digits of the original key value(equivalently, all bits when the number is viewed in binary)contribute to the middle two digits of the squared value.Thus, the result is not dominated by the distribution of the bottomdigit or the top digit of the original key value.Of course, if the key values all tend to be small numbers,then their squares will only affect the low-order digits of the hash value.

Here is a little calculator for you to see how this works.Start with ‘4567’ as an example.

• Java
• C++

 int sascii(String x, int M) { char ch[]; ch = x.toCharArray(); int i, sum; for (sum=0, i=0; i < x.length(); i++) { sum += ch[i]; } return sum % M; }

 int sascii(String x, int M) { char ch[]; ch = x.toCharArray(); int i, sum; for (sum=0, i=0; i < x.length(); i++) sum += ch[i]; return sum % M; }

• Java
• C++

// Use folding on a string, summed 4 bytes at a timeint sfold(String s, int M) { long sum = 0, mul = 1; for (int i = 0; i < s.length(); i++) { mul = (i % 4 == 0) ? 1 : mul * 256; sum += s.charAt(i) * mul; } return (int)(Math.abs(sum) % M);}

// Use folding on a string, summed 4 bytes at a timeint sfold(String s, int M) { long sum = 0, mul = 1; for (int i = 0; i < s.length(); i++) { mul = (i % 4 == 0) ? 1 : mul * 256; sum += s.charAt(i) * mul; } return (int)(Math.abs(sum) % M);}