[JS|자료구조] 자바스크립트(javascript)의 Hash(해시) 알아보기

 

- Hash란?

해시(Hash) : 대량의 데이터들의 빠른 삽입, 삭제, 검색을 위한 자료구조

 

먼저, 자료구조 Hash를 사용하는 이유에 대하여 자세히 알아보자.

만약 대량의 데이터를 선형 검색한다면, 찾아낼 값이 나올 때까지 모든 데이터를 확인하므로 최악의 경우 O(N)의 시간이 걸린다.

하지만 대량의 데이터를 Hash 함수를 사용하여 저장한 뒤 검색한다면, 데이터는 한 번에 찾아낼 수 있을 것이다 (O(1))

 

다음 그림으로 확인해볼 수 있다.

 

 

다음과 같이 해시함수를 활용하여 해시값으로 변환하여 저장한다면, 원하는 데이터를 보다 더 빠르게 탐색할 수 있다.

---

자료구조 해시의 구조와 특징에 대하여 알아보자.

관련된 단어와 개념들에 대하여 다음과 같이 정리할 수 있다.

 

 

자바스크립트에서 해시를 구현하는 방법을 알아보자.

자바스크립트에서는 {키 : 값} 형태를 지닌 Object, Map, Set의 자료형을 사용하여 hash처럼 활용할 수 있다.

 

 

어떤 언어를 사용하는 지는 개인차이지만

 

반복문 순회가 가능하고, 데이터 삽입/삭제에 좋은 성능을 보이며, size 확인이 가능한 Map을 사용하는 것을 권한다.

 

MDN 문서 : 자바스크립트의 Map 객체에서 본 Map과 Obejct의 차이

1. 반복문 순회가 가능하다.

 

2. 데이터 삽입/삭제에 좋은 성능을 보인다.

 

3. size 확인이 가능하다.

 

 

Map을 HashTable처럼 활용하기

1. Map에 {키 : 값}을 저장하기 : Map.prototype.set()

let hashTable = new Map()

 

- set() 메소드를 사용하여 Map에 {키 : 값}을 저장한다.

hashTable.set('1', '010-1111-1111')
hashTable.set('2', '010-2222-2222')

console.log(hashTable)
// Map(2) { '1' => '010-1111-1111', '2' => '010-2222-2222' }

 

- 주의할 점!

     ㄴ ['key']의 형태로 저장할 때, 알맞게 저장한 것처럼 보이지만 사실 이는 객체의 기능을 사용하는 것이므로 다르게 저장되어진다.

 

hashTable['3'] = '010-3333-3333'

console.log(hashTable)
// Map(2) {
// '1' => '010-1111-1111',
// '2' => '010-2222-2222',
// '3': '010-3333-3333'
// }

 

 

다음과 같이 Map에는 저장되어있지 않은 것으로 확인된다.

console.log(hashTable.has('1')) // true
console.log(hashTable.has('3')) // false

 

 

2. Map에서 키를 통해 값을 불러오기 : Map.prototype.get()

- get() 메소드를 사용하여 Map에 저장되어있는 값을 키를 통해 불러온다.

console.log(hashTable.get('2'))
// 010-2222-2222

 

3. 반복문 사용하기 : (for [key, value] of Map), (forEach(value, key, Map))

- for [key, value] of Map 사용하기

for ([key, value] of hashTable) {
console.log(`${key}: ${value}`)
}
// 1: 010-1111-1111
// 2: 010-2222-2222

 

 

 

- forEach(value, key, Map) 사용하기

hashTable.forEach((value, key, hashTable) => {
console.log(`${key}: ${value}`)
})

// 1: 010-1111-1111
// 2: 010-2222-2222