[Javascript] Hash(해시) - 해시 테이블(hash table) 구현하기

 

 

해시란?

해시 함수(hash function)는 에서 얻어지는 값은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.

해시 함수에 의해 얻어지는 값을 해시라고 부릅니다.

해시함수의 용도 중 하나는 해시 테이블 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에서 널리 사용됩니다.

해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터 검색이나 테이블 검색의 속도를 가속합니다.

 

해시가 데이터 매우 빠른 데이터 검색을 할 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값(value)이 한 쌍으로 존재하고, key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됩니다.

 

const parson = {};
person['firstName'] = 'sewon';
person['lastName'] = 'Jang';

위 코드는 string 자료형의 key에 해당하는 공간을 string 자료형의 value를 집어넣은 것 입니다. 이렇게 키와 값의 형태로 데이터를 저장하는 구조를 자바스크립트의 object나 map으로 구현할 수 있습니다. 이들은 모두 해시 테이블의 일종입니다. 

 

---

1. Hash Table 생성하기

class HashTable{
	table = new Array(100);
    
    setItem = (key, value)=>{};
    
    getItem = (key) =>{
    	return '';
    };
}

setItem에서는 key, value를 파라미터로 받아서 table에 넣어주고, getItem에서는 ㅏey를 파라미터로 받아 table의 key에 맞는 value를 불러오도록 할 것 입니다.

 

cosnt newTable = new HashTable();

newTable.setItem('firstName', 'Sewon');
newTable.getItem('firstName');

다음과 같이 newTable에 firstName이 key인 값으로 Sewon을 setItem으로 지정해주고, getItem을 통해서 Sewon을 가져오고 싶을 때, setItem은 다음과 같다고 생각할 수 있습니다.

 

setItem = (key, value) => {
	table['firstName'] = 'Sewon';
}

하지만 이것은 틀린 방법입니다.

array는 인덱스 숫자로만 접근할 수 있는데, 위처럼 String을 key로 이용할 수 없습니다.

따라서 String 값을 해시 테이블에 넣어 주려면 String 자료형을 number 자료형으로 바꾸어서 해당 number 인덱스에 데이터를 저장하도록 해야 합니다.

이를 바로 hash function, 해시 함수라고 합니다.

 

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

function hashStringToInt(s){
	return 3;
}

다음 함수를 선언해줬습니다. 그리고 setItem 함수를 다음과 같이 선언해 주었습니다.

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

key에 어떠한 값을 넣던 idx는 3이 되어 table[3]에 저장될 것입니다.

 

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

getItem도 어떤값을 key로 넣던 table[3]의 값을 리턴하도록 되어 있습니다.

 

하지만 함수를 만들어서 firstName, lastName에 무엇을 하던 key가 3이되어 마지막으로 set한 value만이 3으로 들어가 return 될 것입니다.

 

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

 

위와 같이 무조건 3만 리턴하게 된다면 값을 세팅하고 가져오는 과정에서 인덱스가 중복이 되어 데이터를 유실하거나 성능이 저하됩니다.

복수의 key가 동일한 메모리 주소 값으로 변환되는 경우를 hash collision, 해시 충돌이라고 합니다.

 

	function hashStringToInt(s) {
    	let hash = 17;
        
        for(let i=0; i<s.length; i++){
        	hash = hash * s.chatCodeAt(i);
        }
    	
        return hash;
    }

 

해시 함수를 작성하는 한 가지 방법은 key로 들어오는 문자열을 charCode로 변환한 값을 활용하는 것 입니다.

(chatCodeAt() 메서드는 주어진 인덱스에 대한 UTF-16 코드를 나타내는 0부터 65535 사이의 정수를 반환합니다.)

문자열을 하나씩 돌면서 숫자로 바꿔준 후, 그 숫자를 해시 테이블의 인덱스를 계산하는 데 화용하는 것입니다.

꼭 이렇게 작성하지 않고 자신만의 방법으로 해시 함수를 구현할 수 있고 또 기업체나 라이브러리에서는 엄청나게 복잡한 해시 함수를 구현해 놓았을 수 있습니다.

위는 연습 문제에서 흔하게 나오는 방법 중 하나로 작성되었습니다.

 

(stackoverflow에서 hash되는 함수를 질문하였을 때 다양한 대답이 나오는 것을 볼 수 있습니다.)

https://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript

Generate a Hash from string in Javascript

 

위의 방법으로 숫자로 변환한 값을 더하기만 한다면 기존에 지정해 준 table의 길이보다 훨씬 커지기 때문에, table의 길이로 hash를 나눈 나머지를 해당 key의 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;
}

 

따라서 tableSize를 함께 파라미터로 받도록 작성했습니다. 그리고 소수도 한 번 씩 더 곱해줍니다.

꼭 13일 필요는 없지만 key를 더욱 효율적으로 분산하기 위해 임의로 고른 소수입니다. 

다음을 적용하게 된다면 값이 적절하게 분산되어 해시 테이블에 저장되고 있다는 것을 확인 할 수 있습니다.

 

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];
  };
}

완성된 로직은 다음과 같습니다.

 

 

---

참고:

 

https://eunjinii.tistory.com/m/87

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