[자료구조] 해시테이블(HashTable), 해시맵(HashMap) in Javascript

zzzzsb·2022년 7월 18일

Hash Table hash 자료구조 해시 해시 테이블

자료구조&알고리즘

목록 보기

3/8

해시테이블(HashTable)

해시 테이블은 key-value pair로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 자료구조이다.

해시테이블(Hash Table)의 구조

해시테이블에 대해 이해하기 위해서는 먼저 해시테이블의 구성에 대해 이해할 필요가 있다.

해시테이블은 키(key), 해시 함수(Hash Function), 해시(Hash), 값(value), 저장소(bucket, slot)로 이루어져 있다.

해시테이블에서 키 값은 해시함수를 통해 해시로 변경(인덱스 매핑) 되며, 이 해시 값은 값과 매칭되어 저장소에 저장된다.

키(key)

키(key)는 고유한 값으로, 해시 함수의 input이 된다. 저장할 때 공간의 효율성을 추구하기 위해 값을 해시 함수로 바꾸어 저장한다.

값(value)

값(value)은 저장소(bucket, slot)에 최종적으로 저장되는 값으로, 키와 매칭되어 저장, 검색, 접근, 삭제가 가능하다.

해시 함수(Hash Function)

해시함수는 key를 고정된 길이의 해시로 변경해주는 역할을 한다. 다양한 길이를 가진 키를 고정된 길이의 해시로 변경해 저장소를 효율적으로 운영할 수 있도록 한다.

이때 해시 함수를 통해 키 값을 해시로 변경하는 작업을 해싱(Hashing)이라고 한다.

해시(Hash)

해시는 해시함수의 결과물로, 해시 테이블의 저장소(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)의 시간복잡도를 갖는다. 따라서 매우 빠르게 데이터를 저장하고 탐색, 삭제할 수 있는 효율성이 좋은 자료구조이다.

하지만 장점만 있을까?
해시테이블에서는 해시 충돌이 발생할 수 있다.

해시맵(HashMap) with Javascript

해시테이블은 속도가 빠르기에 자주 사용되며, 대부분의 프로그래밍 언어에서는 아래와 같은 해시 자료구조를 가지고 있다.

Python: Dictionary

Javascript: Map, Object(객체에서는 key로 문자열만 사용 가능), Set

Java, Go, Scala: Map

Ruby: Hash

자바스크립트에서 해시테이블은 Map, Object, Set이 있다.
본래 자바스크립트에서 해시테이블 자료구조는 Object가 대표적이었으나, ES6에서 Map과 Set이 추가되었다고 한다.

대표적으로 해시맵이라고도 불리는 Map에 대해 정리해 보려 한다.

Map 객체

Map 객체는 key-value로 이루어진 해시테이블이다.

set(): key-value pair를 map에 삽입
get(): key값으로 value를 찾아 리턴
key에 들어갈 수 있는 자료형은 number, string, function, object, NaN 등이 가능하다.

Map 객체 생성

var map = new Map();

Map에 key-value 쌍 데이터 삽입: set(key, value)

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}

key로 value값 반환: get(key)

map.get(str); // 1
map.get(obj); // 2
map.get('none'); // undefined  
map.get({ a: 1 }); // undefined, obj !== { a: 1 }

map에 해당 key의 value 존재 여부: has(key)

map.has(str); // true
map.has(obj); // true
map.has('none'); // false

map의 크기: map.size()

map.size // 4
map.length // undefined

map 탐색

//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)
}

참고 자료

zzzzsb

성장하는 developer

이전 포스트

[자료구조] 큐(Queue)

다음 포스트