해시 테이블

유키미아우·2023년 10월 11일

본 포스팅은 Colt Steele의 JavaScript 알고리즘 & 자료구조 마스터클래스를 수강하며 정리한 노트입니다.
https://www.udemy.com/course/best-javascript-data-structures/

195. 해시 테이블 소개

해시 테이블은 해시맵이라는 이름으로도 잘 알려져 있다.
해시 테이블은 배열과 마찬가지로 자바스크립트, 파이썬, 루비, 자바스콜라 등의 많은 프로그래밍 언어에 내장되어 있다.

❗️ 그러나 만약에 이 내장된 해시테이블 기능이 없어졌다면?!

새로 키-값 데이터 저장법을 새로 써야하는 상황을 가정해보자!

이번 챕터에서는 해시 테이블의 원리인 해시 알고리즘에 대해서 공부한다.
그리고 해시 테이블에서 충돌이 일어나는 경우 사용하는 개별 체이닝, 선형 조사법에 대해 배운다.

해시테이블의 특징

해시 테이블은 어디서나 쉽게 찾아볼 수 있다.
키-값 쌍을 저장하는데 사용된다.
해시 테이블의 키는 순서를 가지지 않는다.
새로운 값의 추가, 제거가 아주 빠르다.
데이터가 연속적인 흐름을 가져야하는 경우 배열을 쓰고 그렇지 않으면 해시맵이나 해시 테이블이 어울린다. (e.g.) colors["cyan"]이 colors[2]보다 사람이 인식하기 편하다.
객체에서는 스트링만을 키로 사용할 수 있다.
자바스크립트에서는 객체(Object). 다른 언어에서는?
파이썬: 딕셔너리
자바, 고, 스칼라: 맵
루비: 해시

196. 해시 테이블에 대한 더 자세한 정보

데이터를 저장하고 접근할 때에 숫자 대신 단어를 사용한다면 사람이 읽을 수 있는 형태라 더 명료하다.
그러나 컴퓨터는 인덱스 "pink"나 "hello world"에 있는 것을 찾거나 거기에 삽입하는 방법을 모른다.
이 때 구원해주는 것이 해시 테이블이다!

pink를 0에서 99사이의 숫자로 변환할 방법: 해시 함수(Hash Function)

해시 함수는 스트링으로 된 키를 배열에서 사용되는 유효한 인덱스 숫자로 항상 일관되게 변환시켜야 한다.

예를 들어 pink는 0, cyan은 3, orangered는 7와 같이 항상 일관되게 같은 숫자로 변화시켜주어야 한다.

해시 함수는 보안이나 암호기술에 많이 적용되므로 이를 전문적으로 개발하고 연구하는 프로그래머 팀이 많다고 한다.

197. 해시 함수 소개

해시 함수는 전세계 인터넷과 개인 정보 보호, 일반 계산 업무 등에서 사용된다.
자바스크립트는 내장 해시 함수를 노출하지 않으나 파이썬에서는 직접 확인해볼 수 있다.

hash("Hello!")
7665438013419399415 // output

❇️ 좋은 해시 함수를 결정하는 기준:
1. 빨라야 하며 상수 시간이 소요되야한다. (i.e. costant time)
2. 일관된 방식으로 고르게 분배해서 충돌을 최대한 피해야함
3. 결정론적이어야 함 (deterministic) (멱등성)
same input - same output!

198. 첫번째 해시 함수 작성하기

어떻게하면 멱등성을 가지며 유니크한 값으로 변환시켜줄 수 있을까?

pink의 length를 활용해볼까? 그러나 많은 단어들의 length가 똑같으므로 쓸 수 없는 방법이다..

각 글자에는 UTF-16 숫자값이 있는데 이것을 활용해보도록 하자.

"a".charCodeAt(0); // 97
"hi".charCodeAt(0); // 104 number for h
"hi".charCodeAt(1); // 105 number for i

96을 빼면 알파벳의 순서값이 나온다고 한다.

"a".charCodeAt(0) - 96 // 1
"z".charCodeAt(0) - 96 // 26

이걸 스트링에 있는 모든 인덱스별 문자에 적용하여 합계를 내면 좋지 않을까?
한글자씩 루프 없이 수동으로 순회를 해보면 다음과 같다.

let total = 0;

