Hash Tables

Suppose you wanted to maintain large collection of numbers, how can you store them such that you can efficiently insert new numbers, delete old numbers and check for the existance of a given number? Use buckets of the numbers’ modulo a large fixed constant. The data structure managing thses buckets is called a hashtable. Use operations to test your solution and print the results for the exists operations.

Example

Input:

let operations = [("exists", 10), ("insert", 10), ("exists", 10), ("delete", 10), ("exists", 10), ("insert", 2), ("insert", 3), ("insert", 4), ("exists", 3), ("exists", 5)]

Expected value/output:

false
true
false
true
false

[collapse]
Hint

Can you see why these buckets will keep a relatively small collection of numbers and thus will be very efficient? Randomness plays an important role here.

[collapse]
Solution

let operations = [("exists", 10), ("insert", 10), ("exists", 10), ("delete", 10), ("exists", 10), ("insert", 2), ("insert", 3), ("insert", 4), ("exists", 3), ("exists", 5)]

var hashtable = [[Int]]()
var constant = 23

func initHashtable() {
    for _ in 0..<constant {
        hashtable.append([])
    }
}

func exists(_ number: Int) -> Bool {
    let modC = number % constant
    for num in hashtable[modC] {
        if number == num {
            return true
        }
    }
    return false
}

func insert(_ number: Int) {
    if exists(number) == true {
        return
    }
    let modC = number % constant
    hashtable[modC].append(number)
}

func delete(_ number: Int) {
    let modC = number % constant
    for i in 0..<hashtable[modC].count {
        if number == hashtable[modC][i] {
            hashtable[modC].remove(at: i)
        }
    }
}

func hashtableRun() {
    initHashtable()
    for operation in operations {
        if operation.0 == "exists" {
            print(exists(operation.1))
        }
        else if operation.0 == "insert" {
            insert(operation.1)
        }
        else if operation.0 == "delete" {
            delete(operation.1)
        }
    }
}

hashtableRun()

[collapse]
1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading...
Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)