들어가며
연결 리스트를 시작으로 자료구조를 본격적으로 공부하려 합니다. 자료구조를 제대로 공부해야만 훗날 근무를 할 때, 더 좋은 코드를 작성할 수 있다고 믿습니다. 그렇다면 자료구조에 대해 깊은 이해가 있는 개발자가 되기 위해 차근차근 공부해보겠습니다.
해시 테이블은 왜 배워야 할까?
유저가 회원가입을 한다고 생각해봅시다. 만약 유저의 아이디와 비밀번호를 DB에 저장하게 될 텐데, 그렇다면 입력받은 데이터를 내부 DB에 그대로 저장해야 할까요? 물론 데이터를 저장해야 합니다. 하지만 입력값 그대로를 저장한다면, 내부 DB가 해커에 의해 뚫리게 되는 순간 개인정보 유출로 인한 피해를 입을 수 있습니다. 그래서 개발자는 비밀번호를 저장할 때, 비밀번호를 암호화해서 저장합니다. 이때 해시 함수를 활용해서 비밀번호를 임의의 값으로 변환합니다. 그렇다면 해시는 무엇이며, 해시 함수는 무엇인지 알아보겠습니다.
해시란 단방향 암호화 기법으로 해시함수를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미합니다. 그리고 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때 매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시값, 매핑하는 과정을 해싱이라고 합니다.
SHA256 Hash Generator Online
This online tool allows you to generate the SHA256 hash of any string. SHA256 is designed by NSA, it's more reliable than SHA1. Enter your text below:
passwordsgenerator.net
위의 주소에 들어가면, hash값을 만들어주는 사이트에 접속할 수 있는데, 바뀔 때마다 hash값이 바뀌는 것을 볼 수 있습니다. 해시 알고리즘은 종류가 다양하고 알고리즘마다 hash 길이가 다릅니다. 해시 알고리즘은 모두에게 공개되어있습니다. 즉, 해커에게도 공개되어있다는 말이기도 합니다. 그래서 이미 보안이 뚫린 해시 함수가 존재하는데, MD5, SHA-1, HAS-180은 사용해선 안됩니다. SHA-256, SHA-512 등을 사용하기를 권고하고 있습니다.
해시 알고리즘은 특정 입력에 대해 항상 같은 해시 값을 리턴하기 때문에 이를 이용해 인증이 가능합니다. 어떤 입력인지 몰라도 해시함수를 이용해서 해시된 값이 일치하면 입력이 같다는 것이 인증되는 것입니다.
입력은 만들어낼 수 있는 값의 길이 제한이 없어 무한정으로 만들 수 있지만 해시값은 항상 고정된 길이의 값으로 나타나기 때문에 한계가 있습니다. 그래서 다른 입력이지만 같은 해시값이 나오는 경우가 있을 수 있습니다. (중복이 적게 나타날수록 좋은 해시함수입니다.)
단순히 해시 함수를 이용해서 변환한다고 해서 완벽하지 않습니다. 해커가 무차별적으로 임의의 값을 입력하면서 입력된 값을 알아낼 수 있습니다. 이 점을 보완하기 위해 비밀번호에 솔트(salt)라는 특정 값을 넣는 방법이 있고, 해시 함수를 여러 번 번 돌리는 방법이 있습니다. 두 가지 방법을 합하여 입력값에 salt값을 붙여서 여러 번 반복 해싱할 수도 있습니다.
Node.js에 crypto라는 내장 모듈이 있는데, crpyto 모듈의 pbkdf2 메서드 사용 예시를 소개하겠습니다. pbkdf2는 단방향 암호화에서 많이 사용하는데, pbkdf2 메서드는 입력값(secret), salt, 해시 함수 반복 횟수, 바이트 길이, 해시 알고리즘 이렇게 5개의 인자를 받습니다.
const crypto = require('crypto');
crypto.pbkdf2('secret', 'salt', 100000, 64, 'sha512', (err,
derivedKey) => {
if (err) {
throw err;
}
console.log(derivedKey.toString('hex')); // '3745e48...08d59ae'
});
위 예시에서 해싱에 성공하면 Buffer 형태로 callback으로 넘겨주기 때문에 derivedKey.toString('hex') 이렇게 hex 방식으로 문자열로 만들어 주어야 합니다. (base64도 많이 사용합니다. base64, hex는 인코딩 방식입니다.)
해시 함수는 암호화를 위한 게 아닌 검색을 위해 만들어졌기 때문에 매우 빨라서 10만 번을 반복해도 1초도 걸리지 않습니다. 1초가 걸릴 때까지 반복 횟수를 늘리는 것도 좋은 방법 중에 하나입니다. 이렇게 간단하게 비밀번호를 해시 함수를 통해 해싱하는 방법에 대해 알아봤습니다. 그럼 해시와 해시 함수에 대해 익혔다면 본격적으로 해시 테이블이란 무엇인지에 대해 알아보겠습니다.
해시 테이블이 그래서 뭐야?
해시 테이블은 해시 함수를 활용해서 키 값에 인덱스를 배정하고, 인덱스의 값에 데이터를 넣는 자료 구조를 말합니다. 그리고 해시란, 키와 값이 한 쌍으로 구성된 데이터를 말합니다. 아직은 감이 안 잡히실 분들도 있으리라 생각이 듭니다. 그렇다면, 해시 테이블이라는 개념은 어디서부터 출발한 것인지 살펴보겠습니다.
직접 주소 테이블(Direct Address Table)
해시 테이블의 아이디어는 직접 주소 테이블이라는 자료구조에서 출발합니다. 직접 주소 테이블은 입력받은 value가 곧 key가 되는 데이터 매핑 방식입니다. 아래의 코드로 직접 주소 테이블을 이해해봅시다.
class DirectAddressTable {
constructor () {
this.table = [];
}
setValue (value = -1) {
this.table[value] = value;
}
getValue (value = -1) {
return this.table[value];
}
getTable () {
return this.table;
}
}
const myTable = new DirectAddressTable();
myTable.setValue(7);
myTable.setValue(20);
myTable.setValue(50);
console.log(myTable.getTable());출처 : JavaScript와 함께 해시 테이블을 파헤쳐보자
만약 이 코드를 복사 붙여 넣기 한 후 브라우저 콘솔이나 Node.JS로 실행해본다면, 콘솔에 아래와 같은 테이블이 출력될 것입니다.
예를 들어 우리가 7을 테이블에 넣으면 이 값은 배열의 7번 인덱스의 요소가 되고 50을 넣으면 50번 인덱스의 요소가 됩니다. 직접 주소 테이블을 사용할 때는 들어오는 값을 알면 저장된 인덱스도 함께 알 수 있습니다. 즉 시간 복잡도는 다. 또한 테이블에 있는 값을 삽입, 수정, 삭제할 때도 값이 어디 있는지 알고 있기 때문에 O(1)의 시간 복잡도로 해결할 수 있습니다.
하지만 직접 주소 테이블도 당연히 단점이 있습니다. 바로 공간의 효율성이 좋지 못하다는 것입니다.
위의 예처럼, 저장된 데이터를 제외하고 0으로 채워진 나머지 공간은 값은 없지만 메모리 공간은 할당되어 있는 상태입니다. 만약 1000과 같이 큰 값이 하나만 테이블에 더 들어온다면, 테이블의 크기는 1001이 되면서 적재율은 훨씬 떨어지게 됩니다. 즉, 저장해야 할 값의 범위가 크지 않은 데이터를 저장할 때 직접 주소 테이블을 사용하면 좋을 것 같습니다. 하지만 저장해야 할 값의 범위가 크다면, 직접 주소 테이블은 큰 비효율성을 보일 수 있습니다. 그렇다면, 비효율의 문제를 어떻게 해결할 수 있을까요?
직접 주소 테이블의 단점을 해시 함수로 보완하자!
직접 주소 테이블의 공간 효율이 좋지 않다는 단점을 보완한 게 바로 해시 테이블입니다. 해시 테이블은 직접 주소 테이블과 같이 값을 바로 테이블의 인덱스로 사용하는 것이 아니라 해시 함수라는 것에 한번 통과시켜 사용합니다. 해시 함수란, 입력받은 데이터가 인덱스를 받을 수 있도록, 매핑하는 함수입니다. 이때 함수가 뱉어내는 결과물을 해시라고 부릅니다. 그럼 이해를 돕기 위해 아래에 간단한 해시 함수를 만들어보겠습니다.
function hashFunction (key) {
return key % 10;
}
console.log(hashFunction(102948)); // 8
console.log(hashFunction(19191919191)); // 1출처 : JavaScript와 함께 해시 테이블을 파헤쳐보자
위의 해시 함수는 들어오는 key값을 10으로 나눈 후의 나머지를 반환합니다. 하지만 어떤 값이 들어오든 그 값의 1의 자리만 반환합니다. 그렇기 때문에 반환되는 값은 무조건 0~9 사이의 값이 나옵니다.
위의 직접 주소 테이블에서는 1000이라는 값이 하나만 들어와도 1000번 인덱스에 값을 저장하기 위해 1000의 크기를 가진 테이블을 생성해야 했고, 999개의 버리는 공간이 발생했습니다. 하지만 해시 함수를 활용하면 1001이 들어오면 1을 반환하기 때문에, 고정된 테이블의 길이를 정해둘 수 있고, 그 안에만 데이터를 저장할 수 있습니다. 이로써 '직접 주소 테이블'의 단점이었던 낭비되는 공간을 줄일 수 있습니다.
해시의 충돌(Collision)
해시 테이블은 충돌 문제가 발생할 수 있습니다. 예를 들어 위의 그림에서 보면, John Smith와 Sam Doe는 해쉬 함수를 통해 152라는 인덱스를 배정받았습니다. 만약 같은 인덱스를 배정받는다면, 이 데이터를 어떻게 처리해줘야 할까요? 이런 문제를 충돌이라고 이야기합니다.
이런 충돌이 발생한다면, 이 문제를 어떻게 해결할 수 있을까요?
개방 주소법 (Open Address)
개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Probe) 한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식입니다. 해시 함수를 거쳐서 나온 인덱스에 데이터가 이미 있으니, 다른 인덱스에 데이터를 저장한다는 의미로 개방 주소(Open Address)라고 합니다. 개방 주소법은 어떤 방식으로 비어있는 공간을 탐사할 것이냐에 따라 나누어집니다. 개방 주소법으로 공간을 탐사하는 방법에 대해 소개하겠습니다.
1. 선형 탐사법(Linear Probing)
먼저 선형 탐사법에 대해 소개합니다. 선형 탐사법은 선형으로 순차적으로 탐사하는 방법입니다. 아래에 1001과 11의 상황을 통해 충돌 상황을 만들어보겠습니다.
function hashFunction (key) {
return key % 10;
}
console.log(hashFunction(1001)); // 1
console.log(hashFunction(11)); // 1
처음 콘솔 값을 확인해보면, 해시의 인덱스로 1이 나올 것입니다. 그 이후 11을 해시 함수에 통과시켰더니 또 1이 나왔습니다. 하지만 이미 1번 인덱스에는 1001가 있기 때문에 11은 해시 테이블에 들어갈 자리가 없게 됩니다. 이럴 경우에 충돌이 발생합니다. 선형 탐사법은 이렇게 충돌이 났을 때 정해진 칸만큼의 옆 방을 주는 방법입니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1001 | 11 |
만약 해시 함수에 key값을 넣었을 때, 또 1이 나온다면, 충돌이 발생하게 되고, 그렇다면 이번에는 값을 3번 인덱스에 저장할 것입니다. 이런 방식으로 빈 공간이 나타날 때까지 순차적으로 탐사를 진행합니다.
선형 탐사법의 단점은 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화(Primary Clustering) 문제에 취약하다는 것입니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1001 | 11 | 21 | 31 |
같은 해시가 여러 번 나오는 상황이라면, 선형 탐사법을 사용하면 데이터가 연속되게 저장될 가능성이 높아집니다. 이런 경우 해시의 값이 1이 나왔을 때뿐만 아니라 2나 3이 나왔을 때도 충돌이 발생합니다. 이미 해시 값으로 2, 3에 해당하는 곳에 데이터가 저장되어있기 때문에, 계속해서 해시 값으로 1이 나왔고, 새롭게 2, 3이 나오더라도, 저장하려고 하는 공간에 데이터가 있기 때문에 충돌이 나게 됩니다.
이런 식으로 충돌이 계속될수록 데이터가 연속되게 저장되기 때문에 데이터 덩어리가 더 커집니다. 이것이 바로 Primary Clustering입니다. 그렇다면 이 문제를 어떻게 해결할 수 있을지 다른 방법을 알아보겠습니다.
2. 제곱 탐사법(Quadratic Probing)
제곱 탐사법은 탐사하는 폭이 고정폭이 아닌 제곱으로 늘어나는 부분에서 선형 탐사법과 차이점을 가집니다.
첫 번째 충돌이 발생했을 때는 충돌 난 지점으로부터 1의 제곱만큼, 두 번째 충돌이 발생했을 때는 2의 제곱만큼, 세 번째는 3의 제곱만큼 탐사하는 스텝이 빠르게 커집니다. 선형 탐사법 때와 동일한 상황에서 제곱 탐사법을 사용하면 해시 테이블은 아래와 같은 모양이 됩니다.
| 첫 번째 | ||||||||
충돌이 났을 때 11은 충돌 난 1번 인덱스로부터 1의 제곱 = 1만큼의 옆 방으로 들어갑니다.
두 번째 충돌이 났을 때 21은 충돌이 난 1번 인덱스로부터 2의 제곱 = 4만큼의 옆 방으로 들어갑니다.
세 번째 충돌이 났을 때 31은 충돌이 난 1번 인덱스로부터 3의 제곱 = 9만큼의 옆 방으로 들어갑니다.
이렇게 제곱 탐사법을 사용하면 충돌이 발생하더라도 데이터의 밀집도가 선형 탐사법보다 많이 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 많이 줄어듭니다.
그래도 결국 해시로 1이 여러 번 나오면 계속 충돌이 나는 것은 피할 수 없습니다. 결국 데이터의 군집은 피할 수 없는 숙명이므로 이 현상을 이차 군집화(Secondary Clustering)이라고 부릅니다.
여기서 더 개선할 수 있는 방법에 대해 고민해보겠습니다.
3. 이중 해싱(Double Hashing)
이중 해싱은 해시 함수를 이중으로 사용하는 것을 뜻합니다.
하나는 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용합니다. 이렇게 하면, 최초 해시로 같은 값이 나오더라도 다른 해시 함수를 거치면서 다른 탐사 이동폭을 제공하기 때문에 다른 공간에 값이 골고루 저장될 확률도 높아집니다.
const myTableSize = 23; // 테이블 사이즈가 소수여야 효과가 좋다
const myHashTable = [];
const getSaveHash = value => value % myTableSize;
// 스텝 해시에 사용되는 수는 테이블 사이즈보다 약간 작은 소수를 사용한다.
const getStepHash = value => 17 - (value % 17);
const setValue = value => {
let index = getSaveHash(value);
let targetValue = myHashTable[index];
while (true) {
if (!targetValue) {
myHashTable[index] = value;
console.log(`${index}번 인덱스에 ${value} 저장! `);
return;
}
else if (myHashTable.length >= myTableSize) {
console.log('풀방입니다');
return;
}
else {
console.log(`${index}번 인덱스에 ${value} 저장하려다 충돌 발생!ㅜㅜ`);
index += getStepHash(value);
index = index > myTableSize ? index - myTableSize : index;
targetValue = myHashTable[index];
}
}
}출처 : JavaScript와 함께 해시 테이블을 파헤쳐보자
이때 테이블 사이즈와 두 번째 해시함수에 사용될 수는 둘 다 소수를 사용하는 것이 좋습니다. 둘 중에 하나가 소수가 아니라면 결국 언젠가 같은 해싱이 반복되기 때문입니다. setValue 함수를 차례로 뜯어보겠습니다.
1. 저장할 인덱스를 getSaveHash 해시 함수로 얻습니다.
2. myHashTable에 index를 키로 받는 값을 targetValue 변수에 저장합니다.
3. 반복문을 시작합니다.
4. 만약 targetValue가 없으면, 배열에 값이 비었다는 뜻이므로, 인덱스에 맞는 키값을 저장합니다.
5. 만약 배열의 길이가 myTableSize의 길이보다 크거나 같다면 배열이 모두 꽉 찼다는 뜻입니다.
6. 만약 인덱스에 맞는 키값이 있고, 배열이 가득 차 있지도 않다면 인덱스에 맞는 키값을 저장하려다가 충돌이 발생합니다.
그렇다면 다음 인덱스를 받아서, 그 인덱스에 맞는 값으로 키값을 저장합니다.
console.log(setValue(1001));
console.log(setValue(11));
console.log(setValue(21));
console.log(setValue(31));
// 12번 인덱스에 1001 저장!
// 11번 인덱스에 11 저장!
// 21번 인덱스에 21 저장!
// 8번 인덱스에 31 저장!
위의 선형 탐사법과 제곱 탐사법을 사용했다면 모두 해시의 결과가 1이어서 연쇄적으로 충돌이 발생해야 할 값들입니다. 하지만 이중 해싱을 사용하면 한 번의 충돌만으로 모든 값을 저장할 수 있습니다. 지금까지 해시의 충돌을 대비하기 위한 방법으로 개방 주소법을 알아봤습니다. 그렇다면, 충돌을 대처하기 위한 다른 방법인 분리 연결법에 대해서도 알아보겠습니다.
분리 연결법 (Separate Chaining)
분리 연결법은 해시 테이블의 버킷에 하나의 값이 아니라 링크드 리스트(Linked List)나 트리(Tree)를 사용합니다. 링크드 리스트를 바탕으로 분리 연결법을 알아보겠습니다.
테이블 크기가 5일 때 해시로 1을 반환하는 1001, 11, 21, 31을 저장할 때 분리 연결법을 사용하면 이렇게 됩니다.
| 0 | 1 | 2 | 3 | 4 |
| [31, 21, 11, 1001] |
표를 자세히 보면, [1001, 11, 21, 31]의 순서가 아니라 [31, 21, 11, 1001]의 순서로 뒤집혀 있습니다. 이는 데이터를 삽입할 때 조금이라도 수행 시간을 줄이기 위해 사용하는 방법입니다.
왜 그런지 설명하기 위해 우리 테이블의 1번 인덱스에 저장된 링크드 리스트가 [1001, 11, 21, 31]의 순서일 때를 살펴봅시다.
| 1 | 2 | 3 | 4 |
| {값: 1001, 다음 노드: 2} |
{값: 11, 다음 노드: 3} |
{값: 21, 다음 노드: 4} |
{값: 31, 다음 노드: null} |
만약 이번에 추가할 값이 41이라고 해본다면, 일단 메모리 주소가 99인 곳이 남길래 여기에 {값: 41, 다음 노드: null}을 저장했습니다. 그 후 이 새로운 노드를 리스트에 붙여야 하니까 해당 리스트의 마지막 노드인 메모리 4에 저장된 노드까지 찾아가야 합니다.
그다음에 메모리 4에 저장된 값을 {값: 31, 다음 노드: 99}로 바꿔주면 끝입니다.
| 1 | 2 | 3 | 4 | 99 |
| {값: 1001, 다음 노드: 2} |
{값: 11, 다음 노드: 3} |
{값: 21, 다음 노드: 4} |
{값: 31, 다음노드: 99} |
{값: 41, 다음 노드: null} |
문제는 새 노드를 리스트에 붙이기 위해서 메모리 4에 저장된 노드를 찾는 과정입니다. 먼저 리스트의 머리인 메모리 1부터 찾은 다음에 다음 메모리 주소 값을 확인하고, 2로 이동해서 또 다음 메모리 주소를 확인하고.. 이게 지금 4번이니까 할만하지, 리스트의 길이가 길어질수록 수행 시간도 비례해서 늘어나기 때문에 좋지 못합니다. 하지만 순서를 반대로 뒤집으면 데이터 삽입이 한결 쉬워집니다.
| 99 | 1 | 2 | 3 | 4 |
| {값: 41, 다음 노드: 1} |
{값: 1001, 다음 노드: 2} |
{값: 11, 다음 노드: 3} |
{값: 21, 다음 노드: 4} |
{값: 31, 다음노드: null} |
맨 앞에 노드를 추가하는 것이기 때문에 다른 노드를 탐색할 필요 없이 그냥 메모리에 밀어 넣고 { 값: 11, 다음 노드: 1 }이라고 저장해주면 되기 때문입니다. 그래서 해시 테이블에 저장할 때도 리스트의 꼬리에 데이터를 붙이기보다는 머리에 붙이는 방법을 보통 많이 사용합니다.
대신 이렇게 분리 연결법을 사용하려면 해시 함수의 역할이 굉장히 중요합니다. 결국 균일하지 못한 해시를 사용해서 특정 인덱스에 데이터가 몰리게 된다면, 다른 곳은 텅텅 비어있는데 한 버킷에 저장된 리스트의 길이만 계속 길어지기 때문입니다.
결국 내가 찾고자 하는 값이 리스트의 맨 마지막에 위치하고 있다면, 링크드 리스트를 처음부터 끝까지 다 탐색해야 하기 때문에 O(n)의 시간 복잡도를 가지게 됩니다. 그렇기 때문에 최대한 저장하고자 하는 데이터를 균일하게 퍼트려서 리스트의 길이를 어느 정도로 유지해주는 해시 함수의 역할이 중요합니다.
사례로 보는 충돌 해결법
간단한 사례들을 바탕으로 복습을 해보겠습니다.
개방 주소법을 활용해서 데이터를 저장한다면, 위와 같은 그림이 될 것입니다. 윤아와 서현은 해시함수를 거치면서, 같은 인덱스 값을 받아서 충돌이 일어난 상황입니다. 윤아를 인덱스 2의 값에 저장했다면, 서현은 2의 인덱스에 값을 저장하지 못하기 때문에, 빈 공간을 찾아서 빈 공간에 값을 저장했습니다. 이를 통해 충돌을 해결할 수 있었습니다. 하지만 군집화의 문제가 발생할 수 있다는 것이 단점일 수 있다는 것이 바로 개방 주소법에 대한 설명이었습니다.
분리 연결법을 활용해서 데이터를 저장한다면, 위와 같은 그림이 될 것입니다. 위의 상황과 같이, 윤아와 서현은 해시함수를 거치면서, 같은 인덱스 값을 받아서 충돌이 일어난 상황입니다. 윤아를 인덱스 2의 값에 저장했다면, 개방 주소법 같은 경우에는 빈 공간에 데이터를 저장했겠지만, 분리 연결법은 링크드 리스트를 활용하여 같은 인덱스에 값을 저장하면서, 테이블을 형성하고 있습니다. 사례에서는 서현을 꼬리 쪽에 저장하고 있지만, 조금 더 효율적으로 데이터를 쌓으려면 머리 쪽에 쌓으면 된다는 부분까지 우리는 방금까지의 공부를 통해 알아갈 수 있었습니다.
테이블 크기 재할당 (Resizing)
해시 테이블은 고정적인 공간을 할당해서 많은 데이터를 담기 위한 자료구조인 만큼 언젠가는 데이터가 넘치기 마련입니다. 만약 개방 주소법을 사용하는 경우에는 테이블이 실제로 꽉 차서 더 이상 저장을 못하는 상황이 발생할 수 있습니다. 그리고 분리 연결법을 사용하는 경우에는 충돌이 발생할수록 각각의 버킷에 저장된 리스트가 점점 더 길어져서 리스트를 탐색하는 리소스가 너무 늘어난 상황이 발생할 것입니다.
그렇기 때문에 해시 테이블은 어느 정도 비워져 있는 것이 성능상 더 좋을 수 있습니다. 그렇기 때문에 해시 테이블을 운용할 때는 어느 정도 데이터가 차면 테이블의 크기를 늘려줘야 합니다.
이건 특별한 알고리즘이라기보다는 그냥 기존 크기의 두 배정도로 새로운 테이블을 선언해서 기존 테이블의 데이터를 그대로 옮겨 담는 방법을 사용합니다. 분리 연결법을 사용한 해시 테이블의 경우 재 해싱을 통해 너무 길어진 리스트의 길이를 나누어서 다시 저장하는 방법을 사용하기도 합니다.
그렇다면, 언제 테이블의 크기를 늘려줘야 할까요? 이는 사용률이 대개의 경우 사용률이 0.7 이상으로 커지면 해시 테이블을 리사이징 하는데 대략 2배 정도의 크기로 배열을 만든다고 합니다. 그렇다면 사용률은 어떻게 계산할 수 있을까요?
위의 공식과 같이 사용률을 구할 수 있습니다. 만약 테이블에 5개의 버킷이 있을 때, 그중 2개의 버킷에 데이터가 저장되어 있다면 2/5 = 0.4의 사용률이 됩니다. 만약 저장할 데이터가 100개라면, 개방 주소법을 활용해서 생각해본다면, 해시 테이블에는 최소 100개의 공간이 있어야 합니다. 만약 100개의 데이터에 100개의 버킷이 있다면 해시 테이블의 사용률은 1이 됩니다. 즉 이런 식으로 계산해서 사용률이 0.7 이상이 된다면, 해시 테이블을 리사이징 해주는 것입니다.
리사이징을 해서 배열을 크게 만들고 나면 해시 함수를 사용해서 기존 테이블에 있던 데이터를 새로운 해시 테이블에 다시 저장해야 합니다. 이 과정은 시간이 매우 오래 걸리기 때문에 리사이징을 자주 하는 것은 좋지 않다고 합니다.
그렇다면, 해시 테이블을 JS에서는 어떻게 활용하는지 알아보겠습니다.
JavaScript에서의 해시 테이블
JS에서는 해시 테이블을 어떻게 구현하고, 어떻게 활용할 수 있는지 알아보겠습니다.
hashmap
HashMap Class for JavaScript
www.npmjs.com
프로젝트 내에서 hashmap을 활용할 수 있습니다. npm을 통해 hashmap을 설치해서 활용한다면 더 쉽게 프로젝트에 활용할 수 있습니다. 설치하는 방법은 아래와 같습니다.
$ npm install hashmap
해시 맵을 활용 해서, 다양한 배열 요소를 만들 수 있습니다. 이중 배열도 가능하며, 여러 키와 값을 가진 배열도 만들 수 있습니다.
new HashMap() // 빈 해시 맵을 만듭니다.
new HashMap(map:HashMap) // 키 - 값을 가진 해시 맵을 만듭니다.
new HashMap(arr:Array) // 키값 배열에서 해시 맵을 생성 합니다. 예를 들어 [['key1', 'val1'], ['key2', 'val2']] 이런 식으로 해시 맵을 생성 합니다.
new HashMap(key: *, value: *, key2: *, value2: *,... ) // 여러 키 -값을 가진 해시 맵을 만듭니다.
그렇다면, hashmap의 메서드는 무엇이 있는지 알아보겠습니다.
get(key: *) : * // 해당 키에 대해 저장된 값을 반환합니다.
set(key:*, value:*) : // 키 - 값을 저장합니다.
multi(key:*, value:*, key2:*, value2:*,...) : 여러 개의 키와 값을 저장합니다.
copy(other:HashMap) : 키와 값을 복사합니다.
has(key:*) : 해시 맵에 키가 설정되어 있는지 여부를 반환합니다.
search(value:*) : 주어진 값이 저장된 키를 반환합니다.
delete(key:*) : 키 - 값을 삭제합니다.
type(key:*) : 제공된 키의 데이터 유형을 반환합니다.
keys() : 등록된 모든 키가 있는 배열을 반환합니다.
values() : 모든 값을 가진 배열을 반환합니다.
entries() : key, value 쌍을 가진 배열을 반환합니다.
size : 키와 값의 양을 반환합니다.
count() : 키와 값의 양을 반환합니다.
clear() : 해시 맵의 모든 키와 값을 삭제합니다.
clone() : 원본의 모든 키 값을 활용해서 새 해시 맵을 만듭니다.
forEach(function(value, key)) : 키와 값을 반복하고, 각각에 대해 함수를 호출합니다.
hashmap의 메서드를 어떻게 활용하는지 알아보겠습니다. 먼저 hashmap의 set과 get 메서드에 대한 활용법입니다.
const HashMap = require('hashmap');
let map = new HashMap();
map.set("some_key", "some_value");
map.get("some_key"); // "some_value" 값이 나온다.
hashmap의 set으로 데이터를 넣고, size를 통해 테이블의 크기에 대해 알아보는 메서드 활용법입니다.
const HashMap = require('hashmap');
let map = new HashMap();
map.set("key1", "val1");
map.set("key2", "val2");
map.size; // -> 2가 나온다.
다음은 hashmap을 삭제하는 메서드 활용법입니다.
const HashMap = require('hashmap');
let map = new HashMap();
map.set("some_key", "some value");
map.delete("some_key");
map.get("some_key"); // -> undefined
다음은 객체를 키로 사용하는 메서드 활용법입니다.
const HashMap = require('hashmap');
let map = new HashMap();
let key = {};
let key2 = {};
map.set(key, 123);
map.set(key2, 321);
map.get(key); // --> 123
다음은 해시 맵을 활용 해서 반복하는 메서드 활용법입니다.
map.set(1, "test 1");
map.set(2, "test 2");
map.set(3, "test 3");
map.forEach(function(value, key) {
console.log(key + " : " + value);
});
다음은 메서드를 연결하는 방법입니다.
map
.set(1, "test 1")
.set(2, "test 2")
.set(3, "test 3")
.forEach(function(value, key) {
console.log(key + " : " + value);
});
이렇게 자바스크립트에서 hashmap을 활용하는 방법에 대해 알아봤습니다. 그렇다면 해시 맵 개념을 활용해서 알고리즘 문제를 어떻게 하면 잘 풀 수 있는지 같이 알아보겠습니다.
알고리즘에서의 해시 테이블
JS에서는 해시 테이블을 어떻게 구현하고, 어떻게 활용할 수 있는지 해시 관련 문제를 풀어보면서, 공부하면 더 좋을 것 같습니다. 공부한 내용을 적용한 부분은 따로 정리해서 올릴 예정입니다.
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
해시 테이블의 장단점
해시 테이블의 경우 중복 데이터를 찾아내기 쉽다는 장점이 있습니다. 또한 빠르게 데이터를 탐색하고, 삽입하고, 삭제할 수 있다는 장점이 있습니다. 하지만 단점도 물론 존재합니다. 해시 테이블의 가장 큰 단점은 공간 효율성이 낮다는 것입니다. 물론 직접 주소 테이블보다는 훨씬 공간 효율성이 좋다고 말할 수는 있지만, 해시 테이블도 미리 빈 공간을 만들어서 데이터를 넣는 방식이기 때문에 만들어둔 공간에 데이터가 들어가지 않는다면, 이 또한 공간 효율성이 좋지 못한 사례가 될 수 있습니다.
또한 해시 테이블은 정렬된 데이터를 다루기 적절하지 않은 구조여서, 해시 함수에 대한 의존도가 매우 높다는 것도 단점 중 하나로 볼 수 있습니다. 만약 해시 함수의 성능이 좋지 못하거나, 함수가 원하는 대로 작동하지 않는다면, 해시 테이블의 성능과 효율도 매우 나빠질 것이기 때문입니다.
해시 테이블의 Big-O (시간 복잡도)
해시 테이블을 활용해서 자료를 삽입하고 삭제하고 검색한다면 시간 복잡도는 어떻게 될까요? 이는 충돌이 발생한 경우와 발생하지 않은 경우 두 가지 경우를 두고 생각해보겠습니다.
충돌이 발생하지 않은 경우
| Insertion | O(1) |
| Deletion | O(1) |
| Search | O(1) |
충돌이 발생한 경우
| Insertion | O(N) |
| Deletion | O(N) |
| Search | O(N) |
검색 단계의 시간 복잡도는 O(1)입니다. 키는 고유하고 해시 함수의 결과로 나온 해시에 매칭 되는 값을 찾으면 되기 때문입니다. 이때 해시함수의 시간 복잡도는 함께 고려하지 않습니다. 하지만 최악의 경우 O(n)이 될 수 있습니다. 해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문입니다.
저장 단계의 시간 복잡도는 O(1)입니다. 키는 고유하며 해시함수의 결과로 나온 해시와 값을 저장소에 넣으면 되기 때문입니다. 이때 해시함수의 시간 복잡도는 함께 고려하지 않습니다. 하지만 최악의 경우 O(n)이 될 수 있습니다. 해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문입니다.
삭제 단계의 시간 복잡도는 O(1)입니다. 저장되어 있는 값을 삭제할 때는 저장소에서 해당 key와 매칭 되는 값(value)을 찾아서 삭제하면 됩니다. 이때 해시함수의 시간 복잡도는 함께 고려하지 않습니다. 하지만 최악의 경우 O(n)이 될 수 있습니다. 해시 충돌로 인해 모든 bucket의 value들을 찾아봐야 하는 경우도 있기 때문입니다.
충돌을 방지하는 방법들은 데이터의 규칙성(클러스터링)을 방지하기 위한 방식이지만 공간을 많이 사용한다는 치명적인 단점이 있습니다. 만약 테이블이 꽉 차있는 경우라면 테이블을 확장해줘야 하는데, 이는 매우 심각한 성능의 저하를 불러오기 때문에 가급적이면 확정을 하지 않도록 테이블을 설계해줘야 합니다. 또한 해시 테이블에서 자주 사용하게 되는 데이터를 Cache에 적용하면 효율을 높일 수 있습니다. 자주 hit 하게 되는 데이터를 캐시에서 바로 찾음으로써 해시 테이블의 성능을 향상할 수 있습니다.
마치며
자료구조를 처음 공부합니다. 공부하는데 많은 시간이 걸렸습니다. 이해가 안 되는 것들이 많아서 더 그랬던 것 같습니다.
하지만 제대로 공부하는 과정이라고 생각합니다. 저는 어렵게 공부하면 공부한 내용을 잊지 않는다고 믿고 있습니다. 느리더라도, 포기하지 않고 꾸준히 앞으로 나아가겠습니다. 지켜봐 주세요. 감사합니다.
참고
JavaScript와 함께 해시테이블을 파헤쳐보자
이번 포스팅에서는 많이 사용되는 자료구조 중 하나인 에 대해서 정리하려고 한다. 먼저 이 무엇인지, 왜 사용하는지 알아보자!
evan-moon.github.io
[자료 구조] Data Structure - (2) Hash Table
오늘은 자료 구조 중에서 매우 중요한 것들 중 하나인 Hash Table(해시테이블) 자료 구조에 대해서 정리해보려고 한다. 만약에 다음과 같은 친구들의 이름과 전화번호 리스트가 있다고 해보자. 1 Ali
im-developer.tistory.com
hashmap
HashMap Class for JavaScript
www.npmjs.com
(Crypto) 해시(hash)란?
해시(hash)란 단방향 암호화 기법으로 해시함수(해시 알고리즘)를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미합니다.
medium.com
[자료구조] 해시테이블(HashTable)이란?
1. 해시테이블(HashTable)이란? [ HashTable(해시테이블)이란? ] 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른
mangkyu.tistory.com
Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해
0_HJVxQPQ-eW0Exx7M.jpeg DATA들이 사용하기 쉽게 정리되어 있다. 자료구조는 도대체 무엇일까? 자료구조(Data-Structure)는 데이터들의 모임, 관계, 함수, 명령 등의 집합을 의미한다. 더 쉽게 표현하자면, 1)
velog.io
'자료구조' 카테고리의 다른 글
| [자료구조] 스택 with JavaScript (0) | 2021.11.07 |
|---|---|
| [자료구조] 연결리스트 with JavaScript (2) | 2021.09.25 |
| [자료구조] 시간복잡도 with JavaScript (1) | 2021.09.02 |
