Examples of Hash Functions: Journey to the Center of the Algorithm

A hash function deterministically transforms data of arbitrary size into a fixed-length output called a hash or a digest. It is effectively a one-way function, meaning it is virtually impossible to guess the input once you see the hash. You can see some real-life hashes in Omni's hash identifier.

For more theory, visit a dedicated page on how hash functions work. In this article, to develop a better intuition about hash functions, we will discuss a wide range of examples:

• Simple examples of hash functions using multiplication and division;
• Creative examples of a hashing function using middle digits and the golden ratio;
• Real-life examples of hash functions for strings; and
• Examples of cryptographic hashing functions.

The division and multiplication methods are based on the modulo operation.

Division method

The hash is computed as the remainder of the key divided by a prime number, that is:

hash(n) = n (mod m)

where:

• n is the input; and
• m is the size of the hash table.

The fact that m is a prime number helps us minimize clustering of hashes and prevent collisions.

Multiplication method

First, we multiply the input by a fixed constant A where 0 < A < 1. From the result, we retain only the fractional part, which we then multiply by the table size and finally round down to the nearest integer. Formally that’s:

hash(n) = floor(m ⋅ (n ⋅ A mod 1))

where:

• A is a fixed real constant;
• x mod 1 denotes the fractional part of x; and
• floor( ) denotes floor division — rounding down to the nearest integer.

Although it looks more complex than the division method, the elegance here is that no division by m is required.

Let us discuss some slightly less obvious formulas for hash functions.

Mid-Square method

The hash is computed as the middle digits of the squared input:

hash(n) = middle_digits(n²)

Let us see an example. Suppose we want a hash table of size 100, so we want hashes that are 2 digits long. Assume the input is 37:

1. Square the input: 37² = 1369
2. Take the middle two digits: 36
3. The hash value 36 now serves as the index in the table.

It is easy to extract the middle two digits from a four-digit number, but what if the key is 111, meaning it squares to 12321? The algorithm must know precisely what to do when the symmetry is broken. A common convention is to shift one place to the left and extract 23 as the hash value.

Folding method

To compute the hash:

1. Divide the input into equal-sized parts (often digits or groups of bytes).
2. Add the parts together.
3. Reduce the sum to fit the hash table size by the modulo operation mod m.

As an example, suppose we have a key 123456789 and a hash table of size 100:

1. Split the key into 3-digit parts: 123, 456, 789.
2. Add the parts: 123 + 456 + 789 = 1368.
3. Reduce modulo table size: 1368 mod 100 = 68.
4. Hash value is 68.

As you can see, this method is particularly well-suited for very long keys, where taking the square would be computationally expensive.

These two hash functions work for strings and use the ASCII values along with our old buddy mod.

DJB2 method

Start with the initial hash value 5381 and follow these steps:

1. Process each character of the string one by one.
2. Multiply the current hash value by 33.
3. Add the ASCII value of the current character to the hash value.
4. Repeat Step 2 and Step 3 until you run out of string characters.
5. At the end, reduce the hash value modulo table size if needed.

Steps 2 and 3 can be summarized in the following hash update formula:

hash = hash × 33 + ASCII(char)

SDBM method

This method is a twin brother of DJB2: they follow the same philosophy. The main difference is the multiplier used and the starting value:

• The initial hash value is 0.
• We multiply the previous hash by 65599.

That is, the update formula for SDBM reads:

hash = hash × 65599 + ASCII(char)

Since cryptographic hash functions are the backbone of password storage, blockchain, file verification, and digital signatures, they must satisfy extra security requirements. If you are interested in details, check our dedicated article on cryptographic hash function properties.

As a result, cryptographic hash functions are extremely complicated. However, at their core, they still use modulo operators and bitwise logical operators. Let us discuss three examples of cryptographic hash functions. We will provide you with an overview without delving too deeply into the details.

MD5 algorithm operates on 512-bit blocks of input on which several types of calculations are repeatedly performed:

• Bitwise AND, OR, NOT, XOR;
• Modulo addition; and
• Left rotations of bits.

The resulting hash has 128 bits.

It is an example of a historic cryptographic hash function. It’s no longer safe for security purposes.

The SHA-1 algorithm returns 160 bits, but otherwise, it is similar to MD5: it also processes input in fixed-size blocks, applies rounds of bitwise operations and modular additions, and uses rotations to mix the data thoroughly.

SHA-1 has more rounds and a longer output, which originally made it more resistant to collisions than MD5. However, SHA-1 is also now deprecated.

SHA-256 produces (you won’t guess it) 256 bits and is again similar in the general structure to MD5 and SHA-1. The main differences are that SHA-256 has more rounds, a longer output, and a larger internal state, which makes it significantly stronger against collisions and preimage attacks.

SHA-256 is the current standard technology for secure hashing.

SHA-3 produces variable-length hashes (e.g., 224, 256, 384, 512 bits). It is the latest standard for very strong and secure hashing. It features a completely new design called the sponge construction, which scrambles the input in a manner different from SHA-1 or SHA-256.