해시 테이블 (Hash Table)

Jun 2k (Jun2)·2023년 9월 27일

자료구조&알고리즘

목록 보기

8/19

해시 테이블

키와 값을 받아 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료 구조이다.
삽입은 O(1), 키를 알고 있다면 삭제, 탐색도 O(1)의 시간 복잡도를 가진다.
각 테이블에 해당하는 index를 bucket이라고 부른다.

해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수
함수의 유형은 정해져 있지 않다.
대표적인 예시로는 문자열로 된 키 값의 각 문자의 아스키코드를 더한 값을 해시로 변환 가능하다.

해시 테이블의 문제점

만약 해시 함수의 결과가 동일하여 겹칠 가능성이 있다면? => 해시 충돌

해시 충돌 (Hash Collision)의 해결 방법

선형 탐사법
충돌이 발생하면 index를 옆으로 한 칸 이동한다.
제곱 탐사법
충돌이 발생하면 충돌 발생한 횟수의 제곱만큼 옆으로 이동한다.
=> 선형탐사법보다 데이터가 몰리는 빈도가 적다.
이중 해싱
충돌이 발생하면 다른 해시 함수를 이용한다.
해시 함수를 교체하면서 새로운 index를 만든다.
분리 연결법
버킷의 값을 연결 리스트로 사용해서 충돌 발생 시 값을 추가한다. 최악의 경우 하나의 bucket에 값이 몰릴 수 있다.

해시 테이블의 사용 예시

학생 정보 관리하는 경우
연결 리스트를 사용하면 학생 정보를 알고 싶을 때 O(n)의 시간 복잡도가 걸린다.
배열도 인덱스를 모르면 찾는데 O(n)의 시간 복잡도가 필요하다.

따라서 빠르게 값을 찾아야 하는 경우에는 해시 테이블을 사용하는 것이 좋다.
해시 테이블을 사용하여 키-값 형태로 찾게 되면 O(1)의 시간 복잡도가 소요된다.

JavaScript에서 해시 테이블을 구현

JavaScript Array

자바스크립트에서 배열은 객체 타입이라 해시 테이블처럼 사용 가능하다.
하지만 이것은 올바른 방법은 아니기에 권장하지는 않는다.

const table = [];
table['key'] = 100;
table['key2'] = 'Hash';
console.log(table['key']); // 100

table['key'] = 200;
console.log(table['key']); // 200
delete table['key'];
console.log(table['key']); // undefined

JavaScript Object

가장 간단하고 정석적인 방법은 객체를 사용하는 것이다.

const table = {};
table['key'] = 100;
table['key2'] = 'Hash';
console.log(table['key']); // 100

table['key'] = 200;
console.log(table['key']); // 200
delete table['key'];
console.log(table['key']); // undefined

Map을 사용

set 함수를 이용하여 값을 넣고 get 함수를 통해 값을 찾는다.
기존 객체와 다르게 object 값도 key로 사용 가능하다.
다양한 타입을 key로 사용하기 위해서는 Map을 사용한다.
다양한 메서드와 순회가 편리하다.

const table = new Map();
table.set('key', 100);
table.set('key2', 'Hi');
console.log(table['key']); // undefined
console.log(table.get('key')); // 100

const object = { a: 23 };
table.set(object, 'A1'); // Map 객체는 Object를 key로 사용 가능
console.log(table.get(object)); // A1

table.delete(object); // key, value 삭제
console.log(table.get(object)); // undefined
console.log(table.keys()); // { 'key', 'key2' }
console.log(table.values()); // { 100, 'Hi' }
table.clear();
console.log(table.values()); // {  }

Set을 사용

키와 값이 동일하게 저장된다.
수학에서의 집합과 동일하다. 중복된 내용을 제거할 때 용이하다.

const table = new Set();
table.add('key'); // key와 value가 동일하게 저장된다.
table.add('key2');
console.log(table.has('key')); // true
console.log(table.has('key3')); // false

table.delete('key2');
console.log(table.has('key2')); // false
table.add('key3');
console.log(table.size); // 2
table.clear();
console.log(table.size); // 0