Javascript Hash Table

Hash

• hash는 잘게 자르다, 뒤섞다, 다져서 섞은 음식 따위를 일컫는 단어
• 원래 형태를 알아보기 어렵게 섞어버리는 공통 특성이 존재
• CS 세계에서는 어떤 데이터를 받아서 짧고 일정한 값으로 뒤섞어 변환하는 것을 의미
• hash의 성질은 다음과 같음
  • 같은 입력은 항상 같은 출력
  • 출력 길이는 고정
  • 입력이 조금만 달라도 출력은 크게 달라짐
  • 되돌릴 수 없음

Hash Table

• 값을 저장할 위치를 계산해서 바로 찾아가는 테이블
• 데이터 ──▶ 해시 함수 ──▶ 인덱스 ──▶ 저장 위치
• 일반 배열을 통해 값을 찾으려면 처음부터 끝까지 순회하는 O(n)의 시간 복잡도
• 해시 테이블은 위치를 계산해서 바로 점프할 수 있기 때문에 평균 O(1)의 시간 복잡도
• 핵심 용어
  • Key: 검색 기준
  • Value: 실제 저장할 데이터
  • Hash Function: key를 숫자로 변환, 테이블 크기에 맞게 조정
  • Bucket: 실제로 데이터가 들어가는 칸, 배열의 한 슬롯
  • Collsion: 서로 다른 key가 같은 bucket으로 가는 경우 발생하는 충돌
• [[ modulo ]] 연산은 Key 값을 테이블 크기로 나누어 나머지를 인덱스로 변환하는 기법

Javascript's Hash Table

Object

• JS에서 가장 오래된 해시 기반 구조
• 키는 string, symbol만 가능
• V8 엔진의 경우 [[ Hidden Class ]] 지원으로 해시 기반 접근보다 빠를 수 있음

Map

• 모든 타입을 키로 사용 가능
• 삽입 순서 보장
• 프로토타입 이슈 없음
• 키-값 쌍의 빈번한 추가/제거에 관해서는 객체보다 성능이 좋다고 함

Set

• 내부적으로 해시 기반
• 값의 존재 여부 체크에 최적

WeakMap, WeakSet

• 키는 객체만 가능
• 약한 참조라서 GC에 의해 자동 정리
• 순회 불가