Skip to content

Instantly share code, notes, and snippets.

@chiahsien
Created August 26, 2021 07:22
Show Gist options
  • Save chiahsien/b28fb3af5586858bcb36828fe9c2425d to your computer and use it in GitHub Desktop.
Save chiahsien/b28fb3af5586858bcb36828fe9c2425d to your computer and use it in GitHub Desktop.
//
// Reference:
// https://khanlou.com/2016/07/implementing-dictionary-in-swift/
//
import Foundation
class Item<Key: Hashable, Value> {
let key: Key
var value: Value
var next: Item?
init(key: Key, value: Value) {
self.key = key
self.value = value
self.next = nil
}
}
extension Item: CustomStringConvertible {
var description: String {
return "[\(key): \(value)]"
}
}
class LinkedList<Key: Hashable, Value> {
var head: Item<Key, Value>?
func addItem(key: Key, value: Value) {
let item = Item(key: key, value: value)
item.next = head
head = item
}
func deleteItem(key: Key) -> Item<Key, Value>? {
guard let head = head else { return nil }
if head.key == key {
self.head = head.next
head.next = nil
return head
}
var previous: Item = head
var current = head.next
while current != nil, current!.key != key {
previous = current!
current = current!.next
}
if current != nil {
previous.next = current!.next
current!.next = nil
return current
}
return nil
}
}
extension LinkedList: Sequence {
func makeIterator() -> LinkedListIterator<Key, Value> {
return LinkedListIterator(head)
}
}
struct LinkedListIterator<Key: Hashable, Value>: IteratorProtocol {
typealias Element = Item<Key, Value>
var current: Element?
init(_ head: Element?) {
self.current = head
}
mutating func next() -> Element? {
let element = current
current = current?.next
return element
}
}
struct MyDictionary<Key, Value> where Key : Hashable {
private var storage: [LinkedList<Key, Value>?] = Array(repeating: nil, count: 8)
private(set) var count: Int = 0
private let maxLoadFactor = 0.8
private var loadFactor: Double {
return Double(storage.compactMap { $0 }.count) / Double(storage.count)
}
var isEmpty: Bool {
count == 0
}
subscript(key: Key) -> Value? {
get {
let index = abs(key.hashValue) % storage.capacity
guard let list = storage[index] else { return nil }
for item in list where item.key == key {
return item.value
}
return nil
}
set {
let index = abs(key.hashValue) % storage.capacity
if let value = newValue {
update(key: key, value: value, at: index)
resizeIfNeeded()
} else {
delete(key: key, at: index)
}
}
}
private mutating func delete(key: Key, at index: Int) {
guard let list = storage[index] else { return }
if list.deleteItem(key: key) != nil {
count -= 1
}
if list.head == nil {
storage[index] = nil
}
}
private mutating func update(key: Key, value: Value, at index: Int) {
let list: LinkedList<Key, Value>
if storage[index] == nil {
list = .init()
storage[index] = list
} else {
list = storage[index]!
}
if list.deleteItem(key: key) != nil {
count -= 1
}
list.addItem(key: key, value: value)
count += 1
}
private mutating func resizeIfNeeded() {
guard loadFactor >= maxLoadFactor else { return }
print("Resizing storage...")
let temp = storage.compactMap { $0 }
storage = Array(repeating: nil, count: storage.count * 2)
count = 0
var item: Item<Key, Value>?
for list in temp {
item = list.head
while item != nil {
self[item!.key] = item!.value
item = item!.next
}
}
}
func dump() {
print("Current load factor: \(loadFactor)")
for item in self {
print(item, terminator: " -> ")
}
}
}
extension MyDictionary: Sequence {
func makeIterator() -> MyDictionaryIterator<Key, Value> {
return MyDictionaryIterator(storage)
}
}
struct MyDictionaryIterator<Key: Hashable, Value>: IteratorProtocol {
typealias Element = Item<Key, Value>
let storage: [LinkedList<Key, Value>]
var currentItem: Element?
var currentListIndex: Int
init(_ storage: [LinkedList<Key, Value>?]) {
self.storage = storage.compactMap { $0 }
currentListIndex = 0
if currentListIndex < self.storage.count-1 {
currentItem = self.storage[currentListIndex].head
}
}
mutating func next() -> Element? {
let element = currentItem
if currentItem?.next != nil {
currentItem = currentItem?.next
} else if currentListIndex < storage.count-1 {
currentListIndex += 1
currentItem = self.storage[currentListIndex].head
} else {
currentItem = nil
}
return element
}
}
var dict = MyDictionary<Int, String>()
dict[300] = "Ooops"
dict[200] = "OK"
dict[400] = "test"
dict[200] = nil
dict[100] = "100"
dict[1] = "1"
dict[2] = "2"
dict[3] = "3"
dict[4] = "4"
dict[5] = "5"
dict.count
dict.isEmpty
dict[300]
dict[200]
dict[400]
dict.dump()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment