Hash Functions C/C++ Help

A hash function. h. transforms an identifier into a bucket address in the hash table. As mentioned earlier. the desired properties of I such a function are that it be easy to compute, and that it minimize the nor of collision i. k function such as the one discussed earlier is not a very good choice for a hash function for symbol tables. even though it is easy 10 compute. The reason for this is that ,the function depends only on the first character in the identifier. Since many programs use several identifiers with the same first letter, we expect several collisions to occur general then. we would like the function.to depend upon all the chapters in the identifiers. In, addition. we would like the hash function to ·be such that it does not result in a biased use of the hash table for random inputs; i.e., if x is an identifier chosen at random from the identifier space. then we want the probability that II (x)  i 10 be lib for all buckets i. Then a random x has an equal chance of hashing into any of the b buckets. A hash function satisfying this property will be called a uniform  function.

Several kinds of uniform, hash functions are in use. We shall describe four of those.


Internal representations of x and x2 in octal notation (x is input right justified, zero-filled, six bits or two octal digits per character) represented by six bits, and identifiers are stored right justified in I C§O..but word with leading bits filled with zeros, then with M .2′, i $ 6. the identifiers AI. 81. CI, X 41 DNTXY1, etc., all have the same bucket address. With 11.2′. IS 12. the identifiers AXY, BXY..WTXY, etc., have the same bucket address.

As a result of this observation. we see that when the division function is used as a hash function, the table size should not be- a power of two, whereas when the mid-square function hm is used, the table size is a power of two.

If M is divisible by two, then odd keys are mapped to odd buckets (as the remainder is odd), and even keys are mapped to even buckets. The use of the hash table is thus biased.

Let x = x, X2 and y = x zx, be two identifiers, each consisting of the characters x, and x:. If the internal binary representation of x, has value C(x) ), and that for x 2 has value C IX2). then if each character is represented by six bits, the numeric value of .r is 26C(x,) + C (x 1), and that for y is 26C(x 2) + C (x d. If p is a prime number that divides M, then:

That is, permutations of the same set of characters are hashed at a distance a multiple of three apart. Programs in which many variables are permutations of each other would again result in a biased use of the table and hence result in many collisions. This happens because 64 % 3 = 1. The same behavior can be expected when 7 divides M, as 64 %7=1.

These difficulties can be avoided by making M a prime number. Then, the only factors of Mare M and 1. Donald Knuth has shown that when M divides rk ± a, where k and a are small numbers and r is the radix of the character set (in the example above r = (4), then x % M tends to be a simple superposition of the characters in .r. Thus, a prime number such” that M does not divide rk ± a for small k and a would be a good choice for M. We shall see other reasons for choosing M as a prime number. In practice it has been observed that it is sufficient to choose M such .that it has no prime divisors less than 20.


In this method the identifier x is partitioned ‘into several parts, all but possibly the last being of the same length. These partitions are then added together to obtain the hash address for x. There are two ways of carrying out this addition. In the first, all but the last partition are shifted so that the least significant bit of each line-s up with the corresponding bit s>f. the last partition .. The different partitions are now added together to get h (x). This method is known as shift folding. In the second method,folding at the boundaries, the identifier is folded at the partition boundaries, and digits falling into the same position are added together to obtain h (x). This is equivalent to reversing every other partition and then adding.


Suppose that x = 12320324111220, and we partition it into parts that are three decimal digits long. The partitions are PI = 123, P 2 = 203, P 3 = 241, P 4 = 112, and P.5 = 20. Using shift folding, we obtain.

When folding at the boundaries is used, we first reverse P2 and P4 to obtain 302 and 211, respectively. Next, the five partitions are added to obtain h (x) = 123 + 302 + 241 + 21 I + 20 = 897.

Digit Analysis

This method is particularly useful in the case of a static file where all the identifiers in the table are known in advance. Each identifier x is interpreted as a number using some radix r. The same radix is used for all the identifiers in the table. Using this radix, the digits of each identifier are examined. Digits having the most skewed distributions are deleted. Enough digits are deleted so that the number of remaining digits is small enough to give an address in the range of the hash table.

we compare the various methods used to generate a hash address. Of these methods, the one most suitable for general-purpose applications is the division method with a divisor, M, such that M has no prime factors less than 20.

Posted on November 12, 2015 in Hashing

Share the Story

Back to Top
Share This