[Data Structure] 해쉬 테이블(Hash Table) 구현해보기(feat. Swift)

안녕하세요 Foma 💻 입니다!

오늘은 저번 글에서 해쉬 테이블의 이론에 이어서 직접 구현해 보려고 합니다!

(혹시 저번 글을 안보셨다면 여기 를 통해서 보고 와주세요~)

바로 시작할게요~

---

HashTable

먼저 저는 해쉬 함수를 Digit Folding 알고리즘을 이용해서 만들 것이기 때문에 key값을 String으로 설정했습니다.

또한 충돌이 났을 때 해결 방법으로 Chaining 기법을 사용하였지만 연결 리스트 대신 배열을 사용했습니다.

아래와 같이 typealias로 별칭을 설정해주고 버킷을 이중배열로 선언했습니다.

 

    public struct HashTable<String,Value> {
    public typealias Key = String 
    private typealias Element = (key:Key,value:Value) 
    private var bucket:[[Element]] = [] ...

---

Initialize

초기화는 해쉬 테이블을 만들 때 버킷사이즈를 설정하도록 해놓고 그 크기만큼 버킷을 만들어주었습니다.

 

 public init(bucketSize:Int) {
      bucket = Array<[Element]>(repeating:[], count: bucketSize) 
 }

subscript를 사용해서 get일 땐 key값에 따라 value를 반환했고, set일 땐 nil이 아니라면 새로운 값으로 update를 해주고

nil이라면 삭제를 했습니다.

 

public subscript(key: String) -> Value? {
    get {
         return value(forKey: key) 
    } 
    set {
        if let value = newValue {
             updateValue(value, forKey: key) 
         } else {
              removeValue(forKey: key) 
         } 
    } 
}

---

Hash Function

index를 찾기 위한 알고리즘으로 앞서 설명했다시피 digitFolding을 사용해서 반환해 줍니다.

 

 private func findIndexByDigitFolding(forKey key:Key) -> Int {
      return "\(key)".unicodeScalars.reduce(0, { $0 + Int($1.value) }) % bucket.count 
 }

---

Search

key값에 따른 value값을 반환할 때는 아래와 같이 index를 digitFoliding으로 key값을 변환해준 값으로 설정하고,

버킷 안의 index의 배열 안에서 현재 key값과 같은 값을 가진 value를 반환해주고 없다면 nil을 반환해줍니다.

 public func value(forKey key: Key) -> Value? {
      let index = findIndexByDigitFolding(forKey: key) 
      
      for element in bucket[index] {
           if "\(element.key)" == "\(key)" {
               return element.value 
           } 
       } 
       return nil 
  }

---

Append(Update)

값을 삽일할 때 버킷 안의 값들을 찾아서 만약 있다면 update를 하고 없다면 append를 해주었습니다.

public mutating func updateValue(_ value: Value, forKey key: Key) {
     let index = findIndexByDigitFolding(forKey: key) 
     
     for (i, element) in bucket[index].enumerated() {
          if "\(element.key)" == "\(key)" {
               bucket[index][i].value = value 
          } 
     } 
     bucket[index].append((key: key, value: value)) 
}

---

Remove

삭제는 버킷의 해당 index에 있는 배열 안에 똑같은 key값을 찾아 nil로 만들어 줍니다.

public mutating func removeValue(forKey key: Key) {
     let index = findIndexByDigitFolding(forKey: key) 
     
     for (i, element) in bucket[index].enumerated() {
          if "\(element.key)" == "\(key)" {
               bucket[index].remove(at: i) 
          } 
     } 
 }

---

실행결과

 

 var hashTable = HashTable<String, Any>(bucketSize: 13) //삽입 
 hashTable["foma"] = "foma" 
 hashTable["gran"] = "gran" //충돌(foma와 mofa는 digitfolding에 의해 똑같은 인덱스가 나옵니다.) 
 hashTable["mofa"] = "mofa" 
 print(hashTable["foma"],hashTable["gran"],hashTable["mofa"],hashTable["fomagran"]) //Optional("foma") Optional("gran") Optional("mofa") nil 
 hashTable["foma"] = nil //삭제 
 hashTable["gran"] = "foma" //업데이트
 print(hashTable["foma"],hashTable["gran"],hashTable["mofa"],hashTable["fomagran"])  //nil Optional("foma") Optional("mofa") nil

---

Reference

 

GitHub - raywenderlich/swift-algorithm-club: Algorithms and data structures in Swift, with explanations!