[자료구조] Hash

🏔️ Hash

해시 테이블

• key: 고유값
  • hash function의 input
• hash function: key를 고정된 길이의 hash로 변경해주는 역할
  • 서로 다른 key가 hashing 후 같은 값이 나올 수 있음 > 해시 충돌
    • 해시 충돌은 발생확률이 낮을 수록 좋음
    • 해시 충돌이 균등하게 발생하는 것도 중요
      • 모든 키가 같은 해시값이 나오게 되면 데이터 저장시 비효율성도 커지고 보안이 취약해짐
• value: 저장소에 최종적으로 저장되는 값
  • 해시와 매칭되어 저장
• hash table: 해시 함수를 사용하여 키를 해시값으로 매핑, 이 해시값을 주소 삼아 데이터(value)를 key와 함께 저장
  • 데이터가 저장되는 곳은 버킷/슬롯이라 함

장점: key-value의 1:1 매핑 > 삽입/삭제/검색 과정이 평규적으로 O(1)
단점

• 해시 충돌 발생 > 개방 주소법, 체이닝으로 해결
• 순서/관계가 있는 배열에는 부적합
• 공간 효율성이 떨어짐 > 데이터가 저장되기 전에 저장공간을 만들어둬서 빈 공간 생기기도 함
• 해시 함수에 대한 의존도가 높음 > 해시함수가 복잡하면 해쉬를 만드는데 오래 걸림

성능

• 검색: O(N)
• 삽입/삭제: O(N)
• 해쉬 충돌로 인해 worst case 성능은 위와 같음

🏔️ 해시 함수

좋은 해시 함수란, 특정값에 치우치지 않고 해시값을 고르게 만들어내는 것

• Division method
  • 가장 기본적인 해시 함수
  • 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 변환
  • 빠른 연산
  • 해시의 중복 방지를 위해 테이블의 크기 m은 소수인 것이 좋음
  • 하지만 남는 공간이 발생해 메모리상 비효율적
• Multiplication method
  • h(k) = floor(m(kA % 1))
    • k - key
    • m - 해시 테이블 크기
    • A - 0 < A < 1인 실수
• Universal hashing
  • 여러 개의 해시함수를 만들고, 이 해쉬함수의 집합 H에서 무작위로 해시함수를 선택해 해쉬값을 만드는 기법
  • 서로 다른 해시함수가 서로 다른 해시값을 만들어내서 같은 공간에 매핑할 확률을 줄이는 것

🏔️ 충돌이 최대한 적은 해시 함수

좋은 해시 함수의 조건

1. 키를 고르게 분포 시킴
2. 충돌 발생 빈도가 낮음
3. 빠른 연산
4. 단방향성 (해시 값에서 원래값 유추 불가, 안정성)

Chi-squared test를 통해 confidence interval of 0.95~1.05를 내는 해시 함수면 괜찮은 분포

🏔️ 해시 값이 충돌했을 때

Chaining: 저장소에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법

• 장점: 미리 충돌을 대비해서 공간을 더 많이 잡아놓을 필요 없음
• 단점: 같은 해쉬에 자료들이 많이 연결되면 검색 효율이 낮아짐
• 성능 (a = 적재율)
  • 검색/삭제: O(n)
  • 삽입: O(1)

Open Addressing, 개방 주소법: 충돌이 일어나면 비어있는 해시를 찾아 데이터 저장 (hash-value의 1:1 관계 유지)

