Hash Functions

In the previous example, we determined a hash value by examining the remainder after division. In this section we'll examine several algorithms that compute a hash value.

Division Method (TableSize = Prime)

A hash value, from 0 to (HashTableSize - 1), is computed by dividing the key value by the size of the hash table and taking the remainder:

Public Function Hash(ByVal Key As Long) As Long
    Hash = Key Mod HashTableSize
End Function

Selecting an appropriate HashTableSize is important to the success of this method. For example, a HashTableSize divisible by two would yield even hash values for even keys, and odd hash values for odd keys. This is an undesirable property, as all keys would hash to even values if they happened to be even. If HashTableSize is a power of two, then the hash function simply selects a subset of the key bits as the table index. To obtain a more random scattering, HashTableSize should be a prime number not too close to a power of two.

Multiplication Method (TableSize = 2ⁿ)

The multiplication method may be used for a HashTableSize that is a power of 2. The Key is multiplied by a constant, and then the necessary bits are extracted to index into the table. One method uses the fractional part of the product of the key and the golden ratio, or (sqrt(5) - 1)/2. For example, assuming a word size of 8 bits, the golden ratio is multiplied by 28 to obtain 158. The product of the 8-bit key and 158 results in a 16-bit integer. For a table size of 25, the 5 most significant bits of the least significant word are extracted for the hash value. The following definitions may be used for the multiplication method:

' 8-bit index
Private Const K As Long = 158

' 16-bit index
Private Const K As Long = 40503

' 32-bit index
Private Const K As Long = 2654435769

' bitwidth(index)=w, size of table=2^m
Private Const S As Long = 2^(w - m)
Private Const N As Long = 2^m - 1
Hash = ((K * Key) And N) \ S

For example, if HashTableSize is 1024 (2¹⁰), then a 16-bit index is sufficient and S would be assigned a value of 2^{(16 - 10)} = 64. Constant N would be 2¹⁰ - 1, or 1023. Thus, we have:

Private Const K As Long = 40503
Private Const S As Long = 64
Private Const N As Long = 1023

Public Function Hash(ByVal Key As Long) As Long
    Hash = ((K * Key) And N) \ S
End Function

Variable String Addition Method (TableSize = 256)

To hash a variable-length string, each character is added, modulo 256, to a total. A hash value, range 0–255, is computed.

Public Function Hash(ByVal S As String) As Long
    Dim h As Byte
    Dim i As Long
    
    h = 0
    For i = 1 to Len(S)
        h = h + Asc(Mid(S, i, 1))
    Next i
    Hash = h
End Function

Variable String Exclusive-Or Method (TableSize = 256)

This method is similar to the addition method, but successfully distinguishes similar words and anagrams. To obtain a hash value in the range 0–255, all bytes in the string are exclusive-or'd together. However, in the process of doing each exclusive-or, a random component is introduced.

Private Rand8(0 To 255) As Byte

Public Function Hash(ByVal S As String) As Long
    Dim h As Byte
    Dim i As Long

    h = 0
    For i = 1 To Len(S)
        h = Rand8(h Xor Asc(Mid(S, i, 1)))
    Next i
    Hash = h
End Function

Rand8 is a table of 256 8-bit unique random numbers. The exact ordering is not critical. The exclusive-or method has its basis in cryptography, and is quite effective.

Variable String Exclusive-Or Method (TableSize <= 65536)

If we hash the string twice, we may derive a hash value for an arbitrary table size up to 65536. The second time the string is hashed, one is added to the first character. Then the two 8-bit hash values are concatenated together to form a 16-bit hash value:

Private Rand8(0 To 255) As Byte

Public Function Hash(ByVal S As String) As Long
    Dim h1 As Byte
    Dim h2 As Byte
    Dim c As Byte
    Dim i As Long

    if Len(S) = 0 Then
        Hash = 0
        Exit Function
    End If

    h1 = Asc(Mid(S, 1, 1))
    h2 = h1 + 1
    For i = 2 To Len(S)
        c = Asc(Mid(S, i, 1))
        h1 = Rand8(h1 Xor c)
        h2 = Rand8(h2 Xor c)
    Next i

    ' Hash is in range 0 .. 65535
    Hash = (h1 * 256) + h2
    ' scale Hash to table size
    Hash = Hash Mod HashTableSize
End Function