[Data Structure] Hash Table(1) - Concept

만약 다음과 같은 데이터가 있다고 가정해 보자. 

이들을 저장하기 위해선, 품목을 키값으로 매핑해 개수를 저장해야 한다. 

즉, 품목이 인덱스화 될 필요가 있다. 

 

이처럼 key-value를 매핑하는 것이 "해시 테이블(Hash Table) ADT"이다.

 

해시 테이블 ADT를 자료구조로 구현하기 위해선, key 값을 정수값으로 매핑할 필요가 있다. 

이러한 Key값을 해시 테이블의 인덱스로 매핑하는 것이 "해시 함수"(Hash Function)이다.

이때, 해시 함수의 결과값을 해시, 해시 값, 해시 코드라 부른다.

 

즉, 해시 테이블(Hash Table) ADT를 자료구조로 구현하기 위해 필요한 것이 해시 함수이다. 

 

해시 함수의 결과값인 해시(해시 값, 해시 코드)는 해시테이블의 인덱스가 된다. 이렇게 인덱스를 통해 접근한 해시 테이블의 각 Entry를 "Bucket"이라 부른다. 

 

이러한, 해시 테이블은 Hash Map, Dictionary라 부른다.

추가적으로 Hash Set으로도 불리는데, Set ADT를 구현하는 방법은 다양하지만, 

가장 많이 사용되는 방법이 Hash기 때문에, Hash Set으로 불리는 것이다. 

In computer science, a set is an abstract data type that can store unique values, without any particular order.
- 위키 피디아
Set ADT는 단순히 순서 없이, unique한 값만 저장할 수 있는 기능을 제공한다.

 

Hash Function

"해시 함수"(Hash Function)는 특정 해싱 알고리즘을 적용해, 임의의 크기를 갖는 데이터를 고정된 크기의 값으로 매핑하는 함수이다.

이때 해시 함수의 결과물을 해시, 해시 값 이라고 불린다. 

 

이러한 해시 함수는 단방향 구조인데, 키값을 통해 해시값은 얻을 수 있지만, 해시 값에서 키 값을 얻을 수는 없다. 

이러한 특성 때문에, SHA-1 해시 알고리즘과 같이 암호학 분야에서도 사용되며, 이때의 해시 값을 체크섬이라고도 부른다. 

대표적으로 Git에서 commit들을 SHA-1해시를 사용하는데, 이 해시 값(체크섬)을 통해 수천, 수만 줄의 코드에서 변경된 점을 찾을 수 있다. 

 

이런 해시 함수가 정수로 변환해주는 것을 통해 해시 테이블(Hash Table) 자료구조에 사용된다.

해시 함수는 다음과 같이 간단 할 수도 혹은 복잡할 수도 있다. 

func hash(for key: String) -> Int {
	let unicodeScalrs = key.unicodeScalars.map { Int($0.value) }
	
	return unicodeScalrs.reduce(0, +) % hashTable.size
}

 

이러한 해시 함수는 최대한 Unique하게 해시 테이블에 매핑해주어야 한다.

해시 테이블의 크기는 한정되었지만, 함수의 정의역 공간이 너무 크기 때문에, 다른 키 값임에도 해시 값이 겹치는 결과가 발생하게 된다.

이를 "해시 충돌"이라 부른다. 

 

"해시 충돌"은 불가피하지만, 발생할수록 해시테이블 자료구조의 성능이 저하되기 때문에 최대한 피해야 한다.

 

즉, "해시 함수"는 충돌을 최소화하기 위해 

해시 테이블에 균등한 분포로 매핑해주어야 하며, 계산하기 쉬워야 한다.

 

 

또한, 해시 함수에서 최종적으로 "해시 테이블의 사이즈"(Bucket의 수)로 모듈러 연산을 진행해 주는데, 

return unicodeScalrs.reduce(0, +) % hashTable.size

이때, 나눠주는 값이 짝수가 된다면, 내부적으로 저장되는 이진수의 비트가 shift되어 기존의 해시값이 사라질 수 있다. 

따라서, 해시 테이블의 사이즈는 되도록이면 20이상의 소수를 사용한다.

