자료구조 | Hash Map

Hash Map

Image : https://miro.medium.com/max/2058/1*-wSoXj2YIehpaipRq1a8yw.png

데이터 관리에 유용한 자료구조로 보안, 블록체인, 전자서명, 브라우저 로컬스토리지 등에도 많이 활용된다. hash function을 통해 동일한 키는 동일한 값을 만들어 내고 hashing의 결과로 얻어진 값은 배열의 인덱스가 된다. 이때, 소수를 이용하여 배열의 크기를 정하고 인덱스를 연산하면 데이터를 더 고루 배분할 수 있다.

Collision

해싱의 결과 같은 값이 나오면 배열의 같은 인덱스에 데이터가 여러개 들어가게 되므로 충돌이 발생한다. 충돌을 방지하기 위해서 크게 두가지 방법을 사용한다.

1. Seprate Chaining

   인덱스에 담길 데이터를 중첩 배열의 구조로 한다. 그러면 해싱 결과가 같아도 이미 담겨있는 데이터 뒤에 계속해서 데이터를 추가할 수 있다.

2. Linear Probing

   해당 인덱스에 이미 데이터가 있으면 다음 인덱스 중에 빈 곳을 찾아 데이터를 추가한다. 중복을 방지할 수 있지만 금방 메모리가 차버린다는 단점이 있다.
   
   

JS map

자바스크립트의 map 메서드를 사용하면 해싱을 이용할 수 있다. 거의 모든 프로그램 언어는 해시맵을 지원한다.

const map1 = new Map();

map1.set('a',1)
console.log(map1.get('a')); // 1

map1.set('a',24)
console.log(map1.get('a')); // 24

console.log(map1.size); // 1

map1.delete('a');

console.log(map1.size); // 0

시간 복잡도

삽입(set), 제거(delete), 접근(get)의 작업은 O(1)로 매우 빠르다. 하지만 최대값이나 최소값을 구하거나 정렬, 재배치 등 전체 데이터를 탐색해야 하는 경우에는 매우 느리다.

• INSERT: O(1)

• DELETE: O(1)

• ACCESS: O(1)
  
  
  
  

Reference
https://www.udemy.com/course/best-javascript-data-structures/