[자료구조] 해시 테이블에 대해서 알아보자 (자바스크립트 JS)

안녕하세요! 이번 시간에는 선형 자료구조인 해시테이블에 대해 알아보겠습니다. :)

 

---

 

학창 시절 사물함을 떠올려보자.사물함의 각 칸에는 이름과 번호가 있기 때문에 우리는 쉽게 위치를 찾을 수 있었다.

해시 테이블은 사물함과 비슷하다. 해시 테이블은 한정된 배열 공간에 key를 index로 변환하여 값을 넣게 된다.

그럼 index는 어떻게 구할까?

 

해시테이블

키와 값을 받아 키를 해싱(Hashing)하여 나온 index값을 저장하는 선형 자료구조

삽입은 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행한다.

 

용어설명

각 테이블에 해당하는 index를 해시 테이블에서는 버킷이라고 부른다.

테이블의 각 요소는 키와 값을 저장하고 있어야 한다.

Hash 는 '고기와 감자를 잘게 다져 요리한 것'을 말한다.

해시 테이블의 해시도 입력받은 키를 잘게 잘라 숫자로 만든다는 점이 비슷하다.

 

해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수다. 해시 함수는 특정한 구현 방법이 있지는 않다.

해시 함수는 문제점이 있는데, '만약 해시 함수의 결과가 동일하여 겹친다면?' 이런 경우에 충돌이 난다는 것이다.

 

Hash Collision

해시 충돌을 해결하기 위한 방법을 알아보자

 

선형탐사법

충돌이 난다면 옆으로 한 칸 이동한다.

단순하지만 특정 영역에 데이터가 몰릴 수 있다는 단점이 있으며,

이동한 버켓에서 또 충돌이 발생한다면 충돌이 나지 않을때까지 반복한다.

그래서 이름 그대로 최악의 경우 탐색에 선형시간이 걸릴 수도 있다.

 

제곱탐사법

선형탐사법의 단점을 보완해 특정 영역에 데이터가 몰리지 않게끔 하는 방식이다.

충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.

충돌이 발생할수록 범위가 커지기 때문에 데이터가 몰리는 것이 선형탐사법보다 덜 한다.

 

이중해싱

충돌이 발생하면 또 다른 해시 함수를 이용하여 새로운 index를 만들어낸다.

또 충돌이 발생하면 충돌이 발생하지 않을떄까지 두번쨰 해시로 계속해서 인덱스를 만들어낸다.

 

분리 연결법

앞서 소개한 세가지 방법과는 다르게 충돌이 발생할 경우 다른 인덱스로 이동하지 않는다.

대신 해시 테이블의 요소를 연결 리스트로 만들어 충돌이 발생한 버킷에 그대로 사용한다.

(버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

대신 이방법은 최악의 경우에 하나의 버킷이 무한정 늘어날 수 있다는 단점이 있다.

 

 

Hash Table은 어디에 사용할까?

학생 정보를 관리하는 소프트 웨어를 만든다고 가정해보자.

어떻게 만들어야 학생 정보를 빠르게 기록하고 찾을 수 있을까?

연결리스트를 떠올려보자. 학생을 추가하거나 제거하는 데에는 빠르지만, 찾을 때 선형시간만큼 시간이 걸린다.

배열을 이용할 수 있지만 index를 모를 경우 모두 찾아봐야 하기 때문에선형시간이 걸린다.

 

따라서 이런 경우에는 해시 테이블을 사용하는 것이 유리하다.

이름을 키로하여 탐색과 삽입, 삭제가 모두 상수시간만에 끝난다.

최악의 경우에는 탐색에 선형시간이 걸릴 때도 있지만 연결리스트나 배열보다는 안정적이라고 할 수 있다.

 

 

 

자바스크립트에서 사용하기

 

JavaScript Array ≈ Hash Table

---

우선 우리가 사용하던 배열은 실제로는 객체 타입이라 해시 테이블로 사용할 수 있다. 단, 이 방법은 올바른 사용법이라고는 할 수 없기 때문에 추천하지 않는다.

const table = [];
table["key"] = 100;
table["key2"] = "Hello";
console.log(table["key"]); // 100
table["key"] = 349;
console.log(table["key"]); // 349
delete table["key"];
console.log(table["key"]); // undefined

 

JavaScript Object ≈ Hash Table

---

제일 간단한 방법으로 객체를 이용할 수도 있다.

const table = {};
table["key"] = 100;
table["key2"] = "Hello";
console.log(table["key"]); // 100
table["key"] = 349;
console.log(table["key"]); // 349
delete table["key"];
console.log(table["key"]); // undefined

 

Map

---

별도로 맵 객체를 사용할 수도 있다. set 함수를 이용하여 값을 넣고, get 함수를 이용하여 값을 찾을 수 있다.

const table = new Map();
table.set("key", 100);
table.set("key2", "Hello");
console.log(table["key"]); // undefined
console.log(table.get("key")); // 100
const object = { a: 1 };
table.set(object, "A1"); // Map은 Object도 Key로 쓸 수 있다.
console.log(table.get(object)); // A1
table.delete(object);
console.log(table.get(object)); // undefined
console.log(table.keys()); // {'key', 'key2'}
console.log(table.values()); // { 100, 'Hello' }
table.clear();
console.log(table.keys()); // { }
console.log(table.values()); // { }

 

기존의 객체와는 다르게 key 값으로 object나 배열같은 복잡한 타입도 사용할 수 있다. 객체의 경우 들어오는 값이 정수가 아닌 경우, 전부 문자열로 바꿔버리기 때문에 다양한 타입을 넣고 싶다면 Map을 이용하는 것이 유리하다. 여러 편리한 메소드를 제공해주고, 순회를 편하게 할 수 있다는 장점도 있다.

 

 

Set

---

Set을 사용할 수도 있다. Set은 키와 값이 동일하게 저장되는 방식을 채택하고 있다. 일종의 집합 연산이라고 볼 수 있다.

따라서 중복된 내용을 전부 제거할 때 사용할 수 있다.

const table = new Set();
table.add("key");
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