#Hash Table
해시란 무엇일까?
위키피디아에 따르면 해시 함수에 의해 얻어진 값을 해시라 한다.
그럼 해시 함수란?
임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다.
마지막으로 해시 테이블이란?
해시를 이용한 테이블이겠지..ㅎ
해시 테이블은 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열을 말한다.
좀 더 쉽게 풀어서 설명하자면
데이터를 어떠한 알고리즘으로 고유한 숫자를 만든다.
그리고 이것을 인덱스로 사용해 저장하는 방법이다.
배열을 사용하여 데이터를 저장하며
데이터 고유의 인덱스로 접근하게 되므로
매우 빠른 검색 속도를 갖는 자료구조이다.
이미 배열이 생성되어 있고 비어있는 곳을 굳이 채워 넣을 필요가 없기 때문에
삽입 또는 삭제도 효율적으로 수행할 수 있다.
물론 이때문에 충분한 메모리 공간이 필요하다는 단점이 있다.
포켓몬 이름으로 포켓몬의 정보를 해시방법으로 저장한다고 가정해보자.
샤미드, 쥬피썬더, 부스터를 각 이름을 해시 함수에 넣어 인덱스를 구하고
해당 인덱스에 데이터를 저장한다.
나중에 해당 포켓몬의 정보를 얻을 때
이름만 입력하면 바로 데이터를 가져올 수 있다.
그런데 해시 함수의 결과 값은 항상 고유값은 아니라는 문제가 있다.
중복값이 발생할 때를 해시 충돌이라 하고 보통 두가지 해결 방법이 제시된다.
다음과 같이 충돌이 난다고 가정해보자.
버터플과 도나리 모두 해시함수에 넣었을 때
동일한 인덱스 값이 나온다.
이처럼 해시 충돌에 대한 첫번째 해결 방법은 Separate Chaining 방식이 있다.
이는 나중에 들어온 데이터를 추가하는 방법이다.
LinkedList 또는 Tree를 사용하는 방식이 있다.
이 둘을 사용하는 기준은 버킷에 할당된 key-value 쌍의 개수이다.
트리는 기본적으로 메모리 사용량이 많고
데이터 개수가 적을 때
Worst Case를 살펴보면 이 둘의 성능 상 차이가 거의 없으므로
메모리 측면에서 볼 때 LinkedList를 사용하는 것이 맞다.
LinkedList를 이용하면 다음과 같이 저장이 된다.
두번째 방법은 Open Address 방식이 있다.
해시 충돌이 발생하면 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다.
이 방법에서 또 3가지로 나뉘어진다.
1. Linear Probing: 순차적으로 비어있는 버킷 탐색
2. Quadratic Probing: 선형 탐사와 비슷하지만 폭을 제곱수로 넓게 탐색
3. Double hashing Probing: 해시 출동 발생 시 2차 해시 함수 이용하여 새로운 주소 할당
이중 Linear Probing으로 충돌을 해결하면 다음과 같이 저장된다.
그렇다면 어떤 기준을 가지고 Separate Chaining과 Open Addressing을 사용해야 할까?
둘 모드 Worst Case O(M)이다.
그러나 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에
Separate Chaining보다 캐시 효율이 높다.
따라서 데이터 개수가 적다면 Open Addressing이 성능이 좋지만
데이터 개수가 커질수록 Worst Case 발생빈도가 높아지기 때문에
Open Addressing이 Separate Chaining보다 느려진다.
Separate Chaining은 충돌 빈도를 보조 해시 함수를 이용하여 조절할 수 있기 때문에
Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다.
(보조 해시 함수는 key의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다)
해싱에는 정적 해싱과 동적 해싱이 있다.
정적 해싱은 데이터를 입력하기 전에 일정 크기의 메모리를 미리 할당받는 것이며
해시 테이블의 크기가 할당된 메모리의 크기를 넘어갈 수 있다.
이러한 문제점을 해결하기 위해서 동적 해싱이 등장했는데
동적해싱은 오버플로우 발생시 버킷 안의 엔트리들만 재조정하고
동적으로 해시 테이블의 크기를 변화시키면서 성능을 높여주는 방법이다.
동적 해싱은 데이터가 증가해도 검색의 성능이 유지되고 메모리 낭비를 줄일 수 있다는 장점이 있지만
로직이 복잡하고 버킷을 쪼개거나 합치는 과정 중에 부하가 발생하는 단점도 가지고 있다.
참고
- https://k39335.tistory.com/18
- https://d2.naver.com/helloworld/831311
To be continued.........
Made by 꿩