[Data Structure] Hash Table(2) - Implementation

Swift에서 HashTable을 활용한 자료구조에는 Set과 Dictionary가 존재한다.

이 중 Key-Value 쌍으로 데이터를 저장하는 Dictionary를 구현해 보자. 

 

해당 포스팅에선 Dictionary를 Chaing방법과 Open Addressing 2가지 방법으로 모두 구현해 볼 것이다.

여기서는 구현에 관해서만 다룰 것이기 때문에, 해시 테이블 이론에 관련한 것들은 이전 포스팅을 참고 바란다.

https://seokyoungg.tistory.com/92

[Data Structure] Hash Table(1) - Concept

 

전체적인 구현은 해당 링크에서 확인해 볼 수 있다. 

https://github.com/jungseokyoung-cloud/Data-Structure/tree/main/Data-Structure/HashTable.playground

Data-Structure/Data-Structure/HashTable.playground at main · jungseokyoung-cloud/Data-Structure

 

본격적인 구현에 들어가기 전에,  Dictionary에서 사용할 Data 타입을 프로토콜로 제한해 주자.

protocol Dictionable {
	associatedtype Key: Hashable
	associatedtype Value
	var key: Key { get set }
	var value: Value { get set }
}

이때, key값의 경우에는 Hashable타입을 강제한다.

 

Chaining 

우선, Chaining에서 사용할 Element를 정의해 주자. 

struct ChainingElement<Key, Value> where Key: Hashable {
	var key: Key
	var value: Value
}

extension ChainingElement: Dictionable {}

 

Linked List

Chaining 기법에선 연결리스트를 통해 해시 충돌을 처리하기 때문에, 연결리스트를 구현해주어야 한다.

이중 연결리스트를 활용했으며, find메서드만 key값을 통해 element를 찾을 수 있게끔 변경해 주었다. 

struct HashTableLinkedList<T: Dictionable> {
	typealias Node = DoubleLinkedNode<T>
	
	private var head: Node?
	private weak var tail: Node?
	
	var isEmpty: Bool { head == nil }
	
	init() { }
}

... 

extension HashTableLinkedList {
	/// key 값을 가지는 연결리스트를 리턴합니다. 
	func find(for key: T.Key) -> Node? {
		var beginIterator = self.makeIterator()
		var endIterator = self.makeIterator()
		
		while
			let begin = beginIterator.next(),
			let end = endIterator.prev() {
			if begin.data.key == key {
				return begin
			} else if end.data.key == key {
				return end
			}
			
			if begin === end { break }
		}
		
		return nil
	}
}

 

Dictionary 

이제부터 본격적으로 Dictionary 본체이다. 

public struct ChaingingDictionary<Key, Value> where Key: Hashable {
	typealias Element = ChainingElement<Key, Value>
	
	/// HashTable의 LoadFactor가 3이상일 경우 rehash가 일어납니다.
	private let maxLoadFactor: Double = 3
	
	/// 현재 HashTable의 loadFactor를 표시합니다.
	public var loadFactor: Double { Double(count) / Double(bucketCount)}
	
	/// HashTable의 Bucket의 숫자를 리턴합니다.
	private var bucketCount: Int
	
	/// HashTable내의 모든 값들의 개수를 리턴합니다.
	public private(set) var count: Int = 0
	
	private var buckets: [HashTableLinkedList<Element>]
	
	public init(bucketCount: Int = 23) {
		self.bucketCount = bucketCount
		self.buckets = Array(repeating: HashTableLinkedList<Element>(), count: bucketCount)
	}
    
 ...
 
 }
 
 // MARK: - Private Methods
private extension ChaingingDictionary {
	func index(for key: Key) -> Int {
		return abs(key.hashValue) % bucketCount
	}
...
}

loadFactor가 maxLoadFactor를 넘어서는 경우 rehash 작업이 일어난다. 

With separate chaining the value of $\alpha_{max}$ the gives best performance is typically between 1 and 3
- wikipedia -

위키 피디아에 의하면, 1~3 사이의 LoadFactor를 유지하는 것이 성능적으로 좋다고 나와있기 때문에, maxLoadFactor를 3으로 설정했다.

 

