[Hash Table] Hash Table을 구현해보자

Hash Table

https://zzong-a.tistory.com/196

[자료구조] Hash / Hash Table in Python

예전에 파이썬으로 기록해둔 Hash Table이 있다. 자세한 설명은 위 게시글에서 볼 수 있다.!

 

대략 몇줄로 요약해보자면,

[key, value] ---- (Hash Func에 key를 넣어서 암호화!) -----> [Hash Table, value]

key를 hash 함수를 통과시켜 암호화를 해서 hash table에 저장시켜뒀음 !

근데 우리는 value를 알고싶으니까 암호화한 방식 그대로 우리가 알고싶은 value의 Key를 해시함수에 넣어서 암호화 매칭된 값에 있는 value를 읽어오면 끝 ! 

 

 

그렇다면 swift 에서 hash table을 알아보짜!

import Foundation

var hashTable: [String?] = .init(repeating: nil, count: 3)

//우리가 만든 해시함수
func hash(key: Int) -> Int {
    return key % 3
}

func updateValue(_ value: String, forKey key: String) {
    guard let key = UnicodeScalar(key)?.value else { return } //key값을 String -> Int(Unicode이용)
    let hashAddr = hash(key: Int(key))
    hashTable[hashAddr] = value
}

func getValue(forKey key: String) -> String? {
    guard let key = UnicodeScalar(key)?.value else { return nil }
    let hashAddr = hash(key: Int(key))
    return hashTable[hashAddr]
}

updateValue("재석", forKey: "유")
updateValue("명수", forKey: "박")
print(getValue(forKey: "유")!)
print(getValue(forKey: "박")!)

 

위의 해시 함수가 너무 단순한 나머지 

key "유"와 "이"는 같은 해시 주소값을 반환해버린다. 

따라서 key- Value가 덮어씌어지는 충돌이 발생하는데 ... 위의 게시글에도 설명해뒀던 Hash collision 인 것이당.

 

 

해결방법으로는 1. chaining 기법 2. Linear Probing 기법이 존재하는데 한번 알아보자 ! 어렵다! 힘내자!!!!!!1 

(수정할거임 !! 잠시대기 )