total += "hello".charCodeAt(0) - 96 // 8
total += "hello".charCodeAt(1) - 96 // 13
total += "hello".charCodeAt(2) - 96 // 25
total += "hello".charCodeAt(3) - 96 // 37
total += "hello".charCodeAt(4) - 96 // 52

// total은 52

그리고 결과를 %(modular)를 통해서 우리가 원하는 크기의 배열범위 내부로 작게 줄여줄 수 있다.
modular? 나눈 뒤에 나머지 값을 반환하는 연산자

아래와 같이 아무리 큰 숫자라도 %를 이용하면 줄일 수 있다.

10002489325 % 10 // 5

위의 방법들을 종합하여 아래와같은 해쉬함수를 작성할 수 있다.

function hash(key, arrayLength) {
	let total = 0;

  	for (let char of key) {
      	let value = char.charCodeAt(0) - 96;
      	total = (total + value) % arrayLength;
    }

  	return total;
}

hash("pink", 10) // 0

해쉬 함수에 "pink"와 배열의 크기인 10을 매개변수로 1천번 호출하면 1천번 모두 일관되게 0이 결과로 반환됨을 확인할 수 있다.

그러나 아래와 같은 문제점이 있다.

string밖에 해쉬하지 못함.
상수시간이 걸리지 않고 O(n)임.
무작위성이 떨어지고 데이터가 뭉치기 쉬움.
(배열의 크기가 10밖에 안되면 일어날만한 일이긴 하지만..)

199. 해쉬 함수 성능 향상시키기

2번과 3번 문제를 개선해보자.

function hash(key, arrayLength) {
	let total = 0;
  	let WEIRD_PRIME = 31;

  	for (let i = 0; Math.min(key.length, 100); i++) {
      	let value = char.charCodeAt(0) - 96;
      	total = (total * WEIRD_PRIME + value) % arrayLength;
    }

  	return total;
}

hash("pink", 10) // 0

만약 string이 200자 300자 혹은 수백만자가 되면 시간이 매우 오래 걸릴 것이다.
따라서 탐색비용을 줄이기 위해 Math.min을 통해서 변환이 되는 문자개수를 설정해준다.
예를들어 30글자면 30개 모두 변환시키겠지만 100개를 초과한 경우 맨 앞 100개만 변환시켜주는 것이다.
해시테이블의 크기에는 소수(prime number)를 사용하자. 데이터가 더 퍼지고 무작위성이 강화될 수 있다.

소수(素數) 1과 자기 자신을 제외한 어떤 수로도 나누어떨어지지 않는 1보다 큰 자연수. 예: 2, 3, 5, 7, 11, 13, 17<

1000만패턴으로 분석해본 결과 소수였던 경우 충돌이 획기적으로 줄었다고 한다.

200. 충돌(collision) 처리

데이터가 많은 경우라면 충돌은 흔히 있을 수 있다.
해시테이블이 작고 해시함수의 성능이 안좋다면 더 자주 일어날 수 있다.

Separate Chaining

가 => 4
나 => 4

0 1 2 3 4 5 6 7 8 9
[][][][][][][][][][]
        ↑
      [["가", "값"],
      ["나", "값"]]

같은 인덱스에서 충돌하는 두 값을 배열이나 링크드리스트 형태로 함께 저장하기.

Linear Probing (open addressing의 방법 중 하나)

가 => 4
나 => 4


0 1 2 3 4 5 6 7 8 9
[][][][][][][][][][]
        ↑ 4가 이미 차있군.. 옆을 볼까?
        ["가", "값"]
          ↑ 5는 비어있네. 여기에 저장해야지.
      	  ["나", "값"]

각 위치에 하나의 데이터만 저장한다는 규칙을 지키는 방법.
충돌이 발생하면 다음 빈 슬롯을 찾아 저장한다.
그러나 배열의 공간이 금방 부족해진다는 단점이 있다.

이 밖에도 아래와 같은 방법이 더 존재.

제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장
이중 해시(Double Hashing): 다른 해시함수를 한번 더 적용한 해시 에 데이터를 저장

201. 해시 테이블 Set과 Get 메소드

class HashTable {
	constructor(size=53){ // 해시테이블 크기. 기본값은 소수인 53, 
    	this.keyMap = new Array(size);
    }
  
