해시 테이블

• key와 value로 이루어진 자료 구조
• 매우 빠른 삽입, 삭제, 탐색 연산을 제공함
  • 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문
  • key값에 해시 함수를 적용해 배열의 고유한 index를 생성!
    • index를 활용해 값을 저장/검색

해시 함수

• 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

• 매핑 전 데이터의 값(key), 매핑 후 데이터의 값(hash value), 매핑하는 과정(hashing)

• 중요한 점은 고유한 인덱스를 생성하는 것! → 중복된 인덱스가 발생하는 것을 **충돌(Collision)**이라 한다.

  • 해시 충돌의 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가함

  <aside> ☝🏻

  해시 충돌이 발생할 가능성이 있는 해시테이블 사용 이유?

  • 적은 리소스로 많은 데이터를 효율적으로 관리
  • 해시 함수는 언제나 동일한 해시값 리턴 → 즉, index만 알게되면 해시테이블의 크기에 상관없이 데이터에 빠르게 접근 가능!
  • 삽입, 삭제, 검색 모두 시간 복잡도가 O(1) </aside>

• 해시 함수 종류

  • division method
    • 나눗셈법 → 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 반환 ( m은 대개 소수 사용, 특히 2의 제곱수와 거리가 먼 소수 사용하는 것이 좋음 )
    • 단점
      • 충돌 많음
      • 해시테이블 크기가 고정
  • universal hash
    • 여러 개의 해시함수를 만들고, 이 해시함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법
    • 서로 다른 해시함수가 서로 다른 해시값을 만들어내기 때문에 같은 공간에 매핑할 확률을 줄이는 것이 목적

충돌 회피 방법(collision resolution method)

• 분리 연결법 (separate chaining)

  

  • 충돌이 발생하면 기존 값과 새로운 값을 연결리스트로 연결하는 방법
  • 흔히 해시 테이블이라고 하면 이 방식을 뜻함 (Java HashMap)
  • 장점
    • 충돌을 대비해서 공간을 준비해놓을 필요 없음
  • 단점
    • 같은 hash에 많은 값이 연결되면 검색 효율 떨어짐

• 개방 주소법 (open addressing)

  

  • 충돌이 발생하면 빈 공간을 찾아 저장

    

    • Linear Probing : 현재의 index로부터 고정폭 만큼씩 이동하여 빈 공간 검색/저장
    • Quadratic Probing : 해시의 저장 순서 폭을 제곱으로 검색/저장
    • Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식. 다른 방법들보다 많은 연산 필요

  • 전체 슬롯의 개수 이상은 저장 불가 (개별 체이닝은 무한정 저장 가능)

  • 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음

<aside> ❓ Java 에서의 HashMap & HashTable 차이?

• 보조 해시 함수
  • HashMap은 보조 해시함수 사용
  • HashTable에 비해 해시 충돌이 덜 발생할 수 있어 상대적으로 성능상 이점 있음
• 동기화 지원 여부
  • 해시 테이블은 동기화 지원 O , 해시맵은 동기화 지원 X
  • 병렬 처리 & 자원의 동기화 ⇒ 해시테이블, 그 외는 해시맵 사용! </aside>