(https://commons.wikimedia.org/wiki/File:Hash_browns_at_KFC_in_Yogyakarta,_Indonesia.jpg)
해시 테이블이라고 말하면 무엇을 가장 먼저 떠올렸을까요? 저는... 감자로 만든 탁자를 제일 먼저 떠올렸습니다. 네, 그렇습니다. 아무것도 아닙니다. 그럼에도 불구하고 이 글을 본 님들은 감자 탁자를 제일 먼저 떠올릴 것입니다.......
해시 테이블을 설명하기에 앞서 목차를 나열하겠읍니다.
hash table이란?
hash table의 특징?
hash 함수가 뭐예요?????
해시 충돌이 뭐예요?
hash table의 장단점?
hash table의 구조?
hash table method
수도 코드
JS 코드
엔지니어 대한민국 님의 설명을 듣고 서술하는 부분도 있습니다! 정말 좋아요 명강의예요
* 중후반엔 자바로 코드를 구현합니다.
Hash table이란 뭘까요?
요즘(이라고 하기엔 연구된 지 너무 오래지만) 핫한 자료 구조입니다. 한번 익히면 에브리웨어에서 사용한다는 구조인데요, 연관 배열을 이용하여 키에 결과값을 저장합니다. 라고 말했는데 저는 연관 배열이 뭔지도 모르고, 그걸 이용해서 키에 값을 어떻게 저장하는지도 모르겠어요! 할 수 있습니다. 저도 그랬습니다.
천천히 설명해 봅시다.
휴대 전화 주소록을 예시로 들어 봅시다.
미진이는 편의점 아르바이트를 하면서 새로운 아르바이트 친구 '권예림'을 사귀었어요. 서로 번호를 교환하는데요, 미진이는 이 친구의 이름을 '권예림'이라고 저장을 했습니다.
그러고 주소록을 봤을 때, 'ㄱ' 카테고리에 '권예림'이 들어가 있었어요.
그냥 권예림이라고만 저장을 했는데, 똑똑한 휴대 전화는 알아서 기역이라는 카테고리에 권예림을 분류해서 넣었습니다. 제가 'ㄱ' 카테고리에 넣어 줘~ 한 것도 아닌데 말이죠.
그리고 이 권예림에게 전화를 걸 때, 권예림에 저장되어 있는 번호로 전화를 합니다.
이것과 비슷합니다.
어떠한 키와 값을 넣었을 때 내부적으로 이 데이터를 분류하여 지정된 장소에 키를 넣고, 키를 다시 호출했을 때 값을 반환할 수 있게 하는 것을 해시 테이블이라고 합니다.
hashing은 뭐예요?
데이터 관리 기법입니다. 가변 크기의 입력값에서 고정된 크기의 출력값을 생성해 내는 과정을 해싱이라고 합니다.
hash table의 특징?
- 내부에 hash 함수를 가지고 있고, 해시 함수를 통해서 데이터를 분류하여 정수로 만들고, 그 정수는 인덱스의 값이 되어 그곳에 넣어지게 됩니다.
- 배열의 크기가 정해져 있습니다. 유동적일 수가 없습니다. 인덱스의 값이 유한하다는 가정 하에 hash 함수를 실행하여서 인덱스 값을 설정하기 때문입니다.
hash 함수가 뭐예요?
hash table에 키와 값을 넣으면, key를 사용하여 인덱스의 값을 도출하는 함수입니다. 음, hash table에서의 정의는 이러한데요, 어떠한 값을 넣었을 때 정보를 암호화하거나 조금 더 자료를 정리하기 위해서 일련의 값으로 만들어 내는 것을 뜻합니다.
해시 함수는 아주 간단하게부터 시작해서 아주 어렵게도 만들 수 있는데, 아주아주 간단하게 만들어 보겠습니다.
function hashfn(key) {
let pw;
pw = Math.floor(key.length / 2);
return pw
}key인 'apples'과 value인 '사과는 사각사각해서 싫어'를 해시 테이블에 넣었을 때, 해시 테이블은 해시 함수로 키 값을 보내고, 해시 함수는 key.length / 2를 통하여 인덱스의 값을 도출해내는데요, 예제에서의 key 'apples'는 6 글자이므로 3을 받겠죠?
그 인덱스를 받은 해시 테이블은 자신의 스토리지의 인덱스 3번에 데이터를 저장하게 됩니다.
hash 함수에게는 특징이 여러 개 있습니다.
- array의 크기 안에서 값이 나와야 함. => array 안에 넣을 것이기 때문에, 지정된 array를 벗어난 인덱스에 넣을 수 없다.
- 언제든지 넣었을 때 같은 값이 나와야 함. => 권예림을 넣었을 때, 언제는 ㅎ에 가 있고, 언제는 ㄱ에 가 있는다면 아주 헷갈릴 것이다. 그렇기에 같은 값을 넣었을 땐 똑같은 숫자가 나와야 한다.
- 들어온 key에 대하여 어떠한 저장도 할 수 없음. => 해시 함수는 인덱스만 도출해내는 공장 같은 것이기 때문에, 어떠한 값도 저장을 할 수가 없다.
- 들어오는 값을 숫자로 바꿈.
- 해시 충돌이 일어날 수 있음.
해시 충돌이 뭐예요?
문자열은 무한하고 인덱스는 유한합니다. 그렇기 때문에 무한한 문자열을 고유한 인덱스에 담기 어려운데요. 그래서 해시 함수는 한정된 인덱스에 값을 얼마나 골고루 넣을 수 있냐에 대한 알고리즘이 잘 된 것을 아주 높게 평가합니다.
다시 주소록을 참고하자면.......
세상에 권씨가 권예림만 있는 게 아닙니다. 권소희도 있을 것이고, 권가진도 있을 것이고....... 그렇기에 고유한 인덱스 주소를 가질 수 없습니다. 그래서 인덱스를 공유하는 것인데요.
만약, ㄱ의 인덱스에 권예림이라는 데이터를 담았다고 가정했을 때, 권소희가 들어왔습니다. 그러면, 어떻게 우리는 이 문제를 해결해야 할까요?
해시 충돌을 돌파하는 방법
여러 방법을 제안하고 있는데요, 크게는 두 가지로 갈래가 나눠집니다. 몇 가지만 알아볼게요.
- open addressing: 다른 여분의 인덱스에 설정하기
1-1. 선형 탐사: 만약 1번 칸이 비어 있다면 2번 칸이 비어 있는지 검사 후, 비어 있다면 2번 칸에 넣음.
1-2. 이중 해시: 해시 함수를 2개로 두고, 평소에는 1만 쓰다가 충돌시 2를 써서 새로운 인덱스로 조정 - Close addressing: 충돌이 일어나도 해당 위치에 저장한다. 하지만 여러 개를 둘 수 있는 다른 방법을 사용함.
2-1. 버켓: 배열의 한 요소가 다시 배열임. 2차원 배열처럼. 그래서 해시 충돌이 일어나게 되면 요소 안의 배열로 쌓인다.
2-2. 체이닝: 충돌된 값들을 연결 리스트로 연결.
저는 2번의 갈래를 좋아합니다.
(제가 그린 그림이지만 진짜 못 그렸네요)
hash table의 장단점?
장점: 해싱된 키를 가지고 배열의 인덱스를 사용하여 검색하기 때문에 추가, 삭제 및 탐색이 아주 쉽고 빠르다.
해시 충돌이 없을 때는 O(1)의 상수 시간에 가까워지고, 해시 충돌이 많아질수록 O(n)에 가까워진다.
단점: 해시 함수를 사용하는 데에 추가적인 연산이 필요하다.
해시 테이블의 크기가 유한적이고, 해시 함수의 특성상 해시 충돌을 일으킬 수 있다.
적은 데이터를 가지고 해시 충돌을 연결 리스트를 사용한다면 캐시 효율이 떨어진다.
해시 테이블 안의 데이터가 25% ~ 75% 정도 차 있을 때 가장 최상의 효율을 내기 때문에, 25% ~ 75%의 공간을 맞추기 위하여 resizing을 할 수 있다.
만약 배열의 인덱스가 8개이고 6개가 차 있는데 1개가 더 들어온다면, 해시 테이블은 75% 이상임을 인지하고 8개의 두배인 16개로 늘린다. 혹은 2개 이하로 떨어질 땐 해시 테이블은 25% 이하임을 인지하고 4개로 줄인다.
해시 테이블을 늘이거나 줄일 땐 그 인덱스에 맞춰 해싱을 다시 해 줘야 되는 번거로움을 가지고 있다.
hash table의 구조
(타블렛아 맥북한테 좀 곁을 내주지 않을래?)
요기서 storage, tuple, bucket이 나왔는데요, 요 용어에 대해서 도 말해 봅시다.
storage: 해시 테이블의 그 "테이블"입니다. 데이터들을 저장하는 공간이고, 배열입니다.
bucket: 데이터가 들어갈 공간을 말하는데요, 이 버켓은 인덱스에서 담겨 있고, 데이터 하나마다 버켓 하나가 들어갑니다.
tuple: 데이터들을 담고 있는 곳을 말하는데요, 이 데이터는 수정 혹은 추가, 삭제할 수가 없기 때문에 tuple과 같은 첨삭이 불가한 읽기 전용입니다.
hash table method
hash table을 포함한 limited Array, hash function이 있는데, 메소드를 나열하고, 구현하는 건 hash table에 국한합니다.
- insert: 키와 값을 해시 테이블에 넣어 줍니다.
- retireve: 키를 넣었을 때, 값이 나옵니다.
- remove: 해당 데이터를 삭제합니다.
- _resize: 25%~75%의 효율을 지킬 수 있도록 배열의 사이즈를 줄이거나 키웁니다.
수도 코드
메소드를 수도 코드로 구현해 봅시다.
변수 index는 해시 함수에서 key를 해싱 한 상태입니다.
- insert
- obj을 하나 생성한다. (bucket)
- storage에 해당 index가 없으면 obj[key] = value로 설정하고 값을 스토리지에 넣어 준다.
- 만약 해당 인덱스가 있다면 storage를 obj으로 할당하고, 그 obj에 key와 value를 넣는다.
- size에 1을 추가한다.
- 만약 데이터가 스토리지에 75% 이상 찼다면, 2배로 resizing한다.
- 스토리지를 리턴한다.
- retireve
- 스토리지에 해당 인덱스가 없다면 undefined를 리턴한다.
- 스토리지에 해당 인덱스가 있다면 그 인덱스의 키를 리턴한다.
- remove
- 삭제할 값을 변수에 넣는다.
- 해당 값을 undefined로 만든다.
- 사이즈를 -1 줄인다.
- 만약 사이즈를 줄였을 때, 데이터의 비중이 25% 이하라면 절반으로 resizing한다.
- 1번의 변수를 리턴한다.
- _resize
- 전달인자를 2배 이상 혹은 절감의 limit 길이로 받는다.
- 현재 스토리지를 oldStorage의 변수로 받는다.
- 리밋을 변수 리밋으로 할당하고, 현재 스토리지를 새로운 변수 리밋으로 변환시킨다.
- 반복문을 사용하여 oldStorage의 인덱스의 키가 undifined인 것을 찾아서 딜리트한다.
- 반복문을 사용하여 oldStorage를 현재의 스토리지에 넣는다. (재귀)
JS CODE
해시 펑션이 있다는 가정 / limited_array가 있다는 가정(limited array는 get, set, each의 메서드를 가지고 있음)
class HashTable {
constructor() {
this._size = 0;
this._limit = 8;
this._storage = LimitedArray(this._limit);
}
insert(key, value){
const index = hashFunction(key, this._limit);
let bucket = {};
if(this._storage.get(index) === undefined) {
bucket[key] = value;
this._storage.set(index, bucket);
}else {
bucket = this._storage.get(index);
bucket[key] = value;
this._storage.set(index, bucket);
}
this._size++;
if ((this._size / this._limit) * 100 > 75) {
this._resize(this._limit * 2);
}
return this._storage
}
retrieve(key){
const index = hashFunction(key, this._limit);
if(this._storage.get(index) === undefined) {
return undefined;
}
return this._storage.get(index)[key];
}
remove(key){
const index = hashFunction(key, this._limit);
let delValue = this._storage.get(index)[key];
this._storage.get(index)[key] === undefined;
this._size--;
if ((this._size / this._limit) * 100 < 25) {
this._resize(this._limit / 2);
}
return delValue;
}
_resize(newLimit){
let oldStorage = this._storage;
this._size = 0;
this._limit = newLimit;
this._storage = LimetedArray(this._limit);
oldStorage.each(obj => {
for (let objKey in obj) {
if(obj[objKey] === undefined) {
delete obj[objKey];
}
}
});
//oldStorage의 storage[i]를 obj라는 변수로 넣음
oldStorage.each(busket => {
for (let tuple in busket) {
this.insert(tuple, busket[tuple]);
}
});
return this._stroage;
}
}