해시 함수 내부에서 곱셉 혹은 나눗셈 연산을 진행할 때 역시 마찬가지로 20 이상의 소수를 사용한다. 

 

 

Collision Resolution

앞서 설명했듯, 해시 함수의 정의역이 너무나 크기 때문에, 해시 충돌 현상은 불가피하다. 

그렇기 때문에, 해시 테이블에선 해시 충돌에 대해 대처할 수 있어야 하는데, 대표적으로 2가지 방법이 있다. 

• Chaining(Close Addressing)
• Open Addressing

 

Chaining (Closed Addressing) 

각 Bucket마다 다음과 같이 List를 추가해 충돌을 회피하는 방법이다. 

해시 값에 대응되는 곳에만 데이터를 삽입하기에 Closed Addressing이라고도 부른다.

만약 해시 함수가 균등한 분포로 매핑하지 못한다면, 특정 Bucket에 몰리게 되며, 탐색의 시간 복잡도가 O(N)이 되게 된다. 

 

List에서,

연결리스트를 사용하게 된다면, 삭제 측면에선 효율적이지만, 

동적배열은 탐색에 있어서 cache hit ratio가 높아 효율적이다. 

 

 Open Addressing 

Open Addressing은 Closed Addressing과 반대로, 

해시 값에 대응되지 않는 곳에 데이터를 삽입할 수 있다. 

 

만약에 해시 값에 대응되는 Bucket에 이미 다른 값이 존재한다면, 특정 규칙에 적용해 삽입 될 빈 Entry를 찾는다. 

이렇게 삽입 될 빈 Entry를 찾는 방법은 크게 3가지가 있다. 

• Linear Probing
• Quaratic Probing
• Rehashing 

 

Linear Probing 

말 그대로 선형적으로 탐사하는 방법으로, 바로 다음 Bucket을 탐색하는 과정을 빈 공간을 찾을 때까지 반복한다. 

 

다음과 같은 해시 함수를 가지고 삽입을 진행해 보자.

private let bucketCount = 10 

func hash(for key: Int) -> Int {
	return key % bucketCount
}

 

 

이후, 10을 삽입할 때 0번의 인덱스가 이미 다른 값이 채워져 있기 때문에, 해시 충돌이 발생한다. 

따라서, 선형 탐사를 진행하며 바로 다음칸이 비었기 때문에, 다음위치에 삽입한다. 

 

 

다음으로 20을 삽입하면, 마찬가지로 해시 충돌이 발생하며, 다음 다음칸에 삽입된다. 

 

51을 삽입할 때 역시 마찬가지로 1의 위치에 다른 값이 있기 때문에, 3번 인덱스에 삽입이 이루어진다. 

 

 

"선형 탐사"는 구현이 간단하고, Spatial Locality에 의해 Cache Hit Ratio가 높다는 장점을 가지고 있다.

 

반면, 다음과 같이 "군집"(Cluster)이 형성되게 되는데, 군집의 크기가 커질수록 해시 충돌이 더 자주 발생하게 되고, 

찾을 때까지 한 칸씩 이동해야하기 때문에 연산의 속도 역시 느려지게 된다.

또한, 군집에서 중간에 원소가 삭제되면, 데이터가 존재함에도 찾지 못하는 상황이 발생하기에, 해당 위치를 Dummy값으로 채워 넣어야 한다. 

 

Quadratic Probing

Quaratic Probing은 바로 다음 칸이 아닌, $1^2$, $2^2$, $3^2$, $4^2$ .. 과 같이 탐사를 하는 방식이다.

 

Linear Probing에 비해 Cache hit ratio가 떨어지지만, 그렇다고 해서 나쁜 편은 아니다.

또한, 클러스터가 형성되는 문제도 어느 정도 회피할 수는 있지만, 이동하는 경로가 같기 때문에 해시 값이 동일하다면 여전히 클러스터 문제가 발생한다.

 

Double Hashing

Double Hashing은 충돌이 발생한 경우, 해시 함수를 한번 더 적용해 몇 칸을 점프할지 결정하게 된다. 