insert(_:with:)

mutating func insert(_ value: Value, with key: Key) {
	let index = index(for: key)
	
	// 해댕 키 값의 원소가 이미 있으면, value만 변경
	if let node = buckets[index].find(for: key) {
		node.data.value = value
	// 반대의 경우, 원소를 추가
	} else {
		buckets[index].append(.init(key: key, value: value))
		count += 1
	}
	
	if loadFactor >= maxLoadFactor {
		rehash(bucketCount: bucketCount * 2)
	}
}

insert(_:with:) 메서드의 경우에는 key값을 해싱해, 

해당 hash Table에 원소가 존재하면, update를 진행하고, 

없다면 새로 추가한다. 

 

만약, loadFactor가 maxLoadFactor를 넘어섰을 경우, bucketCount를 2배로 늘려 rehash작업이 일어난다. 

 

delete(for:)

@discardableResult
mutating func delete(for key: Key) -> Value? {
	let index = index(for: key)
	
	guard let node = buckets[index].find(for: key) else { return nil }
	
	count -= 1
	return buckets[index].remove(at: node)?.value
}

 

find(for:)

func find(for key: Key) -> Value? {
	let index = index(for: key)
	
	return buckets[index].find(for: key)?.data.value
}

 

rehash(bucketCount:)

mutating func rehash(bucketCount: Int) {
	var newBuckets = Array(repeating: HashTableLinkedList<Element>(), count: bucketCount)
	
	self.bucketCount = bucketCount
	
	buckets.forEach { bucket in
		bucket.forEach { node in
			let key = node.data.key
			let value = node.data.value
			let index = index(for: key)
			
			newBuckets[index].append(.init(key: key, value: value))
		}
	}
	
	self.buckets = newBuckets
}

만약, loadFactor가 maxLoadFactor에 다다를 경우 2배 늘려서 rehash 작업을 진행한다.

 

subscript

public subscript(key: Key) -> Value? {
	get {
		return find(for: key)
	}
	mutating set {
		if let newValue = newValue {
			insert(newValue, with: key)
		} else {
			delete(for: key)
		}
	}
}

최종적으로 subscript를 추가해 Swift의 Dictionary처럼 사용가능하도록 구현했다. 

var chain = ChaingingDictionary<String, String>()

chain.insert("seoul", with: "jung")

chain["jung"] = "busan"
chain["jung"] // busan
chain["kim"] // nil
chain.count // 1

chain["kim"] = "seoul"
chain.count // 2

chain["jung"] = nil
chain["jung"] // nil

 

 

Open Addressing

Open Addressing은 중간에 원소를 삭제하게 되면, 뒤에 존재하는 원소들은 탐색할 수 없는 문제가 발생한다.

struct OpenAddressingElement<Key, Value> where Key: Hashable {
	var key: Key
	var value: Value
	var isDeleted: Bool = false
	
	init(key: Key, value: Value) {
		self.key = key
		self.value = value
	}
}

extension OpenAddressingElement: Dictionable { }

따라서, 실질적으로 메모리에서 해제하는 것이 아닌, isDeleted 프로퍼티를 통해 삭제 상태인지 아닌지를 구분할 수 있게 해 주었다.

 

Dictionary

해당 Dictionary는 Swift의 HashTable구현을 참고해 구현했다. 따라서, 실제 Swift의 Hash Table이 사용하는 Linear Probing방식으로 구현했다. 

public struct OpenAddressingDictionary<Key, Value> where Key: Hashable {
	typealias Element = OpenAddressingElement<Key, Value>
	
	/// HashTable의 LoadFactor가 0.75이상일 경우 rehash가 일어납니다.
	private let maxLoadFactor: Double = 0.75
	
	/// 현재 HashTable의 loadFactor를 표시합니다.
	public var loadFactor: Double { Double(count) / Double(bucketCount)}
	
	/// HashTable의 Bucket의 숫자를 리턴합니다.
	private var bucketCount: Int
	
	/// HashTable내의 모든 값들의 개수를 리턴합니다.
	public private(set) var count: Int = 0
	
