자바스크립트로 해시테이블 구현하는 방법

---

const person = {};
person['firstName'] = 'eunjin';
person['lastName'] = 'lee';

 

위 코드는 string 자료형의 key에 해당하는 공간에 string 자료형의 value를 집어넣은 것이다. 이렇게 키와 값의 형태로 데이터를 저장하는 자료 구조를 자바스크립트의 object나 map, 파이썬의 dictionary 등으로 구현할 수 있다. 이들은 모두 해시 테이블의 일종이다. 자료구조를 공부할 때 흔히 이야기하는 해시 테이블이라 함은 특정 오퍼레이션에 대해 시간복잡도를 해결해야 할 때, 원하는 값을 key로 사용하는 자료구조다. 해시 테이블이 무엇인지 공부하고 자바스크립트로 해시 테이블을 짜는 방법을 정리해 보았다. 

 

---

1. Hash Table 생성하기

 

먼저 클래스를 생성한다. 

class HashTable {
  table = new Array(100);

  setItem = (key, value) => { };

  getItem = (key) => { 
    return '';
  };
}

table을 길이가 100인 배열로 선언하고, setItem과 getItem을 선언해 준다. table을 그냥 table = [];로 초기화해 주지 않고 길이를 명시해 주는 이유는 나중에 특정 상황에서 길이를 늘리고자 함이다. (해시 충돌에 대응하기 위한 방법 중 하나다.)

setItem에서는 key, value를 파라미터로 받아서 table에 넣어주고, getItem에서는 key를 파라미터로 받아 table에 해당 키에 해당하는 값을 불러오도록 할 것이다. 

 

const myTable = new HashTable();
myTable.setItem('firstName', 'eunjin');
myTable.getItem('firstName');

console.log(myTable.getItem('firstName')); // [empty string]

myTable을 생성자 함수로 만든 후, setItem으로 'firstName' 키에 'eunjin' 값을 넣어 주고, getItem으로 'firstName' 키에 대한 값을 불러와 본다. 현재는 setItem에서 아무런 로직도 작성하지 않았기 때문에 firstName은 빈 문자열로 나온다.

 

setItem = (key, value) => {
    table['firstName'] = 'eunjin'; // 잘못된 예시
}

setItem은 key와 value 쌍으로 데이터를 집어넣어 준다. 그런데 array는 인덱스 숫자로만 접근할 수 있다. 위처럼 string을 key로 이용할 수 없다는 의미다. 따라서 string 값을 해시 테이블에 넣어 주려면 string 자료형을 number 자료형으로 바꾸어서 해당 number 인덱스에 데이터를 저장하도록 해야 한다. 이렇게 해시 테이블의 키를 number 자료형으로 만드는 어떤 함수를 hash function, 해시 함수라고 한다. 

 

2. 해시 함수(Hash Function)가 필요한 이유

 

function hashStringToInt(s) {
    return 3;
}

hashStringToInt 함수를 선언해 준다. 일단은 그냥 숫자 하나를 리턴하게 해 놓아 본다. 

 

  setItem = (key, value) => {
    const idx = hashStringToInt(key);
    this.table[idx] = value;
  };

그리고 setItem을 다음과 같이 작성한다. 이제 key로 어떤 string이 들어오든, hashStringToInt 함수를 통해 string이 number로 인덱스화해서 table에 값이 저장될 것이다. 지금으로선 어떤 string이 들어오든 해시 함수를 통해 table[3]에 저장될 것이다.

 

  getItem = (key) => {
    const idx = hashStringToInt(key);
    return this.table[idx];
  };

getItem에서도 값을 가져오기 원하는 key를 해시 함수로 변환해서 table[3]의 값을 리턴하도록 한다.

 

const myTable = new HashTable();
myTable.setItem('firstName', 'eunjin');

console.log(myTable.getItem('firstName')); // eunjin

이렇게 firstName이 드디어 eunjin으로 리턴이 된다. 그런데 위에서 만들어 둔 해시 함수는 항상 5를 리턴하기 때문에 어떤 값을 setItem으로 table에 저장해도 같은 인덱스 3에 덮어씌워 저장이 될 것이다. 

 

const myTable = new HashTable();
myTable.setItem('firstName', 'eunjin');
myTable.setItem('lastName', 'lee');

console.log(myTable.getItem('firstName')); // lee

