Week 12 (cont.)

Lecturer: Pritam Bhattacharya, BITS Pilani, Goa Campus

Date: 5/Nov/2021

Hashing

Example for the hashing function taken \(h(k) = k\ \%\ 7\)

Finding an array

find(x) {
    pos = x % 7
    if(T[pos] == x) {
        return True
    }
    else {
        return False
    }
}

Insert to an array

insert(x) {
    pos = x % 7
    if(T[pos] = EMPTY) {
        T[pos] = x
    }
    else {
        # Handle Collision
    }
}

Open Addressing Hashing

Finding in open addressing

find(x) {
    pos = x % 7
    currNode = T[pos]
    while(currNode != NULL) {
        if(currNode -> data == x) {
            return True
        }
        curNode = currNode -> next
    }
    return False
}

Insertion in open addressing

insert(x) {
    pos = x % 7
    struct Node* newNode
    newNode -> data = x
    newNode -> next = NULL
    if(T[pos] == NULL) {
        T[pos] = newNode
    }
    else {
        currNode = T[pos]
        while(currNode -> next != NULL) {
            currNode = currNode -> next
        }
        currNode -> next = newNode
    }
}

Linear Probing

When a collision is reached, what we end up doing is if there is a collision, we find the next hash value as so:

\(h(k, 0) = k\ \%\ 7\)
\(h(k, 1) = (h(k) + 1 )\ \%\ 7\)
\(...\)
\(h(k, n) = (h(k) + n )\ \%\ 7\)

Insertion

insert(k) {
    i = 0
    pos = ((k % 7) + i) % 7
    while(T[pos] != EMPTY) {
        i += 1
        pos = ((k % 7) + i) % 7
        if(pos == k % 7) {
            return "ERROR! HASHTABLE IS FULL"
        }
    }
    T[pos] = k
}

Finding

insert(k) {
    i = 0
    pos = ((k % 7) + i) % 7
    while(T[pos] != k) {
        i += 1
        pos = ((k % 7) + i) % 7
        if(T[pos] == EMPTY || pos == k % 7) {
            return "NOT FOUND IN HASHTABLE"
        }
    }
    return pos
}

---

Tags: !DatastructuresAndAlgorithmsIndex