	private var buckets: [Element?]
	
	public init(bucketCount: Int = 23) {
		self.bucketCount = bucketCount
		self.buckets = Array(repeating: nil, count: bucketCount)
	}
	
	...
	
}

 

Open Addressing 방법에선 maxLoadFactor를 0.75로 설정했다. 

With open addressing, acceptable figures of max load factor $\alpha_{max}$ should range around 0.6 to 0.75
- wikipedia -

 

위키피디아에서도 0.6에서 0.75를 유지하는 것이 좋다고 하며, 실제 Swift의 HashTable도 0.75를 maxLoadFactor로 설정했다. 

extension _HashTable {
	/// The inverse of the maximum hash table load factor.
	private static var maxLoadFactor: Double {
		@inline(__always) get { return 3 / 4 }
	}
	...
}

 

insert(_:with:)

mutating func insert(_ value: Value, with key: Key) {
	let index = index(for: key)
	
	// 이미 존재한다면, update
	if let findIndex = findIndex(key: key, index: index) {
		buckets[findIndex]?.value = value
	// linear probing을 통해 가능한 공간을 찾아서 삽입.
	} else if let insertIndex = findAvailableIndex(from: index) {
		buckets[insertIndex] = .init(key: key, value: value)
		count += 1
	}
	
	if loadFactor >= maxLoadFactor {
		rehash(bucketCount: bucketCount * 2)
	}
}

Linear Probing을 통해, 현재 키값의 인덱스를 탐색한다. 만약, 존재한다면 update를 하고,

존재하지 않는다면, findAvilableIndex(from:) 메서드를 통해 빈 공간을 찾는다.

func findAvailableIndex(from index: Int) -> Int? {
	var index = index
	var count = 1
	
	while
		let element = buckets[index],
		!element.isDeleted {
		index = nextIndex(from: index)
		count += 1
		
		// 한바퀴 돈 경우
		if count > bucketCount { return nil }
	}
	
	return index
}

element의 isDeleted가 true이거나, 실제로 비어있는 공간을 찾아 리턴한다.

 

delete(for:)

@discardableResult
mutating func delete(for key: Key) -> Value? {
	let index = index(for: key)
	
	guard let findIndex = findIndex(key: key, index: index) else { return nil }
	
	buckets[findIndex]?.isDeleted = true
	count -= 1
	return buckets[findIndex]?.value
}

delete 메서드에선, 실제 메모리에서 해제하는 것이 아닌, isDeleted를 true로 설정해 Probing이 가능하도록 한다.

 

find(for:)

func find(for key: Key) -> Value? {
	let index = index(for: key)
	
	guard let findIndex = findIndex(key: key, index: index) else { return nil }
	
	return buckets[findIndex]?.value
}

 

rehash(bucketCount:)

mutating func rehash(bucketCount: Int) {
	let currentBuckets = buckets
	
	buckets = Array(repeating: nil, count: bucketCount)
	self.bucketCount = bucketCount
	
	
	currentBuckets.forEach { element in
		if let element = element, !element.isDeleted {
			insert(element.value, with: element.key)
		}
	}
}

 

subscript

public subscript(key: Key) -> Value? {
	get {
		return find(for: key)
	}
	mutating set {
		if let newValue = newValue {
			insert(newValue, with: key)
		} else {
			delete(for: key)
		}
	}
}

마찬가지로 subscript를 구현해 실제 Dictionary처럼 사용가능하게끔 구현했다.

var openAddressing = OpenAddressingDictionary<String, String>()

openAddressing.insert("seoul", with: "jung")

openAddressing["jung"] = "busan"
openAddressing["jung"] // busan
openAddressing["kim"] // nil
openAddressing.count // 1

openAddressing["kim"] = "seoul"
openAddressing.count // 2

openAddressing["jung"] = nil
openAddressing["jung"] // nil

References

위키백과 

• Hash table

 

Swift Hash Table 

Swift Algorithm Club: Hash Table 

바킹독님 Hash Table 강의

https://medium.com/@alex.hsieh/implement-dictionary-in-swift-5be2792d8bf9