Hash Table이란?
객체는 Hash Table이라는 자료구조의 종류 중 하나이다.
Hash Table은 Key 와 Value가 쌍을 이룬 형태로 데이터가 저장되어 있는 자료구조형을 지칭한다.
- 배열 내 데이터도 Key 와 Value로 이뤄져 있으나, 배열에서는 Key가 오직 index, 즉 숫자만 가능한것에 비해 Hash Table에서는 문자열 또한 Key가 될 수 있다.
해시 테이블 작업별 시간복잡도
| search | O(1) |
| lookup | O(1) |
| insert | O(1) |
| delete | O(1) |
장점 : 빠르다. 탐색, 삽입, 삭제, 중복 데이터를 찾아내기 쉽다.
단점 : 저장할 공간은 많은데 들어올 메모리가 적을 때 효율적이지 않고, 저장할 때 순서가 없다. 또 O(1)의 일정 시간이
길면 모두 시간이 오래 걸린다.
해시 함수(Hash function)
Hash Table은 Key가 input되면 Hash Function을 이용하여 무작위의 주솟값을 생성한 후, 생성된 주솟값에 Key와 value를 저장하는 방식을 취한다. 해시 함수는 두 가지의 특징이 있다.
1. 일방향 : Key가 input 되면 랜던함 값을 output으로 생성해내는데, 이 랜덤한 output을 기반으로 input이 무엇인지를 알아낼 수 없다
2. idemponent: input이 동일하면 항상 동일한 랜덤 output이 출력. input이 한 글자라도 틀려지면 랜덤 output또한 달라진다.
해시 함수를 이용하기 때문에 해시 테이블은 해싱충돌이라는 문제가 야기될 수 있다.
key인 사람이름을 Hash function을 통해 인덱싱을 한다. 해당 index의 값인 Value는 bucket (slot)에 저장이 된다.
이런식으로 key, value를 저장한다
Hash Collision 해시 충돌
Key와 Value로 이루어져 있는 해시 테이블의 특성 상, search, lookup, insert, delete 같은 작업에서 해시 테이블은 아주 빠른 속도를 보인다. O(1), Constant Time이기 때문이다. 이렇게 좋은 성능을 발휘하지만 그러지 못하는 이유는 해시 충돌 때문이다.
해시테이블의 가장 큰 단점은 배열과 달리 자료구조가 정렬되어 있지 않다는 점이다. 메모리 공간에서 주소에 순차적으로 값을 부여하지 않고, random하게 값을 부여한다
만약 0, 1, 2, 3, 4총 4개의 메모리 주소가 있다고 가정하고, 첫 번째 데이터가 0번째 메모리 주소에 들어갔다고 해도, 그 다음 데이터가 1 번째 메모리에 들어가지 않을 수 있다. 랜덤하게 주소가 배정되기 때문이다. 따라서, 0번째 메모리에 다 들어가 저장될 수도 있다. 이러한 현상을 해시 충돌이라고 한다.
개방 주소법(Open Address)
개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Prove) 한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식이다. 해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방주소(Open Addreess)라고 한다.
개방 주소법은 어떤 방식으로 비어있는 공간을 탐사할 것이냐에 따라 4가지로 나누어 진다.
1.선형 탐사법(Linear Probing)
선형으로 순차적으로 탐사하는 방법이다. 만약 충돌하게 된다면 바로 옆 빈 공간이 나타날 대까지 순차적으로 탐사를 하고 값을 할당해준다.
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1991 |
충돌이 일어나면 정해진 n칸만큼 옆 방을 주는 방법이다.
| 0 | 1 | 2 | 3 | 4 | 5 |
| 1991 | 3 |
이런식으로 충돌이 났을 때, 순차적으로 옆 방을 주는 것이 선형 탐사법이다. 또 충돌이 발생하면, 3번 인덱스의 저장될 것이다.
선형 탐사법의 단점은 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화문제에 취약하다는 것이다.
충돌 -> 데이터 덩어리 뒤에 충돌난 값 저장 -> 충돌발생확률 증가 -> 충돌 -> 데이터 덩어리 뒤에 충돌난 값 저장 -> 충돌발생확률 증가 -> 충돌...
이런식으로 무한 반복이 발생한다. 이것이 일차 군집화(Primary Clustering)이라고 한다.
2.제곱 탐사법(Quadratic Probing)
제곱 탐사법은 선형 탐사법과 동일하지만 탐사하는 폭이 고정폭이 아닌 제곱으로 늘어난다.
첫 번째 충돌 발생시 그 지점으로부터 1의 제곱, 그 다음은 2의 2제곱, 그 다음은 3의 3제곱....
그래서 충돌이 발생하더라도 데이터의 밀집도가 선형탐사법보다 낮기 때문에 연쇄적으로 충돌이 발생할 확률이 많이 줄어든다.
3. 이중해시(Double Hasing)
해시 함수를 이중으로 사용 하는 것이다.
하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용한다.
이렇게 하면 최초 해시로 같은 값이 나오더라도 다른 해시 함수를 거치면서 다른 탐사 이동폭이 나올 확률이 높기 때문에 다른 공간에 값이 골고루 저장될 학률도 높아진다.
결론 -
장점은 빠르다. Fast search, fast Insertion and Deletion, Fast lookup
단점은 무작위 주소 할당으로 인한 문제
https://soldonii.tistory.com/72?category=862199