해시테이블 (Hash Table)란?
- Key-Value 형태를 갖는 하나의 자료구조이다.
- 빠르고 효율적으로 데이터를 검색할 수 있다.
해시 테이블은 해시 함수를 사용하여 각 키를 고유한 인덱스로 매핑하고, 해당 인덱스에 값을 저장한다.
- 해시 함수는 입력으로 받은 키를 고정된 길이의 해시 값으로 변환하는 함수로 입력이 같으면 항상 같은 해시 값을 반환해야 한다.
- 해시 테이블은 일반적으로 배열을 기반으로 하며, 각 배열 요소는 버킷(bucket)이라고 불리는 공간에 하나 이상의 Key-Value 쌍을 저장할 수 있다.
배열의 인덱스는 오직 정수로만 접근 가능하지만, 해시는 String 타입이나 다른 어떤 데이터형을 기반으로 자료구조를 접근하고 데이터를 관리할 수 있다.
해시테이블 시간복잡도
-
해시 테이블의 주요 연산에 대한 시간 복잡도는
O(1)이다. 해시 함수를 통해 고유한 인덱스를 찾아내기 때문이다. -
그러나 모든 키가 동일한 해시값을 가지거나 모든 키가 동일한 인덱스로 매핑되는 경우 충돌이 발생하고, 이처럼 데이터의 충돌이 발생한 경우 시간 복잡도는
O(N)이 될 수 있다.
해시 충돌이란?
서로 다른 입력에 대해 동일한 해시 값이 생성되는 상황을 말한다. 즉, 서로 다른 두 개의 데이터가 동일한 해시 값으로 매핑되는 상황을 의미한다.
해시 충돌을 효과적으로 관리하는 방법으로 분산 체이닝(Separate Chaining)과 개방 주소법(Open Addressing)이 있다.
분산 체이닝(Separate Chaining)
- 해시 충돌이 발생했을 때 각 해시 버킷을 연결 리스트로 만들어 충돌된 Key-Value쌍을 그 버킷에 연결하여 저장하는 방법이다.
- 각 버킷은 독립된 연결 리스트를 가지고 있어, 충돌이 발생하더라도 해당 버킷의 연결 리스트에 추가함으로써 충돌을 처리한다.
- 장점 : 연결 리스트를 통해 충돌을 효과적으로 처리할 수 있다.
- 단점 : 메모리를 효율적으로 사용하기 위해서는 연결 리스트의 크기를 적절히 조절해야 하며, 데이터의 수가 많아지면 연결 리스트의 크기가 커져 캐시 효율이 떨어질 수 있다.
개방 주소법(Open Addressing)
- 해시 충돌이 발생했을 때 새로운 Key-Value 쌍을 위해 다른 버킷을 찾아주는 방법이다.
- 충돌이 발생하면 다른 방법을 사용하여 새로운 버킷을 찾아가는 방식으로 충돌을 해결하여 하나의 해시 테이블에서 모든 Key-Value 쌍을 저장할 수 있도록 한다.
- 장점 : 메모리 사용의 효율성을 일 수 있고, 충돌이 발생했을 때 다른 버킷을 찾기 위한 추가적인 연산이 필요하기 때문에 헤시 테이블의 로드 팩터를 조절할 수 있다.
- 단점 : 일정 수준 이상의 로드 팩터에서는 성능이 떨어질 수 있으며, 삭제 연산이 복잡할 수 있다.
Map
자바스크립트에서 Map은 Key-Value의 컬렉션을 나타내는 데이터구조이다.
- Map은 어떤 타입이든지 Key로 사용할 수 있다.
- 순서가 보장되지 않는 객체와 달리 Key-Value를 추가한 순서대로 순회한다.
- 중복을 허용하지 않고, 중복된 Key가 추가되면 나중에 추가된 값이 이전 값을 덮어쓴다.
- 객체는 문자열과 심볼을 제외한 모든 키를 문자열로 변환하는 반면 Map은 원래의 키를 그대로 유지한다.
Map 사용법
// 생성
let myMap = new Map();
// 추가
myMap.set("name", "Yun");
// 조회
console.log(myMap.get("name")); // 출력: Yun
// 순회
for (let [key, value] of myMap) {
console.log(`${key} => ${value}`);
}
// 크기 확인
console.log(myMap.size); // 출력: 3
// 키 존재 여부 확인
console.log(myMap.has("name")); // 출력: true
// 키-값 삭제
myMap.delete(1);