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]
