Hash Table

< 해시 테이블이란? >

도서관에서 책을 분류하는 기준없이 꽂았다고 생각을 해보자.

우리는 책을 어떻게 찾을까? 자신이 원하는 책을 찾을 때까지 모든 책을 탐색할 것이다.

이 경우, 하나의 책을 확인하는데 걸리는 시간이 1초라고 가정하고 마지막 책을 확인했을때 책을

찾았다면 시간은 (도서관에 존재하는 책의 개수)초 만큼의 시간이 걸릴 것이다.

 

그렇다면 지금 우리의 도서관에서는 책을 찾는데 얼마나 시간이 걸릴까?

책의 제목의 맨 처음 글자로 구분했고 우리의 눈앞에 책장들이 있고 책장엔 책 하나씩만

있다고 가정했을때, '가장' 이란 책을 찾는데는 1초가 걸릴 것이다.

 

탐색에서 가장 쉽게 찾는 것은 무엇을 의미할까?

요소들을 하나하나 들여다볼 필요없이 '즉시' 검색하는 것이다.

그리고 이를 구현할 수 있는 추상 자료형이 해시 테이블이다.

 

해쉬 테이블은 배열과 해시 함수 두 부분으로 구성된다.

배열 - 실제 데이터를 담는 부분.

해시 함수 - 데이터를 어디에 둘 것인지 결정하는 부분.

도서관에서 책장을 해시 맵으로 재구성하면 모든 책장이 빈 상태로 시작하고 거기에 책이란 데이터를

추가하기 위해서 해시 함수에게 책을 전달한다.

해시 테이블이 매우 효율적인 이유는 두 데이터 세트 간의 관계인 매핑을 생성하기 때문이다.

해시 테이블은 key와 value로 데이터 세트가 구성된다. 배열로 작업하기에 key는 배열의 인덱스이고 value는

해당 인덱스에 저장된 데이터이다. 해시 함수의 역할은 항목을 입력받아 key를 계산하고 반환하는 것이다.

 

앞에서 예를 든 것처럼 맨 앞의 글자를 그대로 이용하여 책장을 의미하는 해시 버킷이란 곳에 저장되야한다.

하지만 이 경우 겹쳐서 collision, 충돌이 발생할 수 있다. 즉, 배열에서 같은 위치, 동일한 해시 버킷에 

여러 요소가 삽입되는 경우이다. 이것을 통해 알 수 있는 것은 해시 함수가 제공하는 모든 항목에 대해서

항상 고유한 해시 버킷 값을 반환하지 않을 것이다를 확신할 수 있다. 일반적으로 데이터 세트의 크기가

해시 테이블의 크기보다 크기 때문에 항상 동일한 해시 버킷에 여러 요소를 입력한다.

실제 문제에 적용되는 해시 테이블의 좋은 예는 전화번호부이다. 전화번호부는 하나의 초성에는 해당 성을

가진 많은 사람들이 있다. 이는 초성이란 해시 버킷에 많은 데이터 조각이 있다는 것이다.

 

다른 예로 20대 사람 수를 해시 테이블로 나타냈을 때, 10개의 해시 버킷이 나타날 것이고 거기엔

사람의 수가 거의 균등할 것이다. 이 균등함이 해시 알고리즘을 만드는 중요한 부분이다.

가능한 모든 해시 버킷 간에 데이터를 균등하게 분배해야한다. 이점을 기억하면 좋을 것 같다.

 

맨 처음 언급했던 해시 테이블의 효율성에 대해 알아보자.

해시 테이블없이 배열이나 링크드 리스트를 이용하면 요소를 찾기 위해선 선형 탐색을 거쳐야한다.

그럼 O(N)의 시간 복잡도를 가진다. 가장 빠르게 한다고 하면 배열을 이용하여 정렬 후 이진탐색을 

하는 것인데 이것도 O(logN)의 시간 복잡도를 가진다. 하지만 해시 테이블을 이용하면 내가 원하는

요소가 키로 존재한다면 O(1)로 데이터를 매우 빠르고 쉽게 도출할 수 있다. 물론 제거도 O(1)이고 삽입

 또한 O(1)이다. 이는 해시 함수에 의존하여 추가, 제거할 위치를 결정하기 때문에 즉시 도출이 된다.

 

< 해시 테이블의 문제점 >

해시 테이블의 문제점을 알기 위해 '무엇이 좋은 해시 테이블일까?' 를 생각해보자.

되게 간단하게 해시 함수가 기능을 잘하면 되는 것이다. 이를 세분화해서 보면

1. 계산하기 쉬운 해시 함수

2. 충돌이 일어나지 않는 해시 함수

3. 모든 입력 데이터에 사용할 수 있고 하나의 value가 주어졌을때 매번 같은 key를 반환하는 해시 함수

 

이유가 뭘까?

1. 계산하기 너무 어려운 것은 공간을 너무 많이 차지한다. 값 비싼 함수는 효율적인 데이터 구조를 찾는

    목적을 달성하지 못한다.

