Hash tables are used as an exact matching algorithm. For example, forwading tables (MAC address tables) in software use a hash table.

Hash functions map a bit string in a data space to a bit string in another data space. For example, MAC addresses are in a 48-bit address space, but MAC address tables generally store up to 16k entries (about 14-bit space) for the Ethernet switching functionality. Thus, the 48-bit vast space can be compressed to a 14-bit narrow space using a hash function.

Some hash functions are used for one-way encryption, such as password hashing and verification. However, a hash function for hash tables is not necessary to be a cryptographic hash function as it has mechanisms such as a linked list or linear probing to arbitrate collisions of hash values.

Jenkins hash function or CRC32 are widely used for hash tables. The following is a C-style code of Jenkins hash function.

#define KEY_LENGTH 6 // for 48-bit keys
#define HASH_BIT_LENGTH 14 // Output address space of the hash function
uint32_t
jenkins_hash(uint32_t *key)
{
    size_t i;
    uint32_t hash;
    hash = 0;
    for ( i = 0; i < KEY_LENGTH; i++ )
        hash += key[i];
        hash += hash << 10;
        hash ^= hash >> 6;
    }
    hash += hash << 3;
    hash ^= hash >> 11;
    hash += hash << 15;
    return hash & ((1 << HASH_BIT_LENGTH) - 1);
}

As hash functions map a key bit string to another bit string, the resultant bit string corresponding to different input bit strings may collide with each other (be same). To arbitrate the collision, one of the following two mechanisms, linked list or linear probing is commonly used.

A linked list is a naive solution for collision. Assuming the following six keys are stored in a hash table with eight buckets, hash values of 1, 10, and 100 are all 5 and collides.

Each bucket corresponding to a hash value forms a linked list for the entries with the same hash value to arbitrate the collisions as illustrated in the following figure.

A problem with this solution is that the maximum length of the linked list is up to the number of entries if all the hash values collides. This means that the worst computational complexity is O(n), where n is the number of entries.

Linear probing is another solution to arbitrate collisions of hash values. Each bucket in the hash table with linear probing is allowed to have at most one entry. Instead, a next available bucket will be sequentially sought if a hash value collision occurs. For example, assuming the example above used for the linked list, linear probing is performed to insert a key 10 whose hash value is 5 after inserting 1 whose hash value is also 5. Since the bucket corresponding to the hash value 5 is occupied with the key 1, we have no space for the key 10. Then, it tries to seek an empty bucket next to the bucket of 5. As the bucket corresponding to the hash value 6 is empty, the key 10 is inserted to the bucket. By doing this procedure, the hash table will be the following figure when the values are inserted in ascending order.

The lookup procedure requires to probe the buckets until the corresponding value is found. For example, it seeks from the bucket of 5 to 7 to find the key 100. Thus, the computational complexity is bound by the order of the number of buckets. There are extended algorithms such as hopscotch hashing that limit the number of steps of linear probing to reduce the worst case computational complexity.

A problem with linear probing is that the size of a hash table is fixed, and consequently, the hash table is required to reconstruct to expand when the hash table becomes full.