해시테이블이란?

 해시테이블은 key와 value로 데이터를 저장하는 자료구조 중 하나입니다

 (공간을 소모하여 시간을 얻는방법 혹은 가장 빠른 데이터를 검색하는 방식이라고도 부릅니다)

출처 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

각각의 객체는 고유한 주소값을 가지며 이를가지고 hash Function을 통해 이 값을 테이블에 넣어 저장하는 방식입니다

이를 해싱이라고 하며 해시테이블의 가장 큰 장점은 원하는 데이터를 바로 찾을 수있다는 점입니다 시간복잡도로는 O(N) ~ O(1)로 가능한데

O(1)이 가능한 이유는 각각의 객체는 고유한 주소값을 가지고 이 주소값을 가지고 해싱한다면 똑같은 값을얻어 바로 원하는 key로 value에 접근이 가능합니다 

또한 이때 데이터가 저장된 장소를 버킷 또는 슬롯이라고 명칭합니다

그렇다면 O(N)이 나오는 이유는 무엇일까요?

바로 원하는 key의 값이 해시테이블에 저장되어있다면 상관없지만 충돌이 일어났을때 O(N)까지 나올수 있습니다

해시 테이블은 Insert방식은 처음에 매우큰 사이즈의 의 길이를 잡습니다 그 다음 저장할 데이터를 해싱하여 나온 해시값을 key를통해 저장하는 방식인데 

만약 해싱한 해시값이 중복이 된다면? 이때 충돌이 이루어진다고 합니다

해시테이블에서는 충돌에 의한 해결을 크게 두가지의 방식으로 해결하는데 Chaining과 open Addressing 방법입니다

Chaining

간단히 LinkedList를 생각하시면 될것 같습니다 

위와 같이 동일한 버킷에 접근한다면 그 뒤의 주소로 chaining즉 연결을 해서 관리를합니다

실제로 Java의 HashTable에서는 이러한 방식을 사용중인데 이 방식도 장단점이 존재하는데 

장점은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며 삭제 작업이 간단하다는 장점과

단점은 데이터의 수가 많아지면 그만큼 연결되는 리스트 또한 많아지며 캐시의 효율성이 떨어집니다

Open Addressing

이 방식은 해시 테이블에 바로 데이터의 저장이 가능합니다 

대표적인 예로 3가지 방식이 존재하는데 

1. Linear probing

- 선형탐사를 말합니다 버킷의 자리에 더 이상의 데이터의 삽입이 불가하다면 차례대로 검색해 비어있는 버킷에 데이터를 저장하는 방식입니다

2. Quadratic probing

- 해시의 저장순서 폭을 제맘곱으로 저장하는 방식입니다 예를들어 처음에는 1^2, 2^2 이러한순서로 버킷의 저장순서의 폭을 늘려나가는 방식입니다

3. Double hashing probing

- 해시의 값을 한번더 해싱하여 해시의 규칙성을 없애버리는 방식입니다.

충돌 방지법은 데이터의 규칙성을 방지하는 즉 클러스터를 방지하기 위한 방식이지만 치명적인 단점이 존재하는데 공간의 초과입니다

만약 새로운 값을 해시테이블에 저장을 하려 하는데 사이즈가 꽉차서 넣지 못한다면? 

그러한 상황에서는 동적으로 사이즈를 늘려줘야하는데 이를 늘리는 방식은 여러가지지만 하나를 예시로 들면

1. 새 해시 테이블을 할당하지만 이전 해시 테이블을 삭제하지 않고, lookup 과정에서 두 테이블 모두 체크한다.
2. 데이터가 삽입될 때마다 새 테이블에 저장하고 특정 k 만큼 이전 테이블에서 새 테이블로 데이터를 이전한다.
3. k 만큼 데이터를 옮기다가 이전 테이블에 저장된 데이터가 없으면 이전 테이블을 free 한다.

그러나 테이블의 확장은 매우 심각한 성능의 저하를 나타내며 가급적이면 확장을 하지않도록 테이블을 설계하고 수를 제어하는 방법이 필요합니다

물론 해싱을 하는 해시 함수가 뛰어나다면 이러한 성능 저하를 나타낼 수는 적어질것입니다

대표적인 해시 함수들은 다음과 같은데 

1. Division Method 

- 대표적인 나눗셈 법으로 테이블의 사이즈는 소수가 되는쪽이 효율적이라 합니다

주소 = 입력 값 % 테이블의 사이즈 입니다

2. Multiplication Method

- 숫자의 각 자릿수를 더해 해시 값을 만드는 방식으로 문자열의 해시방식에 잘 어울리는 기법입니다

3. Universal Hashing

- 다수의 해시 함수를 만들고 그 중하나를 랜덤으로 선택해 해시값을 만드는 기법

마무리하며

해시테이블은 매우 필수적인 자료구조이며 실제 실무에서도 많이 사용된다고합니다

확실히 값을 O(1)로 찾을수있다는 장점은 매우 특별하고 중요하다고 생각하는데 그만큼 쉽지 않은 자료구조 중 하나라 생각하고

이를 응용할 수 있도록 여러가지 알고리즘 문제를 풀어봐야겠습니다 :)

(보시면서 이상한 점이나 추가해야 할점은 언제든지 남겨주신다면 정말 감사하겠습니다!! )