Skip to content

Instantly share code, notes, and snippets.

@fishkingsin
Created March 17, 2021 14:00
Show Gist options
  • Save fishkingsin/80729f3f8e1260d5500d215f1d32bb2b to your computer and use it in GitHub Desktop.
Save fishkingsin/80729f3f8e1260d5500d215f1d32bb2b to your computer and use it in GitHub Desktop.
HashTable implementation in swift
import UIKit
import XCTest
class HashTableNode<T> {
var value: T
var key: String
var nextNode: HashTableNode?
init(value: T, key: String) {
self.value = value
self.key = key
}
}
enum InsertionStatus {
case success, collision, replacement
}
class HashTable<T> {
private var bucket: [HashTableNode<T>?]
init(bucketSize: Int) {
bucket = Array(repeating: nil, count: bucketSize)
}
func getElement(forKey hashKey: String) -> T? {
let index = findIndex(forKey: hashKey)
var node = bucket[index]
while node != nil {
if node?.key == hashKey { return node?.value }
else {
node = node?.nextNode
}
}
return nil
}
@discardableResult func addElement(_ element: T, forKey hashKey: String) -> InsertionStatus {
let node = HashTableNode(value: element, key: hashKey)
let index = findIndex(forKey: hashKey)
var auxNode = bucket[index]
if auxNode == nil {
bucket[index] = node
return .success
}
while auxNode?.nextNode != nil {
if auxNode?.key == hashKey || auxNode?.nextNode?.key == hashKey {
auxNode = [auxNode, auxNode?.nextNode].first(where: {$0?.key == hashKey})!
auxNode?.value = element
return .replacement
}
auxNode = auxNode?.nextNode
}
auxNode?.nextNode = node
return .collision
}
func deleteElementForKey(_ key: String) -> Bool {
let index = findIndex(forKey: key)
var node = bucket[index]
if node?.key == key {
bucket[index] = node?.nextNode
return true
}
while node?.nextNode != nil {
if node?.nextNode?.key == key {
node?.nextNode = node?.nextNode?.nextNode
return true
}
node = node?.nextNode
}
return false
}
private func findIndex(forKey hashKey: String) -> Int {
if hashKey.isEmpty { return -1 }
let v = hashKey.unicodeScalars.reduce(0, { $0 + Int($1.value) })
print(v)
let ret = v % bucket.count
print(ret)
return ret
}
}
var table = HashTable<String>(bucketSize: 5)
table.addElement("Hello", forKey: "1234")
XCTAssertEqual(table.getElement(forKey: "1234"), "Hello")
XCTAssertNil(table.getElement(forKey: " "))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment