21.06.29
공부한 것을 정리하는 용도의 글이므로 100% 정확하지 않을 수 있습니다.
참고용으로만 봐주시고, 내용이 부족하다고 느끼신다면 다른 글도 보시는 것이 좋습니다.
+ 틀린 부분, 수정해야 할 부분은 언제든지 피드백 주세요. 😊
by. ryalya
들어가기 전
이전 글인 Collection - 배열 (Array)에서 잠깐 Dictionary에 대해서 설명했었다.
리마인딩해보자면 아래와 같다.
Dictionary : Key와 Value의 쌍으로 이루어진 Collection
→ Key - Value로 값을 저장하기 때문에 특정 Key를 던져주면, 그 키에 해당하는 Value가 나오는 형태!
// <Dictionary> 선언/기본
var stringDictionary : [String : String] = [:]
// add key-value pair
dictionary["Name"] = "ryalya"
// retrieve value for a key
dictionary["Name"] // outputs "ryalya"Dictionary의 Key나 Value로 Array를 만들 수 있다.
let colors = ["빨강":"red", "초록":"green", "파랑":"blue"]
print(colors) // ["빨강":"red", "초록":"green", "파랑":"blue"]
// Key
var kColor = colors.keys
print(kColor) // ["초록", "파랑", "빨강"]
print(type(of:kColor)) // Keys 타입
// Value
var eColor = colors.values
print(eColor) = ["blue", "red", "green"]
print(type(of:eColor)) // Values 타입하지만 key type은 String 형으로 바꿔줘야 Array〈String〉 Type으로 사용할 수 있다.
방법은 아래와 같다.
var kColor1 = [String](color.keys)
print(kColor1) // ["초록", "파랑", "빨강"]
print(type(of:kColor1)) // Array<String> 타입Hash Table
Hash
해시 함수(Hash Function)는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑해주는 함수.
매핑전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(Hash Value)또는 해시코드(hash code)라고 하며, 키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing)이라고 한다.
Hash table
해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조.
이때, 해시 함수에 의해 반환된 데이터의 고유 숫자 값을 해시값 또는 해시코드 라고 한다.
기본연산 : 탐색(Search), 삽입(Insert), 삭제(Delete).
-
키(key) : 고유한 값이며, 해시 함수의 input. 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소에 저장됨.
-
해시함수(Hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도움.
-
해시(Hash) : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장됨.
-
값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 함.
Hash Collision(해시 충돌)
서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 한다.
충돌이 발생하지 않으면 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)O(1)에 수행되지만 충돌이 발생할 경우 탐색과 삭제 연산이 O(K)O(K)만큼 걸리게 된다.
해결 방법 1. Separate Chaining(Chaining)
충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결리스트 형태로 저장하는 방법.
쉽게 말해, 각 index에 데이타를 저장하는 Linked list 에 대한 포인터를 가지는 방식.
동일 index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가한다.
이렇게 하면 충돌이 발생하더라도 데이터를 삽입하는 데 문제가 없다.
위 그림을 보면 John Smith 와 Sandra Dee 의 인덱스가 152 로 충돌하게 된 경우인데, 이 때 Sandra Dee 를 John Smith 뒤에 연결함으로써 충돌을 처리하는 것을 볼 수 있다.
데이터를 추출을 하고자할때는 key에 대한 index를 구한후, index가 가리키고 있는 Linked list를 선형 검색하여, 해당 key에 대한 데이타가 있는지를 검색하여 리턴하면 된다.
key를 삭제하는 것 역시 간단한데, key에 대한 index가 가리키고 있는 linked list에서, 그 노드를 삭제하면 된다.
Chaining 장점 :
1) 한정된 저장소(Bucket)을 효율적으로 사용할 수 있다.
2) 해시 함수(Hash Function)을 선택하는 중요성이 상대적으로 적다.
3) 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.
Chaining 단점 :
1) 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.
2) 외부 저장 공간을 사용한다.
3) 외부 저장 공간 작업을 추가로 해야 한다.
해결 방법 2. Open Addressing
index에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고,
hash table array의 빈 공간을 사용하는 방법으로, chaining 방식에 비해 메모리를 덜 사용할 수 있는 방법.
Open Addressing의 해시테이블은 1개의 해시와 1개의 값(value)가 매칭되어 있는 형태로 유지됨.
위의 그림을 보면, Sandra가 저장될때 해시가 John으로 채워져 있어서 그 다음 Hash에 Sandra를 저장했다. 그리고 Ted의 해시도 Sandra가 저장되어 있으므로 그 다음 해시에 Ted를 저장했다. 이처럼 비어있는 해시를 찾아 저장하는 방법을 Open Addressing라고 한다.
이때, 비어있는 해시(Hash)를 찾는 과정은 동일해야 하며(일정한 규칙을 따라 찾아가야 한다.)
Open Addressing은 해시를 찾아가는 규칙에 따라 아래 3개로 나눌 수 있다.
- 선형탐사(Linear Probing)
: 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장
- 제곱탐사(Quadratic Probing)
: 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장한다.
- 이중해싱(Double Hashing)
: 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장한다.
Open Addressing 장점 :
1) 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
2) 또 다른 저장공간에서의 추가적인 작업이 없다.
Open Addressing 단점 :
1) 해시 함수(Hash Function)의 성능에 전체 해시테이블의 성능이 좌지우지된다.
2) 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다.
Reference
