해시 테이블은 key-value pair로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 자료구조이다.
해시테이블에 대해 이해하기 위해서는 먼저 해시테이블의 구성에 대해 이해할 필요가 있다.
해시테이블은 키(key), 해시 함수(Hash Function), 해시(Hash), 값(value), 저장소(bucket, slot)로 이루어져 있다.
해시테이블에서 키 값은 해시함수를 통해 해시로 변경(인덱스 매핑) 되며, 이 해시 값은 값과 매칭되어 저장소에 저장된다.
키(key)는 고유한 값으로, 해시 함수의 input이 된다. 저장할 때 공간의 효율성을 추구하기 위해 값을 해시 함수로 바꾸어 저장한다.
값(value)은 저장소(bucket, slot)에 최종적으로 저장되는 값으로, 키와 매칭되어 저장, 검색, 접근, 삭제가 가능하다.
해시함수는 key를 고정된 길이의 해시로 변경해주는 역할을 한다. 다양한 길이를 가진 키를 고정된 길이의 해시로 변경해 저장소를 효율적으로 운영할 수 있도록 한다.
이때 해시 함수를 통해 키 값을 해시로 변경하는 작업을 해싱(Hashing)이라고 한다.
해시는 해시함수의 결과물로, 해시 테이블의 저장소(bucket)을 가리키는 주소(인덱스)로 사용된다.
즉, 해시 값이 값과 매칭되어 저장소에 저장된다.
즉 정리해보자면,
해시 함수: key -> hash로 변환해주는 함수
해시: 키 값이 해시 함수로 변환된 것, 저장소의 주소(인덱스)로 사용됨
해시 테이블: hash를 주소 삼아 value를 저장하는 자료구조
연산 | Big-O |
---|---|
삽입(Insertion) | 평균 O(1), 최악 O(N) |
검색(Search) | 평균 O(1), 최악 O(N) |
삭제(Deletion) | 평균 O(1), 최악 O(N) |
해시테이블은 Insertion, Search, Deletion에서 평균적으로 O(1)의 시간복잡도를 갖는다. 따라서 매우 빠르게 데이터를 저장하고 탐색, 삭제할 수 있는 효율성이 좋은 자료구조이다.
하지만 장점만 있을까?
해시테이블에서는 해시 충돌이 발생할 수 있다.
해시테이블은 속도가 빠르기에 자주 사용되며, 대부분의 프로그래밍 언어에서는 아래와 같은 해시 자료구조를 가지고 있다.
- Python: Dictionary
- Javascript: Map, Object(객체에서는 key로 문자열만 사용 가능), Set
- Java, Go, Scala: Map
- Ruby: Hash
자바스크립트에서 해시테이블은 Map, Object, Set이 있다.
본래 자바스크립트에서 해시테이블 자료구조는 Object가 대표적이었으나, ES6에서 Map과 Set이 추가되었다고 한다.
대표적으로 해시맵이라고도 불리는 Map에 대해 정리해 보려 한다.
Map 객체는 key-value로 이루어진 해시테이블이다.
var map = new Map();
let number = 0;
let str = 'string';
let obj = { a: 1 };
let func = () => {
console.log('func');
};
map.set(number, 4); //key에 number 가능
map.set(str, 1); // key에 string 가능
map.set(obj, 2); //key에 object 가능
map.set(func, 3); // key에 함수 가능
map.set(number, 0); // 덮어쓰기 가능
console.log(map); // Map(4) {0 => 0, "string" => 1, {…} => 2, ƒunc => 3}
map.get(str); // 1
map.get(obj); // 2
map.get('none'); // undefined
map.get({ a: 1 }); // undefined, obj !== { a: 1 }
map.has(str); // true
map.has(obj); // true
map.has('none'); // false
map.size // 4
map.length // undefined
//key, value 쌍으로 출력
for (let [key, value] of map) {
console.log(key + ' = ' + value)
}
//key만 출력
for (let key of map.keys()) {
console.log(key)
}
//value만 출력
for (let value of map.values()) {
console.log(value)
}