[알고리즘][JS] 해쉬 알고리즘 - JS ES6 Map()

해쉬 알고리즘이란?

해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 이를 이용해 특정한 배열의 인덱스나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존의 자료 구조들을 탐색이나 삽입을 할 때 선형시간이 걸리기도 했던 것에 비해 해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더 빠른 속도로 처리할 수 있다.

1. 직접 주소 테이블(Direct Addressing Table)

 

 

Direct Addressing Table은 key-value 쌍의 데이터를 배열에 저장할 때 key값을 직접적으로 배열의 인덱스로 사용하는 방법이다. 예를 들어 키 값이 400인 데이터가 있다면 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.

똑같은 키 값이 존재하지 않는다고 가정하면 삽입 시에는 각 키마다 자신의 공간이 존재하므로 그 위치에다 저장을 하면 되고, 삭제 시에는 해당 키의 위치에 NULL값을 넣어주면 된다. 탐색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.

찾고자 하는 데이터의 key만 알고있으면 즉시 위치를 찾는 것이 가능하므로 탐색, 저장, 삭제, 갱신은 모두 선형시간인 O(1)로 매우 빠른 속도로 처리가 가능하다.

하지만 key값의 최대 크기만큼 배열이 할당되기 때문에 크기는 매우 큰데 저장하고자 하는 데이터가 적다면 공간을 낭비할 수 있다는 단점이 있다.

 

class DirectAddressTable { 
  constructor () { 
  	this.table = [];
  } 
  setValue (value = -1) { 
  	this.table[value] = value; 
  } 
  getValue (value = -1) { 
  	return this.table[value]; 
  } 
  getTable () { 
  	return this.table; 
  } 
}

const myTable = new DirectAddressTable(); 
myTable.setValue(7); 
myTable.setValue(20); 
myTable.setValue(50); 
console.log(myTable.getTable());

 

콘솔에서 실행 결과

2. 해쉬 테이블(Hash Table)

 

 

Hash Table은 key-value 쌍에서 key값을 테이블에 저장할 때, Direct Addressing Table과는 달리 key값을 함수를 이용해 계산을 수행한 후, 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key값을 계산하는 함수는 해쉬 함수(Hash Function)이라고 부르며, 해쉬 함수는 입력으로 key를 받아 0부터 배열의 크기-1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기 만큼으로 변환시킨 것이다.

이 경우 k값이 h(k)로 해쉬되었다고 하며, h(k)는 k의 해쉬값이라고 한다.

 

위 그림을 참조하면 각 k값을듸 해쉬값인 h(k)값들이 배열의 인덱스로 사용됨을 확인할 수 있다.

해쉬 테이블은 Direct Addressing Table에 비해 공간 낭비가 매우 적은데, 이는 key값의 크기에 테이블의 크기가 좌우되는 것이 아니고, h(k)만큼의 공간에 저장되기 때문이다.

 

---

JS ES6 Map()

Map()은 자바스크립트의 key-value 페어(pair)로 이루어진 컬렉션으로, key를 이용해 value를 get, set 할 수 있다. 이 때 key 들은 중복될 수 없다. (하나의 key에는 하나의 value만)

 

const map1 = new Map();

map1.set('a', 1);
map1.set('b', 2);
map1.set('c', 3);

console.log(map1.get('a'));
// expected output: 1

map1.set('a', 97);

console.log(map1.get('a'));
// expected output: 97

console.log(map1.size);
// expected output: 3

map1.delete('b');

console.log(map1.size);
// expected output: 2

Map과 Object 비교

Object는 Property와 Method를 가지며, 여기서 property가 Map의 key역할을 한다고 생각하면 된다. Object에서 property는 하나의 값과 연결되며 충돌이 발생하지 않도록 유의해야 한다. 

 

var obj = { 
  "key1" : "value1" 
  "key2" : "value2" 
} 
obj.key1; // result : value1 
obj.toString(); // result : [object object]

 

정의상으로는 Object와 Map의 기본적인 콘셉트는 같다. 데이터를 저장하기 위해 Key와 Value를 사용한다는 점에서 말이다. 실제로 Map이 등장하기 전에는 Object가 Map의 역할을 수행했다. 값에 키를 할당할 수 있고, 키를 사용하여 값을 얻을 수 있으며, 키를 삭제하거나 키가 존재하는지 확인할 수 있는 등 대부분의 Map의 기능을 제공하기 때문이다.

 

그렇다면 ES6에 Map이 추가된 이유는 무엇일까?

위 그림과 같이 Object와 Map은 유사한 듯 하지만 분명하게 차이점이 존재한다.

 

• 사용 가능한 Key의 타입
  • Object: string과 symbol(ES6)만 가능
  • map: 어떤 값도 가능(함수, 객체, 원시 자료형 등)
• 순회
  • Object: Key의 배열을 얻어 이 배열을 이용하여 순회
  • Map: built-in iterable. 바로 순회 가능
• 크기
  • Object: 크기를 추적해 직접 판별해야 함
  • Map: size 속성을 이용해 쉽게 얻을 수 있음
• 정렬
  • Object: 안 함
  • Map: 삽입 순으로 정렬
• Object는 프로토타입을 가지기 때문에 주의하지 않으면 Key가 충돌할 수 있음

위의 차이점만 보았을 때는 Map이 Object보다 더 많은 장점이 있는 것 처럼 보이지만, 어떤 경우에는 Object가 더 나은 성능을 보일 때도 있다.

언제 써야 하는가?

 

Object

• 데이터는 저장하기 위한 간단한 구조. Key가 String이거나 integer(또는 Symbol)인 경우에 사용한다. Map을 생성하는 것보다 기본 오브젝트를 생성하는 데 훨씬 적은 시간이 걸리기 때문!
• 각각의 property/element가 별도의 로직이 적용되어야 하는 경우
• JSON으로(에서) 변환해야 하는 경우(Map은 현재 지원하지 않음)

 

Map

• Key의 추가/삭제가 빈번한 경우: Map은 순수한 Hash이고 Object는 그보다 복잡하기 때문에 속도가 Map이 더 뛰어남. 또한 Object Property를 삭제하는 delete 연산은 몇 가지 성능 이슈가 존재함
• Key의 순서가 보장되어야 할 때: Map은 iteration 기반으로 만들어졌기 때문에 기본적으로 순서를 유지
• 데이터의 크기가 클 때: 더 나은 성능을 보임
• 런타임 시점까지 key가 정해지지 않은 경우
• key와 value가 각각 같은 타입일 경우