원본 글을 번역하고, 재구성한 글입니다.

Swift의 Dictionary 자료형은 Key-Value 쌍으로 이루어져 있다.

var dictionary: [String: String] = [:]

// add key-value pair
dictionary["firstName"] = "Steve"

// retrieve value for a key
dictionary["firstName"] // outputs "Steve"

이 Dictionary는 저장을 위해 Key-Value 쌍을 Hash Table로 전달할 것이다.

Hash Tables

Hash Table은 배열에 불과하다. 처음에 배열은 비어있고, 특정 키값을 Hash Table에 넣으면 Hash Function을 이용해 계산된 값을 배열의 index에 저장한다.

hashTable["firstName"] = "Steve"

hashTable은 "firstName" 키를 받아서 hashValue 프로퍼티에 물어본다.
따라서 키는 Hashable 프로토콜을 반드시 상속해야 한다.

Hash Functions

"firstName".hashValue값을 사용하면 big integer인 -8378883973431208045을 return 한다.

아래와 같이 간단한 hash 함수를 작성할 수 있다.

하지만 위의 함수는 문자열의 순열을 구분 할 수 없기 때문에,
abc와 cba값이 같은 294를 가리키고 있다.

A single lock is being opened by many keys!

즉 하나의 294라는 lock이 abc라는 key와 cba 라는 key에 의해 열린다.
따라서 이 함수는 좋지 않은 hash function이다.

아래 함수는 조금 더 나은 함수이다.

이번에는 두 순열이 다른 값을 가지고 있다.

Swift Standard Library for String의 해시 함수 구현은 훨씬 더 복잡하고 SipHash Algorithm을 사용한다.

Keeping Arrays Small

-8378883973431208045 와 같이 큰 hashValue는 보통 양수화 한 뒤에 array size로 modulo 연산을 한다.

따라서 firstName의 index는 abs(-8378883973431208045) % 3 = 1라는 계산식을 통해 1이 된다.

이러한 방법을 통해 Dictionary는 효율적이게 되고 inserting, retrieving, and removing의 시간 복잡도는 O(1)이 된다.

Avoiding Collisions

위 modulo방법에는 하나의 문제가 있다.

djb2Hash("firstName") % 2 // outputs 1
djb2Hash("lastName") % 2 // outputs 1

다음과 같이 같은 index에 저장될 수도 있고, 이를 Collisions라고 부른다.
이 Collisions를 해결하는 방법은 Chaining을 사용하는 것이다.

list는 chains, array elements는 buckets라고 불린다.
위 그림에서는 3개의 buckets가 있고, index 2에는 chain이 존재한다.

Retrieving Items

다음은 hash table에서 item을 retreive하는 예제이다.

let x = hashTable["lastName"]

index 2에서 chain을 가지고 있으므로, "lastName"이라는 key값을 찾기 위해 step through 한다.
step through 는 string comparison으로 키값을 비교하며 진행된다.
그렇게 "Jobs"라는 값을 return 한다.

이러한 Chain mechanism은 linked list나 다른 배열로 이루어진다.
당연히 이러한 chain이 길면 process가 느려지기 때문에 없거나 짧아야한다.