[자료구조] Hash Table

자료구조 04 / Hash Table

---

정의 

해쉬 테이블 키(Key) 값을 주어질때 Hash Function을 거처 하나의 같은 길이(크기)의 데이터(Value)를 저장하는 데이터 구조

 

용어정리

Hash : 임의 값을 고정 길이로 변환하는것

Hashing Function : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

Hash Value (Hash Address) : Key를 해싱 함수로 연산해 해쉬 값을 알아내 해쉬 테이블에서 해당 Key에 대한 데이터 위치

Slot : 한 개의 데이터를 저장할 수 있는 공간

 

 * 저장할 데이터에 대해 Key를 추출 할 수 있는 별도 함수도 존재 할 수있음

 

일반적인 예 (Swift) : Dictionary

Dictionary 사용법 간단한 정리 - [2nd Week] Chapter 05-3. Collection 컬렉션 (Array / Dictionary / Set )

Apple 공식문서 Dictionary

https://ko.wikipedia.org/wiki/해시_테이블

장단점 및 주요 용도

장점

- 데이터 저장/읽기 속도가 빠름 (검색 속도 빠름)

- Hash는 Key에 매칭하는 데이터가 있는지 (중복) 확인 쉬움

 

단점

 - 일반적으로 저장공간이 좀 더 많이 필요

 - 여러 키에 해당하는 주소가 동일 할 경우 충돌을 해결하기 위한 별도 자료구조가 필요 (연결리스트)

 

주요 용도

 - 검색이 많아 필요한 경우

 - 저장, 삭제, 읽기가 빈번한 경우

 - 캐쉬 구현 시 (중복 확인이 쉽기 때문)

 

특이사항

충돌(Collision) 발생하는 경우 (다른 Key 값으로 같은 결과 Hash Value가 나오는 경우) 해결방법

 

1. Chaining 기법 (개방 Hashing, Opne Hashing Method)

 - 해쉬 테이블 저장공간 외의 공간을 활용하는 기법

 - 충돌 일어나면 연결리스트로 데이터를 추가로 뒤에 연결

 

2. Linear Probing 기법 (폐쇄 hashing, Closed Hashing Method)

 - 해쉬 테이블 저장공간 안에서 활용하는 기법

 - 충돌 발생 시 해당 Hash Address 다음 Address 에 충돌되는 데이터를 저장 (공간 활용도 높임) 

 

빈번한 충돌을 개선하는 방법

 - 해슁 함수를 재정의 및 해쉬 테이블 저장 공간을 확대

 

github

GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제

구현 및 구조 설명 

Hashing Function과 Collision

func naiveHash(_ string: String) -> Int {
    let unicodeScalars = string.unicodeScalars.map { Int($0.value) }
    return unicodeScalars.reduce(0, +)
}

print(naiveHash("abc")) // outputs 294
print(naiveHash("bca")) // outputs 294

위 함수는 raywenderlich.com 에서 간단하게 Hashing Function을 구현한 예시이다. 

단순히 문자(key)를 unicodeScalars로 변환(hashing) 하는 동작을 볼 수 있다.

하지만 너무 단순한 함수이기 때문에 다른 두 키값 abc 와 bca의 Hash Value가 동일한 294로 충돌이 발생하는 경우를 볼 수 있다.

func djb2Hash(_ string: String) -> Int {
  let unicodeScalars = string.unicodeScalars.map { $0.value }
  return unicodeScalars.reduce(5381) {
    ($0 << 5) &+ $0 &+ Int($1)
  }
}

djb2Hash("abc") // outputs 193485963
djb2Hash("bca") // outputs 193487083

위 함수는 조금 더 복잡한 함수로 구현(해싱 함수 재정의)해서 충돌을 막는 구현이다.

 

Chaining 기법 (Array or Linked List) 구현해보기 (raywenderlich.com 예제)

public struct HashTable<Key: Hashable, Value> {
    private typealias Element = (key: Key, value: Value)
    private typealias Bucket = [Element]
    private var buckets: [Bucket]
    
    // 현재 HashTable에 존재하는 Key-Value (Element) 갯수
    private(set) public var count = 0
    public var isEmpty: Bool {
        return count == 0
    }
    
    // 초기화
    public init(capacity: Int) {
        assert(capacity > 0)
        buckets = Array<Bucket>(repeating: [], count: capacity)
    }
    
    // Hashing Function
    private func index(for key: Key) -> Int {
        return abs(key.hashValue) % buckets.count
    }
}

