자료구조 시리즈

자바스크립트로 자료구조 공부하기 04

해시 테이블에 대해서

해시 테이블에 대한 개념 정리와 코드 이해는 evan-moon님의 블로그를 많이 참고하였습니다. 정말 감사합니다.

해시 테이블은 무엇인가?

해시 테이블은 어떠한 특정 데이터를 받아 인덱스를 가진 구조로 저장하는 자료구조이다. 그 과정에서 값을 해싱함수에 넣어 해시코드를 만드는 과정이 있다. 함수를 통해서 해시코드를 만드는 과정을 해싱이라고 한다. 아직은 낯선 개념인데 차차 계속 알아가보자.

해시 함수는 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑해준다. 해시 함수를 이용해서 해시코드를 만드는 것은 보통 암호화하는 단계로 불린다.

직접 주소 테이블

evan님의 블로그에서는 직접 주소 테이블을 먼저 설명한다. 해시 테이블의 개념이 직접 주소 테이블과 밀접하기 때문이다. 여기서 직접 주소 테이블은 입력받는 데이터의 값(value)이 저장소의 키가 되는 매핑 방식이다. 아래에 해당하는 인덱스에 해당하는 값이 들어가는 직접 주소 테이블 예시가 있다. 코드를 보면서 직접 주소 테이블의 장점에 대해 알아보자

직접 주소 테이블의 장점

값이 저장된 공간에 인덱스로 바로 접근하여 값을 가져올 수 있다.
값을 수정, 삭제, 삽입하는 과정도 값의 인덱스를 기반으로 바로 할 수 있다.
데이터를 처리하는 시간 복잡도가 O(1)이라고 할 수 있다.

class DirectAddressTable {
   constructor() {
      this.table = [];
   }

   setValue(value = -1) {
      this.table[value] = value;
   }
   getValue(value = -1) {
      this.table[value]
   }
   getTable() {
      return this.table;
   }
}

const table = new DirectAddressTable;
table.setValue(3)
table.getTable() // [empty × 3, 3]   ->  3번 인덱스에 3이 들어간 모습을 볼 수 있다.

위의 직접 주소 테이블은 빠르게 데이터를 처리할 수 있다는 장점이 있지만, 무의미한 메모리 할당이 공간 많이 되는 단점이 있다. 공간 효율성이 떨어지는 것이다. 값은 없지만 메모리에 데이터가 할당되는 상태가 있는 것이다. 이러한 공간 효율성 낭비를 방지하기 위해서 우리는 해시 테이블의 개념을 알아야 한다.

그래서 해싱을 어떻게 사용하는데?

해시 함수의 특성

해싱만 보고는 인자로 어떤 데이터를 입력 받았는지 추측하기 힘들다. > 암호화
고정된 테이블의 길이를 정하고 그 길이 안에서만 데이터를 저장할 수 있다. 아래의 해시 함수는 들어오는 데이터를 10으로 나눈 나머지를 반환한다. 그러면 해싱 저장 길이를 0 ~ 9로 한정시킬 수 있다.

const hashTableTest = new Array(9);  // 길이가 9인 배열 생성

function hashFunc(data) {
   return data % 10
}

hasTableTest[hashFunc(100)] = 100
hasTableTest[hashFunc(101)] = 101
hasTableTest[hashFunc(102)] = 102
hasTableTest[hashFunc(103)] = 103

// hasTableTest = [100, 101, 102, 103, empty ..., empty]

해시 테이블을 생성할 때 고정적인 공간을 지정하고 값을 넣기 때문에 동일한 인덱스간의 해시 충돌이 일어날 수 있다. 위의 예시에서 111이 들어간다면 1번 인덱스에 두 값이 충돌된다.

그래서 우리는 해싱 충돌을 방지하거나 충돌을 우회할 수 있는 방법들을 사용해야 한다.

해싱 충돌 해결하기 01 - 개방 주소법

해시 충돌이 발생하면 테이블 안의 비어있는 인덱스를 조사하여 빈 곳에 충돌된 데이터를 넣는 방식이 ‘개방 주소법’이다. 해시 함수를 이용하여 얻는 인덱스에 넣는 것이 아니다.

