IM 8일차 (Hash Table)

1. 해시 테이블

 

  key와 value로 이루어진 데이터에서 key를 해시 함수를 통해 해싱된 index로 하고

  그 index에 value 값이 저장되는 자료구조를 해시 테이블이라고 한다.

 

  해시 테이블의 장점은 데이터의 삽입, 삭제, 조회가 빠르다는 것에 있다.

  물론 좋은 해시 함수를 통해 해싱을 해야 한다는 것과 충돌이 났을 때 충돌을 잘 해결하는 구현이 필요하다.

 

  다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다고 한다.

  물론 해시충돌 자체를 줄이는 것도 의미가 있겠습니다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다.

 

 

 

2. chaining

 

  해시충돌 문제를 해결하기 위한 아이디어 가운데 하나는 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것이다.

 

  해당 버킷에 데이터가 이미 있다면 마치 연결리스트처럼 노드가 노드를 가리키도록 하기 때문에 체인이라는 말이 붙은 것 같다.

  유연하다는 장점을 가지나 메모리 문제를 야기할 수 있다.

 

  또한 그럴 일은 잘 없겠지만 최악의 경우 한 버킷에 모든 데이터가 들어있어 조회와 삭제의 경우 시간복잡도가 O(n)이 될 수 있다.

 

 

 

3. open addressing

 

  open addressing은 chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이다. 

  그럼 이 경우엔 충돌을 어떻게 해결하느냐?

 

  3 - 1) 선형 탐사

 

    선형 탐사는 한 번에 한 인덱스를 증가시킴으로써 사용 가능한 인덱스를 찾는다.

    예를 들어 'a' 라는 key 와 'b' 라는 key가 동일한 해시값 3을 가진다고 하면 'a'의 value는 3에 들어갈 것이다.

   

    반면 'b'의 value는 3의 자리에 이미 데이터가 존재하기때문에 선형탐사 방식을 이용해 그 다음 빈자리인 4에 들어갈 것이다.

    이러한 방법을 선형 탐사라 한다.

  

    선형 탐사의 단점은 동일한 해시 값을 가지는 키가 많이 존재할 경우 데이터를 조회할 때 순회가 필요하다는 것이다.

    데이터를 조회할 때도 해시 함수를 통해 얻어진 해시 값으로 인덱스를 찾아서 데이터를 조회해야하는데

    만약 그 인덱스에 원하는 데이터가 없는 경우 해당 인덱스부터 시작해서 인덱스를 1씩 증가시켜 반복을 통해 확인해야 한다는 것이다.

 

  3 - 2) 이차 탐사

 

    이차 탐사는 이러한 선형 탐사의 문제를 보완하기위해 도입된 기법이다.

    이차 탐사는 충돌이 일어나는 경우 매번 1씩 증가시키는 선형탐사와 달리 완전 제곱을 사용한다.

    물론 선형 탐사보다는 덜 하지만 이차 탐사 또한 규칙적으로 인덱스를 증가시켜 데이터를 저장하기 때문에 마찬가지로 순회는 필요하다.

 

  3 - 3) 이중 해싱

 

    이중해싱(double hashing)은 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법이다.

    앞서 선형 탐사와 이차 탐사에서의 문제점이 clustering이라고 할 수 있다.

 

    2개의 해시함수를 통해 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다.

    이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 clustering을 모두 완화할 수 있다.