해쉬 충돌을 Bucket이라는 배열을 이용해서 사전에 막아주는 동적 HashTable 구조이다.

public struct HashTable<Key: Hashable, Value> {
    // Key 를 받아서 Value 리턴
    public subscript(key: Key) -> Value? {
      get {
        return value(for: key)
      }
      set {
        if let value = newValue {
          update(value: value, for: key)
        } else {
          removeValue(for: key)
        }
      }
    }
    
    // Key를 받아서 해당 key
    public func value(for key: Key) -> Value? {
      let index = self.index(for: key)
      return buckets[index].first { $0.key == key }?.value
    }
    
    public mutating func update(value: Value, for key: Key) -> Value? {
      let index = self.index(for: key)
      
      // Key에 해당 Hash Address의 배열의 값이 있다면 
      //다음 index에 Value 값 넣고 이전 oldValue 리턴
      if let (i, element) = buckets[index].enumerated().first(where: { $0.1.key == key }) {
        let oldValue = element.value
        buckets[index][i].value = value
        return oldValue
      }

      // Hash Address의 배열의 값이 없다. 배열에 Key와 Value 넣기
      buckets[index].append((key: key, value: value))
      count += 1
      return nil
    }
    
    public mutating func removeValue(for key: Key) -> Value? {
      let index = self.index(for: key)
      
      // Key에 해당하는 Hash Address의 배열의 값이 있다면 
      //해당 index에 Value 값 제거하고 이전 oldValue 리턴
      if let (i, element) = buckets[index].enumerated().first(where: { $0.1.key == key }) {
        buckets[index].remove(at: i)
        count -= 1
        return element.value
      }

      // Hash Address의 배열의 값이 없다. 동작 없음
      return nil
    }
}

데이터를 수정/추가 또는 삭제하는 경우 Key에 해당하는 Hash Address의 배열을 확인한다.

 

Hashable

대표적으로 사용되는 두 Collection 타입은 HashTable 구조를 따르고 있다.

공식문서를 보면 Hashable 이라는 프로토콜을 적용하는 걸 볼 수 있다.

 

A type that can be hashed into a Hasher to produce an integer hash value.

하나의 Hasher을 이용해 하나의 정수 Hash Value를 얻는 프로토콜이다.

 

Key값을 String 또는 Int등 다양하게 설정할 수 있는데

서로 다른 두 key값을 다른 정수 값으로 표현해주는 변환기라고 간단히 설명할 수 있다.

Hashable 프로토콜을 준수하는 Dictionary와 Set의 특징은 중복 값을 갖지 않는 점이 

위 기능 부분의 큰 특징을 이용한걸로 볼 수 있다.

 

Hash Table 개념을 정리하다 당도한 부분이라 개념적인 내용만 이해하고

구조적인 이해와 부가적인 이해는 

Apple 공식 문서 를 참조.... ㅠㅠ

 

추가적으로 생각해볼 내용

시간복잡도

최고 : 충돌 없을 경우 - 저장 및 삭제, 검색 O(1)

최악 : 충돌이 모두 발생하는 경우 - O(n) (일일이 slot을 검색)

 

-> 비둘기 집의 원리  : n+1개 물건을 n개의 상자에 넣으면 어느 상자엔 분명 두개 이상의 물건이 들어있다.

발생하지 않도록 Hashing Function 구현하거나 (복잡해지면 해쉬함수 연산 시간 길어진다)

충돌을 대비한 장치를 구현해야 함 (공간 효율성 낮아진다)

 

비밀번호, Request 등에 보안을 위해 많이 사용한다

눈사태 효과 (단방향 해쉬함수 특징) : input(Key)값이 거의 유사해도 output(value)값이 전혀 다르다 (유추 불가능)

 

SHA, Secure Hash Algorithm

해쉬 함수중 하나로 암호학적 해쉬 함수들을 뜻한다.

 

SHA-0, SHA-1... 등으로 표현하는데

SHA-256이 가장 대중적이며, 해쉬 함수를 거친 결과가 256bit이다.

 

해쉬 테이블의 단점인 충돌 발생을 줄이는 방법의 일종으로 

SHA-256 이후 단계에서는 아직 충돌발생이 발견되지 않았다.

 

비트코인을 포함한 많은 블록체인 시스템에서 SHA-256을 많이 사용한다.

 

 

Definition : HashTable / HashFunction / SHA(Secure Hash Algorithm) (위키백과)
Reference : Hashable공식문서 관련 , raywenderlich예제 관련 , HashTable 충돌 관련 / (개인 블로그)