해시 테이블(Hash Tabel)
해시 테이블?
해시 함수 : 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
해시 테이블은 한정된 공간에서 key를 index로 변환하여 값들을 넣게된다.
키와 값을 받아 키를 해싱(Hasing)하여 나온 index에 값을 저장하는 선형 자료구조다.
삽입은 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행된다.
해시 테이블을 사용하면 O(1)에 값을 찾을 수 있다. 따라서 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋다.
해시 충돌
해시 함수의 키가 동일한 경우 해시 충돌이 발생하는 문제가 있다.
해시 충돌 해결 방법
-
선형 탐사법 : 충돌이 발생하면 옆으로 한 칸 이동한다. 옆의 칸이 비어있을 때 까지 이동해야하기 때문에 O(n)이 걸린다.
-
제곱 탑사범 : 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
-
이중 해싱 : 충돌이 발생하면 다른 해시 함수를 이용한다.
-
분리 연결법 : 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다. 하지만 최악의 경우 하나의 버킷에 값이 무한이 증가할 수 있다.
사용 방법
- 배열
배열은 실제로 객체타입이라 해시 테이블처럼 사용할 수 있지만 배열의 올바른 사용방법은 아니다.
const hashTable = [];
hashTable["key1"] = "Hi";
hashTable["key2"] = "Hello";
console.log(hashTable["key1"]) // Hi
console.log(hashTable["key2"]) // Hello- 객체
객체를 이용하는 방법이 제일 간단하고 정석이다.
const hashTable = {};
hashTable["key1"] = "Hi";
hashTable["key2"] = "Hello";
console.log(hashTable["key1"]) // Hi
console.log(hashTable["key2"]) // Hello- Map
Map은 set함수를 이용하여 값을 넣고 get함수를 이용하여 값을 찾을 수 있다. 키 값을 다양한 타입을 넣고 싶다면 map을 사용하자, 여러 편한 메소드를 지원해주며 순회를 편하게 할 수 있다.
또한 delete로 요소를 삭제할 수 있고 clear로 map 객체를 비울 수 있다.
const hashTable = new Map;
hashTable.set("key1", "Hi");
hashTable.set("key2", "Hello");
console.log(hashTable.get("key1")) // Hi
console.log(hashTable.get("key2")) // Hello- Set
set은 키와 값을 동일하게 저장하는 방식을 이용한다. set은 중복된 내용을 모두 제거할때 사용할 수 있다.
const hashTable = new Set;
hashTable.add("Hi");
hashTable.add("Hello");
console.log(hashTable.has("key1")) // true
hashTable.delete("key1") // key1 삭제
hashTable.clear() // 모두 삭제