[Swift] 자료구조 - 해시 테이블(Hash Table)

안녕하세요~

 

오늘은 연결 리스트에 이어서 해시 테이블을 정리하려고 합니다 : )

 

[ LinkedList 포스팅 ]

[Swift] 자료구조 - 단방향 / 양방향 연결 리스트(Linked List)

 

---

 

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조입니다.

 

해시 테이블은 내부적으로 배열을 이용해 저장하고 있으며 

Key값에 해시 함수를 적용해 저장할 인덱스를 결정합니다.

 

따라서 삽입, 삭제, 조회 등이 O(1)의 시간 복잡도를 갖고 있습니다.

 

흔히 우리가 알고 있는 딕셔너리가 이 중에 하나로 내부적으로

해시테이블을 사용하고 있습니다.

 

해시 테이블 구현

-  배열을 생성합니다.

var myHashTable: [Int?] = .init(repeating: nil, count: 4) // 4개

 

해시 함수

- 키값이 해시 함수의 로직을 통해 인덱스 값을 결정합니다. 

- 대표적으로 3가지가 존재합니다.

1. 나눗셈을 이용하는 방법 : 입력값을 테이블의 크기로 나누어 계산하기
- 주소 = 입력값 % 테이블의 크기
- 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용하면 효율이 좋다고 알려진 방법

2. 곱셈을 이용하는 방법 : 숫자로 된 Key값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 계산.
- h(k)=(k * A * mod 1) × m

3. Digit Folding : 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.

 

- 가장 보편적으로 알려진 나눗셈 방법으로 진행하겠습니다.

private func myHashFunc(key: Int) -> Int {
    return key % 4 // 해시 테이블이 0,1,2,3의 index를 가지고 있기 때문!
}

이 해시함수를 통해 나온 값을 이용해 Index를 결정할 수 있게 되고 이를 활용해 값을 저장하게 됩니다.

 

해시 테이블에 저장하는 함수

// 분기처리, 예외처리를 고려하지 않고 간단하게 구현
func storeValue(value: Int, key: Int) {
    let hashAddress = hash(key: key) // 위의 해시함수를 통해 주소를 찾기
    hashTable[hashAddress] = value // 해당 주소에 value 넣기!
}

 

해시 테이블에서 값을 가지고 오는 함수

func getValue(key: Int) -> Int? {
    let hashAddress = hash(key: key)
    return hashTable[hashAddress]
}

이렇게 두 가지 함수를 구현하고 나면

해시 테이블의 기본적인 기능은 할 수 있습니다.

 

하지만

만약 해싱 알고리즘을 통해 나온 인덱스 값이 같은 경우에는 어떻게 될까요?

 

Key	1	2	3	5
Value	2	3	4	5
HashAddress	1	2	3	1

 

위의 표처럼 Key값이 1과 5인 경우, 모두 1번째 인덱스에 들어가게 될 겁니다.

 

이를 해시 테이블의 충돌이라고 말합니다.

 

해시 테이블 충돌 해결 방법

첫 번째, Chaining 기법

- 이미 해당 인덱스에 원소가 존재한다면 이를 뒤에 연속적으로 이어 붙이는 기법입니다.

- 일전에 포스팅에서 배웠던 연결 리스트를 활용하는 방법으로 그중에서도 단방향 연결리스트를 사용합니다.

- 1번째 주소에 (1,2)의 노드가 있을 경우 이 노드의 next를 (5,5)로 설정해 주면 됩니다.

- [ HashAddress : 1 ]  - [1,2] → [5,5]

 

두 번째, Linear Probing ( Close Hashing ) 기법

- Linear 하게 순서대로 다음 빈 공간을 찾고 값을 저장하는 방법입니다.

- Chaining 기법처럼 Table 이외의 공간을 또 만들지 않기 때문에 Close Hashing이라고도 부릅니다.

 

이 외에도 해시의 저장순서 폭을 제곱으로 설정하는 방식인 Qudratic Probing, 해시된 값을 한번 더 해싱하는 방식인 Double Hashing Probing이 있습니다.

 

해시 테이블에 대해서 간단하게 정리해 봤습니다.

그럼 이만 👋🏻 👋🏻 👋🏻

 

 

---

 

 

참고 자료

감사합니다 👏

[자료구조] 해시테이블(HashTable)이란?

Swift) 해시 테이블(Hash Table) 이해하기