Hash Value
원본 데이터를 특정 규칙에 따라 처리하여 간단한 숫자로 만든 것을 해쉬값이라고 한다. 정확히는 원본 데이터 (객체)를 해쉬 함수 (hash function)을 사용하여 64bit의 Int값으로 변환한 것이다.
2개의 데이터를 비교할 때, 데이터가 동일하면 각 데이터의 해쉬값도 동일하다.
하지만 데이터가 조금이라도 다르면, 완전히 다른 해쉬값을 가진다.
하지만 해쉬값은 일정 크기의 Int값이므로 유한하고, 데이터 양은 무한하기 때문에 해쉬값이 충분하지 않기 때문에 2개의 서로 다른 데이터가 동일한 해쉬값을 가질 수도 있다. 즉, "해쉬값이 동일하면, 2개의 데이터가 동일하다"는 참이 아닐 수 있다.
이 때문에 해쉬 충돌이 발생한다. 해쉬 충돌은 다른 데이터 구조 (연결 리스트, 선형조사법 등)를 사용하여 해결할 수 있다.
let hi: String = "안녕하세요"
let hello: String = "안녕하세요"
let anotherHello: String = "안녕하세요!!!"
print(hi.hashValue) // 459043611440984182
print(hello.hashValue) // 459043611440984182
print(anotherHello.hashValue) // 2330325378159778121HashTable
key : Value 쌍을 저장하는 데 사용되는 데이터 구조이다.
딕셔너리도 HashTable의 일종이므로 딕셔너리를 생각하면 된다.
HashTable은 내부적으로는 배열로 이용해 저장하며 Key값에 해시함수를 적용해 저장할 인덱스를 결정하고 Key를 사용하여 빠르게 값을 검색할 수 있다.
💡 해시함수란?
Key값에 해시함수를 적용해 저장할 인덱스를 결정한다는게 무슨 의미인지 먼저 살펴보자!
예를 들어 이런 key : Value를 가진 딕셔너리가 있을때, 해시테이블은 데이터가 일반 배열처럼 순서대로 저장되지않고 순서를 지키지 않고 저장된다.
해당하는 Key를 통해서 HashTable에 저장되어있는 데이터에 접근해야하는데, 해시테이블은 내부적으로 배열로 구성되어있기때문에 접근하려는 값의 index를 알아야 접근할 수 있다.
하지만, Value가 저장된 해시테이블의 index를 모르니까, Key를 통해 index를 알아내야 한다.
해시함수를 사용하면 Key를 해당하는 해시테이블의 index로 변환할 수 있고, 동일한 키에 대해 항상 동일한 해시주소(해시테이블의 index)가 생성되도록 할 수 있다. 이 해시주소를 사용해서 배열 내에 해당 키에 대한 인덱스를 계산하고 데이터에 접근할 수 있다.
HashTable 사용하기
딕셔너리의 경우 값이 없으면 nil을 리턴하니, nil로 초기화된 해시 테이블 배열을 만든다.
var hashTable: [String?] = .init(repeating: nil, count: 3)해시함수를 만든다. 대표적인 방법은 세가지가 있다.
1. 나눗셈 이용
키를 해시 테이블의 크기로 나눈 나머지를 해시값으로 사용하는 방법, 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용하면 효율이 좋다고 한다.
주소 = 입력값 % 테이블의 크기
2. 곱셈 이용
숫자로 된 Key값 K와 0 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 계산하여 해시값으로 사용하는 방법
h(k) = (k * A * mod1) * m
3. Digit Folding
각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 해시값으로 사용하는 방법func hash(key: Int) -> Int {
return key % 3 // 해시테이블이 0, 1, 2 세개의 index를 갖고있기때문
}해시테이블에 데이터를 저장하는 함수를 만든다.
func updateValue(_ value: String, forKey key: Int) {
// 해시함수를 이용해서 index 찾기
let hashAddress = hash(key: key)
// 해당하는 index에 value 저장하기
hashTable[hashAddress] = value
}해시테이블의 데이터를 가져오는 함수를 만든다.
func getValue(forKey key: Int) -> String? {
let hashAddress = hash(key: key)
return hashTable[hashAddress]
}HashTable의 충돌
위와 같이 구현하면 간단한 해시테이블의 기능은 구현가능하다. 하지만 해시함수가 단순해서 결과 값인 해시주소가 겹치는 경우가 있다. 아래와 같이 Key값이 1, 5일때 index가 같다. 이렇게 되면 Key - Value 덮어씌워지는 충돌 현상이 일어난다.
(위의 HashTable 사용하기 예제에서는 key가 1, 4일때 HashAddress가 동일하게 1로 충돌이 생긴다)
HashTable의 충돌 해결 방법
-
Chaining 기법 (개방 해슁, Open Hashing)
충돌이 발생하면 연결 리스트Linked List를 이용하여 해시 테이블 저장 공간 외의 공간을 활용해 데이터를 추가로 뒤에 연결시켜서 저장하는Chaning기법이다.
이 방법은 간단하고 메모리를 효율적으로 사용할 수 있으나, 충돌이 많은 경우에는 연결 리스트의 길이가 길어져 검색 시간이 느려질 수 있다. 또한, 꽉 찬 상태에서 삽입 연산을 수행할 때 성능이 저하될 수 있다. -
Linear Probing 기법 (폐쇄 해싱, Close Hashing)
충돌이 발생하면 해시 테이블 저장 공간 안에서 충돌 문제를 해결하는 방법
충돌이 일어날 경우, 해당 해쉬 주소값(index부터) 순회하며 가장 처음 나오는 빈 공간에 저장하는 기법으로 저장 공간의 활용도를 높인다. 하지만 해시 테이블에서 발생하는 문제 중 하나로 연속된 해시 주소에 데이터가 몰리는 현상인 클러스터링(Clustering)이 발생할 수 있어서 성능이 갑자기 저하될 수 있는 단점이 있다.
HashTable의 시간 복잡도
해시 테이블은 배열로 구성되어 있지만 원하는 값을 찾기 위해 0번 index부터 순회해야 하는 배열의 O(n)과 달리, Key 값을 해시하여 바로 Index에 접근하기 때문에 해시테이블의 시간 복잡도는 O(1)로 배열에 비해 매우 빠르다.
모든 충돌이 다 발생한 경우에는 배열처럼 O(n)이지만, 일반적인 경우에는 O(1)이라고 말할 수 있다.
HashTable의 장단점
해시테이블은 해시함수를 사용하여 Key를 해시값으로 매핑하므로 Key의 중복 확인과 속도가 빠르다. 하지만 충돌이 많을 경우 성능이 저하되고 해결하기 위한 별도의 자료구조가 필요해서 메모리 사용량이 증가할 수 있다.
따라서 해시테이블은 검색 및 삽입 연산을 많이 하는 경우나 중복된 키를 허용하지 않아야 하는 경우에 효율적으로 사용된다.
