[자료구조] 해시(Hash Table)

Hash Table

Hash

고유한 데이터를 다루는 기법 또는 고유한 값

• key-value 구조이다.
• hash table에서 hash는 해시 함수를 통해 만들어진 고유한 값이다.

 

Hash Function

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

• 함수 내부적인 패턴에 의해 고유한 값(hash)이 생성되어 반환된다.
• Input : key // output : Hash
• 이렇게 나온 해시가 저장위치가 된다.

 

Hash Table

해시 함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 주소 또는 색인 삼아 데이터를 key와 함께 저장하는 자료구조

• 자바스크립트에서 Object, (Map, Set)
• 시간복잡도 : O(1)
• 아래 구조로 되어있다.

 

구성

• key : 고유한 값. Input
  • key값을 그대로 저장소의 인덱스로 사용할 경우 key의 길이만큼 정보를 저장해야 한다.
  • 이 때 key의 길이가 제각각이기 때문에 고정된 길이를 가지는 해시로 변경한다.
  • why? 길이가 길면 저장소 공간도 길어지기 때문!
  • ex) john : 100101011101111101101 // 1 : 01
• buckets : 배열 같은 형태. 주소(인덱스)와 저장 공간으로 이루어 짐
  
  • 주소(인덱스) : key로 만들어진 hash
  • 저장 공간 : 실제 value를 담는 공간
• hash function : key → hash로 만드는 함수

 

collision

⚠️ 데이터가 많아짐에 따라 key가 같은 해시 값으로 인해 충돌(collision)이 일어날 수도 있다.

• ex) 해시 함수의 알고리즘이 key의 길이로 해시 값을 만든다고 할 때,
  키로 “피자”, “케이크”, “타코” 를 넣는다면 케이크는 해시 값이 3으로 고유한 값이 되지만,
  피자와 타코는 2로 같은 값을 갖는다.
• 개방 주소법, 체이닝 등의 기법으로 해결한다.

 

장점

• 시간 복잡도가 평균 O(1)로 매우 빠름

 

단점

• 해시 충돌 발생
• 순서/ 관계가 있는 배열은 어울리지 않음
• 공간 효율성 떨어짐(저장공간 미리 확보)
• 해시 함수의 의존도가 높다. 함수가 복잡하면 hash를 만드는데 오래 걸림
  
  

사용

객체

const object = {
	name : "name",
	age : 24,
}

 

Map

const map = new Map();
map.set('p1', 1);
map.get('p1'); // 1

 

Set

const set = new Set();
set.add(1);
set.has(1); // true

---
참고 자료
- 노마드 코더 : https://www.youtube.com/watch?v=HraOg7W3VAM