3. 해시 함수는 모든 데이터를 처리해야하고 같은 value에 대해선 항상 같은 key를 반환해야한다. 그렇지

    않다면 검색을 할 수가 없을 것이다. -> 그 정보를 믿을 수가 없기 때문.

 

마지막으로 collision, 충돌이 남았다. 앞서 말했듯 같은 해시 버킷에 값을 삽입하려 했을 때 충돌이 일어난다.

거의 모든 해시 함수는 언젠간 충돌이 발생한다. 이게 발생하지 않는 경우는 모든 키값이 중복되지 않는

완벽한 해시 함수의 경우이다. 이것은 데이터 세트의 개수가 이 해시 버킷의 개수보다 작지 않은 이상

불가능하다. 그렇기에 충돌은 무조건 발생한다고 생각하고 처리하는 방법을 이해해야한다.

 

해시 함수에서 충돌을 처리하는 몇 가지 방법이 존재하고 그 중 어느 것도 반드시 사용하기에 옳은 전술은

아리라는 점을 기억하자. 데이터 세트, 해시 테이블의 크기, 테이블을 이용하여 수행하려는 작업에 따라

달라진다.

 

해시 함수에 사용되는 가장 일반적은 충돌 해결 전술 2 가지를 알아보자.

Linear Probing, 선형 프로빙

이 방법은 충돌이 발생했을 때 다음 빈 해시 버킷을 찾는 것이다.

단순히 다음 빈 버킷으로 이동하여 요소를 추가하는 것이고 일종의 재해싱이며 선형 탐색이라고 볼 수 있다.

이는 다음 해시 버킷도 차있다면 빈 버킷을 찾을 때까지 선형 탐색을 해야하고 끝으로 간 경우 순환해야한다.

즉, 해시 테이블의 끝에 도달하면 처음으로 돌아가야한다.

그러나, 이 방법의 단점은 단순히 다음 빈 해시 버킷으로 이동하고 삽입하는 행위가 clustering, 군집화를

일으킨다. 군집화는 데이터가 삽입되는 곳이 한 영역으로 몰리는 것을 의미한다. 군집화는 해시 테이블에 

좋지 않다. 이는 정의에 따라 잘못 설계되었음을 의미한다. 그리고 해시 함수의 내부에 문제가 있는 것이다.

군집화로 이어지는 두 가지 문제가 존재하는데 해시 함수가 전체 해시 테이블 범위를 사용하지 않거나 해시

테이블의 해시 버킷 전체에 데이터가 고르게 분산되지 않는 것이고 이 두 가지 모두 선형 프로빙으로 인해

발생하여 군집화가 일어난다.

하지만 만약 테이블이 데이터 세트를 수용할 만큼 충분히 크다면 선형 프로빙은 충돌을 처리하는

훌륭한 솔루션이 될 수도 있다.

Chaining, 체이닝

충돌 해결을 위한 두번째 방법은 해시 함수 자체의 구조를 변경하는 것입니다.

선형 탐색의 단점을 처리하고 군집화 문제를 해결해야 하는 것보다 하나의 해시 버킷에 여러 항목을 저장할

수 있다면 좋을 것이다. 

체이닝을 구현하기 위해선 하나의 키에 여러 요소가 저장될 수 있어야한다. 이를 위해서 linked list, 링크드

리스트를 이용한다. 각 해시 버킷에 단일 항목을 저장하는 대신 테이블의 각 키에 링크드 리스트를 참조하는

포인터가 있도록 구현해서 여러 요소를 함께 연결하는 것이다. 충돌이 발생해도 요소를 추가하는 것이 쉽다.

체이닝에도 단점은 존재한다. 해시 버킷에서 원하는 값을 찾기 위해선 O(n)의 시간이 걸리는 선형 탐색을

해야한다. 이것은 해시 버킷이 하나로 집중이 되고 링크드 리스트가 길어진다면 분명 엄청 큰 문제가

될 것이다. 하지만 해시 함수가 전체 해시 버킷에 잘 배포한다면 괜찮을 것이다. 좋은 해시 함수를 사용한다면

체이닝은 여전히 평균 검색 시간을 가진다. O(n) 또는 일정한 조회 시간.

 

두 가지 접근 방식은 장점과 단점이 완전 다른 접근 방식이다.

이 두 가지 접근 방식 모두 해시 함수를 잘 사용한다면 모두 강력한 기술이 될 수 있다.

모든 도구에는 장단점이 있다는 것을 기억하자.

 

< 참조 > - 참조 링크엔 그림이 있어 더 이해하기 좋습니다!!

- https://medium.com/basecs/taking-hash-tables-off-the-shelf-139cbf4752f0

Taking Hash Tables Off The Shelf

- https://medium.com/basecs/hashing-out-hash-functions-ea5dd8beb4dd

Hashing Out Hash Functions