Created
March 17, 2021 14:00
-
-
Save fishkingsin/80729f3f8e1260d5500d215f1d32bb2b to your computer and use it in GitHub Desktop.
HashTable implementation in swift
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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