Hashing: Hash Function

A hash functionA hash function exists within the context of hashing and hash tables. Data to be stored in hash tables includes a unique attribute (id number, username, etc.). Hash functions take the unique attribute and translate it into a hash index. Most algorithms take a numerical value as input, so if your unique attribute is text-based, translate your text into a... exists within the context of hashingA hash table (sometimes also called a hash map) is a data structure that is useful in situations when: you need very quick insertion and retrieval, you very rarely need to iterate over all your items, you don't care what order the items are stored (they don't need to be sorted, etc.), and the data you want to store has... and hash tables. Data to be stored in hash tables includes a unique attribute (id number, username, etc.). Hash functions take the unique attribute and translate it into a hash indexA hash index is an index into the underlying array that supports a hash table. A hash index is determined by a hash function..... Most algorithms take a numerical value as input, so if your unique attribute is text-based, translate your text into a numerical value before sending it to a  hash function.

These are a few popular hash functions:

  • Remainder Method – This is the basis for nearly all hash functions. Simply perform a modulus operation on the numerical value with the size of the array. So if the numerical value was 214 and the array size was 23, you would perform 214 % 23, which equals 7. So, 7 is your hash index. It’s that simple!
  • Multiplicative Method – This method is similar to the remainder method but can help translate smaller numerical values into a larger index space. So, if your numerical value was 214 and the array size was 2,000, you could multiply your numerical value by some (large and prime) constant, let’s say 197 before performing your modulus. So you would have (214 * 197) % 2000, which reduces to 42158 % 2000, which equals 158. So, 158 is your hash index with the multiplicative method.
  • Folding Method – This method has the opposite benefit as the multiplicative method. It takes very large numerical values and translates them into smaller numbers. Basically, you can split your numerical value into “folds” of x digits, where x is some small integer. Let’s say your unique numerical value is 86,940,285. You can split that number into folds of 2, resulting in the collection of smaller numbers 86, 94, 02, and 85. You sum those numbers together to get 267. Then you would perform your modulus (are you getting that the modulus step is important for every hash function?) by the array size (let’s say it’s 53). So 267 % 53 = 2. Your hash function would return a hash index of 2.
Posted in