• 비어있는 해시를 찾는 방법
  • 1. 선형 탐색 (Linear probing): 해시값에서 고정폭으로 건너 뛰면서 비어있는 해시가 나오면 저장
    • h(k, i) = (k + i) % m
    • 문제: 특정 해시값 주변 버킷이 모두 채워져있는 primary clustering 문제에 취약
  • 2. 제곱 탐색 (Quadratic probing): 고정폭이 아닌 1 > 4 > 9 > 16칸 씩 건너 뛰며 빈 칸 찾음
    • h(k, i) = (h'(k) + c1*i + c2*i^2) % m
    • 해시값이 같은 해시들이 들어오면 공간을 많이 확보해야 함
    • secondary clustering에 취약
      • secondary clustering: 새 요소가 항상 같은 경로를 따라 빈 값을 찾아서 이 특정 경로에 따라 찾아지는 버킷들이 늘어남
  • 3. Double hashing: 2개의 해시함수를 이용 + 횟수가 늘어날 때마다 i 값 증가
    • h(k, i) = (h1(k) + i*h2(k)) % m
    • 선형/제곱 탐사에서 발생하는 primary/secondary clustering 해결
    • h2(k) 함수는 해시 테이블 크기 m과 서로소여야 함
      • m - 소수
      • h2(k) - m 보다 작은 정수
    • 성능 (worst case)
      • 검색: O(N)
      • 삽입/삭제: O(1)

🏔️ Java의 Hash

Java - HashTable (Java API), HashMap (Java Collections Framework)

HashTable - Dictionary 클래스 상속, Map 인터페이스 구현

• 원소로 리스트를 갖는 배열
  • 각 리스트는 버킷
• 각 버킷의 인덱스는 key에 hashcode() 메서드를 호출한 값으로 결정
• default capacity: 11
• default loadFactor: 0.75

HashMap - Map 인터페이스 구현

• default capacity: 16
• default load factor: 0.75
• Separate chaining 사용
  • Open Addressing은 데이터 삭제가 비효율적이지만 HashMap에서 remove() 메서드는 빈번하게 호출될 수 있음
  • HashMap에 저장된 key-vale쌍의 개수가 일정 이상으로 늘어나면 일반적으로 Open Addressing이 Separate chaining 보다 느림
    • Open Addressing은 버킷의 밀도가 높아질수록 worst case 빈도가 높아짐
    • Chaining은 해시 충돌이 잘 발생하지 않도록 조정하면 worst case 줄일 수 있음
  • 하나의 해쉬 버킷에 8개 이상의 key-value 쌍이 모이면 링크드리스트에서 트리 구조로 바꿈
    • 6개로 줄면 다시 링크드리스트 구조로 변경
  • key-value 쌍 데이터 개수가 일정 이상이면 해시 버컷의 수를 두배로 늘림 > 해쉬 충돌 확률 줄이기 위해

HashTable vs. HashMap

• Thread-safe
  • HashTable - thread safe
    • HashTable은 동기화 처리 비용 때문에 HashMap에 비해 느림
    • 내부적으로 synchronized되어 있기 때문에 unsynchronized될 수 없음
  • HashMap - thread safe X
    • Map m = Collections.synchronizedMap(new HashMap());로 동기화 가능
• Null 값 허용
  • HashTable
    • key & value에 null 불가
  • HashMap
    • 하나의 null key 허용
    • 다수의 null value 허용
• 속도
  • HashMap이 HashTable보다 빠름
• Traversal
  • HashTable - enumeration & iterator 허용
  • HashMap - iterator만 허용
• Fail-fast: stop normal operation upon condition that may indicate failure
  • does NOT continue a possibly flawed process
  • HashTable - not fail-fast enumerator
  • HashMap - fail-fast iterator
• Inheritance
  • HashTable - Dictionary 클래스 상속 받음
  • HashMap - AbstractMap 클래스 상속 받음

🏔️ Double Hashing의 장단점

장점

• primary/secondary clustering 해결
• probing 중 가장 빠르게 다음 빈칸을 찾음
• 가장 고르게 분포함

단점

• 두개의 해시 함수를 필요로 해서 삽입/검색 연산의 시간복잡도 문제
• 좋은 성능을 내기 위해서는 좋은 해시 함수를 사용해야 함
• 캐쉬 성능이 좋지 않음
• 메모리 사용량이 높음
• 작은 테이블에 적합하지 않음

---

참고:

• [자료구조] Hash의 개념 및 설명
• Difference between HashMap and Hashtable
• Java Hashtable class
• Java HashMap
• Double Hashing | Open Addressing | Hash Tables
• [자료구조] 해시 테이블 (Hash Table)