  	_hash(key) { // 해시 함수
    	let total = 0;
      	let WEIRD_PRIME = 31;
      	for (let i = 0; i < Math.min(key.length, 100); i++) {
        	let char = key[i];
          	let value = char.charCodeAt(0) - 96;
          
          	total = (total * WEIRD_PRIME + value) % this.keyMap.length;
        }
      
      	return total;
    }

}

Set:

키와 밸류를 받는다.
키를 해싱한다.
키와 벨류 페어로 해시테이블의 인덱스에 Separate Chaining방식으로 저장한다.
(중첩 배열 내부에 저장한다는 말.)

Get:

키를 받는다.
키를 해싱한다.
키가 저장되어 있을 인덱스에 접근하고 중첩배열 내부를 탐색한다.
만약 키가 발견되지 않으면 undefined를 출력한다.

202. 해시 테이블 Set메소드 솔루션

키와 벨류를 받으면 아래와 같은 모습으로 데이터를 저장해주어야 한다.
무언가가 없다면 푸시해주고,

[[ , , , , [[key, value]], , , ]]

무언가가 있다면 이미 있던 요소의 뒤에 푸시.

[[ , , , , [[key, value], [key, value]], , , ]]

class HashTable {
 // 상단코드와 동일
 
 set(key, value) {
 	let index = this._hash(key);
   	
   	if (!this.keyMap[index]) { // 사용되고 있지 않은 장소인 경우 빈 배열로 사전설정.
    	this.keyMap[index] = [];
    }
   
   	this.keyMap[index].push([key, value]); // 사용되고 있다면 push
 }

}

202. 해시 테이블 Get메소드 솔루션

class HashTable {
 // 상단코드와 동일
 
 get(key) {
 	let index = this._hash(key);
   	
   	if (this.keyMap[index]) {
      	for (let i = 0; i < this.keyMap[index].length; i++) {
        	if (this.keyMap[index][i][0] === key) { // 첫번째 아이템이 key이므로 [0].
            	return this.keyMap[index][i][1]; // 두번째 아이템이 value이므로 [1].
            }
        }
    }
   
   	return undefined; // key가 있어야할 곳이 비었다면 undefined 반환
 }

}

204. 키와 값이 한 쌍을 이루는 해시 테이블

해시 테이블에 두 메서드를 더 추가해야한다.

values() 모든 벨류를 배열에 모아 반환
keys() 모든 키를 배열에 모아 반환

겹치는 데이터를 어떻게 할 것인가를 고민해야 한다.
예를들어 철수의 성적: C, 영희의 성적: C 이렇게 벨류가 같을 수 있다.
대부분의 경우 values()와 keys() 함수는 유니크한 값 혹은 유니크한 키만으로 배열을 구성해서 반환하도록 작성한다.

205. 해시 테이블의 키와 값 솔루션

values 함수 작성

class HashTable {
 // 상단코드와 동일
 
 values() {
 	let valuesArr = [];
   	
	for (let i = 0; this.keyMap.length; i++) {
      	if (this.keyMap[i]) {
        	for (let j = 0; j < this.keyMap[i].length; j++) {
              	if (!valuesArr.includes(this.keyMap[i][j][1])) { 
                	// 이미 존재한다면 push안함.
                  	valuesArr.push(this.keyMap[i][j][1]);
                }
            }
        }
    }
   
   	return valuesArr;
 }

}

keys 함수 작성

class HashTable {
 // 상단코드와 동일
 
 keys() {
 	let keysArr = [];
   	
	for (let i = 0; this.keyMap.length; i++) {
      	if (this.keyMap[i]) {
        	for (let j = 0; j < this.keyMap[i].length; j++) {
              	if (!valuesArr.includes(this.keyMap[i][j][0])) { 
                	// 이미 존재한다면 push안함. (실제로 겹치는 키는 존재하지 않아야 함..)
                  	valuesArr.push(this.keyMap[i][j][0]);
                }
            }
        }
    }
   
   	return valuesArr;
 }

}

혹여나 중복 키가 있을 경우 무시하도록 작성되어있지만
실제로는 겹치는 키는 존재하지 않아야하며
대부분의 프로그래밍 언어들에서는 삽입하는 키가 중복일경우 overwrite하도록 설계되어있음.

