Hash function 이란?
Hash table is a data structure that provides a mapping from keys to values using a technique called hasing.
Key-values pair (key must be unique)
이는 주로 빈도수를 tracking하기 위해 사용되는데요
Hash function 특징
1. 결정론적 (Deterministic)
H(x) = y라고 했을 때 y이외의 다른 값을 생성하면 안됨
아래 예시처럼, H(5) = 6을 재호출하면 H(5) = 7이 되면서 y값이 변경되면 안된다는 거죠
2. 유일성 보존
H(x) = H(y)처럼 값이 같을 때를 hash collision이라고 하는데
이러한 hash collision을 최대한 줄이는 것이 중요합니다
Hash collision에 대응하는 방법
: Separate chaining & Open addressing
Separate Chaining
: Linked List같은 데이터 구조를 활용해서 특정 값에 hash된 서로 다른 value를 다루는 방식을 의미합니다
이 외에는 array, binary tree, self balancing tree 등등을 이용합니다
아래는 Linked List로 Separate Chaining을 하는 그림입니다
보시면 1,3,4의 key에 원래라면 2개의 값이 있어서 hash collision이 발생하지만, 갈등이 발생하는 값을 Linked List형태로
넣어서 각 값이 서로 다른 Linked List 블록에 있기 때문에 collision이 발생하지 않습니다
하지만, 여기서 Linked List가 길어지면 time complexity 문제가 발생할 수 있겠죠
어떤 요소를 찾을 때마다 모든 요소를 돌아야 한다면 시간이 많이 걸리니까요
이때는 주로 아예 별개의 Hash Table을 만들어서 내부 요소들을 rehash 한다고 하는데요
Open Addressing
: Hash table내에서 다른 값을 찾아서 기존 hash 장소에서 다른 곳으로 offsetting 하는 방법
Separate Chaining 과 달리, 기존 hash table 내에서 값이 저장되기 때문에 hash table의 사이즈에 대한 주의가 필요함
Open addressing을 실행하는 방법에는 아래처럼 여러가지 방법이 있습니다
Hash Table Time Complexity
| Operation | Average | Worst |
| Insertion | O(1)* | O(n) |
| Removal | O(1)* | O(n) |
| Search | O(1)* | O(n) |
Hashable 하다 => Hash table의 key값이 불변한다 (Deterministic 충족을 위해)
(공부하면서 내용을 추가해가도록 하겠습니다...)
댓글