Double Hasing은 클러스터 문제는 효과적으로 피할 수는 있지만, Cache hit ratio가 극악으로 안 좋아진다는 단점이 있다. 

 

Load Factor

load factor는 다음과 같이 정의된다. 

• $n$ : 해시 테이블에 할당된 데이터의 개수
• $m$ : 해시 테이블의 Bucket의 수 

해시 테이블이 좋은 성능을 유지하기 위해선, $\alpha$(Load factor)가 특정값($\alpha_{max}$)을 넘지 않도록 설계해야 한다. 

 

우선, Chaining 방식에선 충돌이 발생해도, 리스트 형태로 관리하기 때문에, 공간의 효율성을 위해 Load Factor를 1에서 3 사이를 유지한다. 

 

반면, Open Addressing 방식에선, Load Factor를 1 이상으로 유지하게 되면, 나중에는 빈 곳을 찾느라 연산이 느려지게 된다. 따라서, Load Factor를 0.65 혹은 0.75보다 작게 유지한다.

 

많은 프로그래밍 언어에선, 이 특정 Load Factor을 넘어설 경우, 해시 테이블의 사이즈를 재조정한다.

 

 

Swift Hashable 

Swift 역시 Hashable 프로토콜을 채택하는 타입들은 값을 정수인 해시 값으로 표현할 수 있다.

protocol Hashable : Equatable

같은 해시 값이 나왔을 때, 동일한 객체인지 혹은 해시 충돌인지 구분하기 위해 Equatable을 만족해야 한다.

기본적으로 Swift의 String, Int, Float, Double, Bool, Set이 기본적으로 Hashable 프로토콜을 채택하고 있다. 

 

이러한 해시 값은 Dictionary의 key값 혹은 Set의 Element 등에 사용된다.

// Dictionary
@frozen
struct Dictionary<Key, Value> where Key : Hashable

// Set
@frozen
struct Set<Element> where Element : Hashable

Dictionary는 Key값을 해싱해 해시 테이블에 저장하고,

Set은 Element를 해싱해 해시 테이블에 저장한다. 

 

커스텀 타입의 경우에도 모든 저장 프로퍼티가 기본 데이터 타입으로 구성되어 있으면, 별다른 구현 없이 Hashable 채택이 가능하다. 

struct Person: Hashable {
	let name: String
	let age: Int
}

 

하지만, 다음과 같이 Hashable을 만족하지 않은 타입이 저장 프로퍼티로 존재한다면, 컴파일 에러가 발생한다. 

struct Person: Hashable {
	let name: String
	let age: Int
	let address: Address
}

struct Address {
	let city: String
}

이러한 상황에선 다음과 같이 Equatable을 구현해 주고, hash(into:) 메서드에서 어떤 값을 해싱할지 구현한다.

extension Person: Equatable {
	static func == (lhs: Person, rhs: Person) -> Bool {
		return (lhs.name == rhs.name) && (lhs.age == rhs.age) && (lhs.address.city == rhs.address.city)
	}
	
	func hash(into hasher: inout Hasher) {
		hasher.combine(name)
		hasher.combine(age)
		hasher.combine(address.city)
	}
}

 

열거형의 경우에는 기본적으로 Hashable이 채택되어 있다. 하지만, associateValue(연관값)이 있는 경우에는 별도로 채택해주어야 한다. 마찬가지로 연관값이 Hashable을 만족하지 않는 타입이라면 hash(into:)메서드를 구현해주어야 한다.

 

또한, 내부적으로 보면 Swift의 해시 테이블은 Linear Probing을 적용한 Open Addressing 방식을 사용하며,

Load Factor는 0.75 이하로 유지하고 있다. 

https://github.com/apple/swift/blob/main/stdlib/public/core/HashTable.swift

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

만약, 0.75를 넘어가게 되면, 재할당이 일어나게 되고,

특정 수준이하로 Load Factor가 떨어지게 되면, 메모리 효율성을 위해 해시 테이블의 일부분을 해제한다. 

 

 

References

위키백과 

• Hash table 

 

애플 공식 문서

• Hashable
• Dictionary
• Set
• Hasher