206. 빅오 복잡도

해쉬함수가 성능이 좋아서 분배를 잘 해주는 경우.

(평균적인 케이스)

삽입: O(1)
제거: O(1)
접근: O(1) (키를 찾을 때)
chaining방법으로 충돌을 해결할 시 링크드리스트를 활용하는 경우, Tail에 자료를 저장할 경우, O(α). 해시 테이블에서 연결 리스트의 맨 끝에 데이터를 추가하려면, 연결 리스트를 끝까지 순회해야 하기 때문.
성능이 무척 떨어져서 한 요소에만 삽입하는 경우:

0 1 2 3 4 5 6 7 8 9
[][][][][][][][][][]
↑
↑
↑
↑
↑
↑

모든 것을 한 자리에 넣게 되면 리스트나 다름이 없기 때문에 O(n)

정리

해시 테이블은 key와 value의 쌍이 담긴 컬렉션이다.
해시 테이블은 key를 이용해서 value를 매우 빠르게 찾을 수 있다.
해시 테이블은 key-value를 빠르게 추가할 수 있다.
해시 테이블은 큰 배열에 데이터를 저장하며 key들을 해싱함으로써 작동한다.
좋은 성능의 해시는 1. 빠르며, 2. 키를 고르게 분배하며, 3. 멱등성이 보장되어야한다.
해시 충돌을 해결하기 위해서 1. 개별 체이닝 (Separate chaining), 2. 직선 탐색법 (Lineal probing) 두가지 방법이 있다.

추가

자바스크립트에는 해시테이블 매커니즘을 활용한 자료구조로 객체, Map, Set이 있다.

맵

출처: https://ko.javascript.info/map-set

맵(Map)은 키가 있는 데이터를 저장한다는 점에서 객체와 유사하다. 다만, 맵은 키에 다양한 자료형을 허용한다는 점에서 차이가 있다.

let map = new Map();

map.set('1', 'str1');   // 문자형 키
map.set(1, 'num1');     // 숫자형 키
map.set(true, 'bool1'); // 불린형 키

// 객체는 키를 문자형으로 변환한다는 걸 기억하고 계신가요?
// 맵은 키의 타입을 변환시키지 않고 그대로 유지합니다. 따라서 아래의 코드는 출력되는 값이 다릅니다.
alert( map.get(1)   ); // 'num1'
alert( map.get('1') ); // 'str1'

alert( map.size ); // 3

셋

셋(Set)은 중복을 허용하지 않는 값을 모아놓은 특별한 컬렉션이다. 셋에 키가 없는 값이 저장된다.

let set = new Set();

let john = { name: "John" };
let pete = { name: "Pete" };
let mary = { name: "Mary" };

// 어떤 고객(john, mary)은 여러 번 방문할 수 있습니다.
set.add(john);
set.add(pete);
set.add(mary);
set.add(john);
set.add(mary);

// 셋에는 유일무이한 값만 저장됩니다.
alert( set.size ); // 3

for (let user of set) {
  alert(user.name); // // John, Pete, Mary 순으로 출력됩니다.
}

객체와 맵의 주요 차이

키 타입:

객체: 객체의 키는 문자열 또는 기호(symbol)
맵: 맵은 어떤 데이터 타입도 키로 사용할 수 있다.

객체: 순서가 존재하지 않음.
맵: 맵은 키-값 쌍을 입력된 순서대로 유지하므로 순서가 보장됌.

객체: 객체의 크기(속성의 개수)를 얻기 위한 내장 메서드나 속성이 없다. 직접 속성을 순회하며 개수를 세어야 한다.
맵: size를 통해 바로 값을 얻을 수 있음.

객체: for...in 루프, Object.keys(), Object.values() 등의 메서드를 사용한다.
맵: 맵은 forEach(), for...of 루프를 사용.

객체: Object.keys()나 for...in 루프에서 나타나지 않도록 속성을 열거 가능하지 않게 설정할 수 있음.
맵: 맵의 모든 키는 열거가능.

// 열거 가능하지 않은 속성 설정
Object.defineProperty(myObject, 'age', {
  value: 30,
  enumerable: false,
});

//접근은 가능. 열거가 안될 뿐.

유키미아우

능동적인 마음

이전 포스트

병합정렬

다음 포스트