01.선형탐사법

개념 : 충돌이 일어난 인덱스 바로 옆에 인덱스를 내어주는 방법.
단점 : 이미 다음 인덱스들에 값이 채워져 있으면 다시 충돌이 발생한다. 이러면 그 뒤에도 충돌이 발생할 확률이 높아지고 저장 덩어리가 커지게 된다. (악순환 반복)

02.제곱탐사법

개념 : 충돌이 일어난 인덱스로부터 1제곱, 2제곱, 3제곱.. 떨어진 인덱스에 저장하는 방법
방식 : 충돌이 한 번 일어나면 해당 인덱스에서 1제곱 떨어진 곳에 저장. > 다시 충돌이 발생하면 그 시점에서 2제곱 떨어진 곳에 저장 …
단점 : 선형탐사법 보다는 밀집도가 떨어지지만, 충돌이 여러번 발생하여 데이터가 결국 군집화 될 가능성이 많다. (이차 군집화)

03.이중해싱

개념 : 해싱 충돌시 탐사하는 이동폭을 얻기 위하여 해시 함수를 이중으로 사용하는 방법
방식 : 기존 해시함수는 최초 해시를 얻기 위함, 이중 해시함수는 충돌시 다시 해시를 거쳐서 탐사하는 용도.

const tableSize = 23;  // 소수를 이용하는 것이 이중 해시에 편하다.
const hashTable = [];

// 최초의 해시를 만들어내는 함수 -> 데이터의 최초 주소를 만든다고 생각!
const hashMaker = value => value % tableSize;

// 이중해싱을 위한 함수 -> 테이블 사이즈보다 작은 수를 사용한다.
const againHash = value => 17 - (value % 17)

// hashTable에 저장하는 함수
const setHash = value => {
   
   // 우선 최초 해시를 만든다. > 저장할 공간을 찾는 것
   // 그 다음에는 충돌 여부를 판단할 값 자체를 지정
   let idx = hashMaker(value);
   let target = hashTable[idx];

   // 반복적으로 탐색하여 충돌방지
   while (true) {
      if (!target) {
         // 저장소에 충돌이 없으면 저장
         hashTable[idx] = value;
         return; // 반복문 종료
      }

      // 저장소에 다 차면 종료
      else if (hashTable.length >= tableSize) {
         return;
      }

      // 충돌이 발생하면
      else {
         idx += againHash(value); // -> idx를 새롭게 지정해준다. 
         idx = idx > tableSize ? idx - tableSize : idx;  // 저장소 길이보다 크면 다시 
         target = hashTable[idx]; // -> 다시 반복문을 타게 된다. 
      }
   }
}

위의 코드가 복잡해보일 수 있다. 천천히 다시 구조를 살펴보고 콘솔에 값을 하나씩 찍으면서 연습하면 도움이 많이 될 것 같다.

해싱 충돌 해결하기 02 - 분리 연결법

분리 연결법은 해시 버켓(저장소) 안에 하나의 값을 넣는 것이 아니라, 연결 리스트나 트리 구조 형태로 데이터를 넣는 방법이다.

연결 리스트를 하나의 버켓에 넣는 경우 꼬리 노드 부분에 데이터를 붙이면 탐색 과정이 길어진다. 그래서 보통은 머리 노드에 데이터를 붙인다.
분리 연결법을 활용하기 위해서는 해시 함수 역할이 아주 중요하다. 균일하지 못한 해시함수라면 하나의 버켓에 저장된 리스트, 트리의 구조만 커질 수 있기 때문이다.
분리 연결법은 직접 코드를 만나봐야 더 이해가 잘 될 것 같다. (검색 필요)

오늘은 해시 테이블에 대해서 evan-moon님의 블로그를 기반으로 정리했다. 나 스스로도 이런 콘텐츠를 작성할 수 있도록 계속 공부에 매진해야 한다. 정말 많은 도움이 되었다. 감사합니다!