Hash Tables

Separate chaining (open hashing)

Implementation

• After hashing an item, it is pushed into a linked list or bucket
• This is one of the more common approaches to implementing a hash table
• It is probably good practice to rehash and resize one a linked list gets larger than 20

Linear Probing (Open addressing or Closed hashing)

• In open addressing, instead of in linked lists, all entry records are stored in the array itself.

• If the slot at the hashed index is unoccupied, then the entry record is inserted in slot at the hashed index else it proceeds in some probe sequence until it finds an unoccupied slot.

• If any collisions are met, a probing sequence is used to find the next available slot

Probing Sequence

const linearProbeInsert = function(obj) {

    let key = hashingFunction(obj)

    let i = 0

    while(hashTable[key] !== null) {
        key = (key + i) % _tablesize
        i++
    }

    hashTable[key] = obj
}

Quadratic Probing

• Quadratic probing is similar to linear probing and the only difference is the interval between successive probes or entry slots

• The interval between slots is computed by adding the successive value of an arbitrary polynomial in the original hashed index.

Probing Sequence

const quadraticInsert = function(obj) {

    let key = hashFunction(obj.name)

    let i = 1

    while(_hashTable[key] !== null) {
        index = (index + i * i) % _tableSize

        i++
    }

    _hashTable[index] = obj
}

Double Hashing

• Interval between probes is calculated using two hashing functions

const doubleHashInsert = function(obj) {

    let keyA = hashFunction1(obj.name)
    let keyB = hashFunction2(obj.name)

    let i = 1

    while(_hashTable[key] !== null) {
        index = (keyA + keyB) % _tableSize

        i++
    }

    _hashTable[index] = obj
}

Reference

• Great tutorial on the different types of hashing