이렇게 lastName 키에 lee 값을 넣어 줬는데, firstName을 꺼내 봤더니 lee가 나온다. 해시 함수에서 무조건 키를 3으로 리턴하도록 해서 제대로 값이 저장되지 않고 있다.

 

3. 해시 함수 작성하는 방법

 

해시충돌 설명

 

해시 충돌을 방지하기 위해서는 해시 함수가 key의 분포를 최대한 분산하도록 작성해야 한다. 아까처럼 숫자 3만 리턴하게 된다면 값을 세팅하고 가져오는 과정에서 인덱스가 중복돼 데이터를 유실하거나 성능이 저하된다. 복수의 key가 동일한 메모리 주소 값으로 변환되는 경우를 hash collision, 해시 충돌이라고 한다.

 

function hashStringToInt(s) { 
  let hash = 17;

  for (let i = 0; i < s.length; i++) { 
    hash = hash * s.charCodeAt(i);
  }
  return hash;
}

해시 함수를 작성하는 한 가지 방법은 key로 들어오는 문자열을 charCode로 변환한 값을 활용하는 것이다. 문자열을 하나씩 돌면서 숫자로 바꿔준 후, 그 숫자를 해시 테이블의 인덱스를 계산하는 데 활용하는 것이다. 꼭 이렇게 작성 안 하고 자신만의 방법으로 해시 함수를 구현할 수 있고 또 기업체나 라이브러리에서는 엄청나게 복잡한 해시 함수를 구현해 놓았을 수 있다. 연습 문제에서 흔하게 나오는 방법 중 하나로 작성해 보았다.

 

일단 hash라는 변수에 17을 할당을 해 주었다. 해시 테이블에서는 주로 테이블의 크기나 각 자릿수에 곱할 값을 소수로 지정하는데, 그 이유는 좀 더 효율적인 key 분산을 위해서다. 그리고 for문을 돌면서 각 문자를 charCodeAt으로 변환해 준 값에 hash를 곱한 수를 하나씩 더해준다.

 

function hashStringToInt(s, tableSize) { 
  let hash = 17;

  for (let i = 0; i < s.length; i++) {
    hash = (13 * hash * s.charCodeAt(i)) % tableSize;
  }
  return hash;
}

그런데 단순히 숫자로 변환한 값을 더하기만 한다면 기존에 지정해 준 table의 길이보다 훨씬 커지기 때문에, table의 길이로 hash를 나눈 나머지를 해당 key의 hash로 만들어 준다. 따라서 tableSize를 함께 파라미터로 받도록 작성한다. 그리고 소수도 한 번씩 더 곱해준다. 꼭 13일 필요는 없지만 key를 더욱 효율적으로 분산하기 위해 임의로 고른 소수 중 하나다. 이렇게 해시 함수 한 개가 완성됐다.

 

const myTable = new HashTable();
myTable.setItem('firstName', 'eunjin');
myTable.setItem('lastName', 'lee'); 

console.log(myTable.getItem('firstName')); // eunjin
console.log(myTable.getItem('lastName')); // lee

앞서 해시 함수를 대충 작성해서 해시 충돌이 일어났을 때와는 달리, 각각 넣어준 'firstName', 'lastName' key에 대한 값이 적절하게 분산되어 해시 테이블에 저장되고 있다는 것을 확인할 수 있다.

 

class HashTable {
    table = new Array(71);

    // ...
}

또 해시 함수에서 각 자리의 숫자를 더한 값을 테이블의 길이로 나눈 나머지를 인덱스로 지정하기 때문에 테이블의 길이도 다시 적당한 소수로 다시 만들어준다.

 

---

 

function hashStringToInt(s, tableSize) {
  let hash = 17;

  for (let i = 0; i < s.length; i++) {
    hash = (13 * hash * s.charCodeAt(i)) % tableSize;
  }
  return hash;
}

class HashTable {
  table = new Array(71);

  setItem = (key, value) => {
    const idx = hashStringToInt(key, this.table.length);
    this.table[idx] = value;
  };

  getItem = (key) => {
    const idx = hashStringToInt(key, this.table.length);
    return this.table[idx];
  };
}

지금까지 완성된 자바스크립트 해시 테이블 로직이다. 다음 글에서는 해시 충돌이 일어나는 경우 어떤 방법을 사용하여 해결할 수 있는지 정리할 것이다.

 

> 자바스크립트 해시 테이블 충돌 해결하는 2가지 방법