자료구조와 알고리즘 - 해시 테이블

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. 해시 테이블이란?

• 해시테이블은 한정된 배열 공간에 key를 index로 변환하여 값을 넣음
• key와 value를 받아 Hasing하여 나온 index에 값을 저장하는 선형 자료구조
• 삽입은 O(1)
• 키를 알고 있으면, 삭제, 탐색도 O(1)로 수행
• Bucket: 각 테이블에 해당하는 index
• 테이블의 각 요소는 key, value를 둘 다 저장
• 빠르게 값을 찾아야하는 경우, 해시 테이블을 사용하기
• JavaScript에서의 Array, Object가 Hash Table
• JavaScript Map의 경우도 Hash Table
  • 다양한 자료형도 key로써 사용 가능
• JavaScript Set의 경우도 hash Table
  • key, value가 동일하게 저장되는 방식
  • 일종의 집합 연산
  • 중복된 내용을 전부 제거시킬 수 있음

2. 해시 함수

• 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
• ex) 문자열 -> 각 문자에 맞는 아스키 코드로 변환
• 문제점
  • Hash Collision(해시충돌): 결과가 동일하여 겹치는 경우

3. Hash Collision

• 선형 탐사법
  • 충돌 발생시, 옆으로 한 칸 이동
  • 단순함
  • 특정 영역에 데이터가 몰릴 수 있음
  • 충돌이 발생하지 않을 때까지 이동
  • 최악의 경우 탐색에 선형 시간이 걸릴 수 있음
• 제곱 탐사법
  • 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
  • 데이터가 몰리지 않음
• 이중 해싱
  • 충돌이 발생 시, 다른 해시 함수를 이용
• 분리 연결법
  • 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면, 버킷의 리스트에 값을 추가
  • 하나의 버킷이 무한정 늘어날 수 있음

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript