Hash Table

• Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.
• 특정한 값을 찾는데 고유의 인덱스로 접근하므로 평균적으로 시간복잡도가 O(1)
  • 충돌이 발생할 수 있어 항상 O(1)은 아니다
• 인덱스로 지정되는 key 값이 불규칙적

  Key 값 → 특별한 알고리즘 → 고유한 숫자 for 인덱스

Hash function

• 특별한 알고리즘
• Hash function에 의해 반환된 데이터의 고유 숫자 값을 hashcode라고 한다.
• 저장되는 값들의 key 값을 hash function을 통해 작은 범위의 값들로 변경

Collision

• 서로 다른 두 개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게 된다.

좋은 Hash function 이란?

• collision이 많아질 수록 탐색에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워진다.
• collision을 최소화한다.
• Collision 발생 시 대응 방법들을 마련한다.

Collision 해결

(1) Open Address (개방주소법)

• 충돌 발생 → 다른 해시 버킷에 해당 자료를 삽입
• 버킷 = 데이터 저장 공간
• 최악의 경우 비어 있는 저장 공간을 찾다가 탐색을 시작한 위치로 돌아올 수 있다
• 비어 있는 저장 공간 탐색 방법
  • Linear probing : 순차적으로 비어 있는 저장공간을 찾을 때까지 탐색하는 방법
  • Quadratic probing : 2차 함수를 이용해 탐색할 위치를 찾는 방법
  • Double hashing probing : 2차 해시 함수를 이용해 새로운 주소를 할당. 많은 연산량을 요구

(2) separate chaining(분리 연결법)

• Open address 방식보다 더 빠름
  • 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다.
• 분리 연결법 방법
  • Linked-list
    • index에 노드가 6개 이하인 경우
    • 버킷 -> 링크드 리스트 : 버킷이 링크드 리스트를 가리키고 있는 형태
    • 충돌이 발생하면 해당 버킷의 링크드 리스트에 노드 추가하여 데이터를 삽입한다.
  • Red-Black Tree
    • index에 노드가 8개 이상인 경우
    • 링크드 리스트 대신 트리를 사용하는 방식
  • 기준이 6개, 8개인 이유
    • 변경하는데 소요되는 비용을 줄이기 위함
• 보조 해시 함수
  • key의 해시 값을 변형하여 해시 충돌을 줄이는 것
  • Separate chaining 방식과 함께 사용

(3) 동적 확장(resize)

• 저장 공간이 일정 수준 채워지면 Separating Chaining의 경우 성능 향을 위해, Open addressing의 경우 배열 크기 확장을 위해 Resizing

(4) Open Address VS Separate chaining

• 데이터가 적은 경우 연속된 공간에 데이터를 저장하는 Open Address이 캐시 효율이 높아 성능이 더 좋다

  Java HashMap에서 사용하는 방식은 Separate Channing이다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문이다. 게다가 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다.
  https://d2.naver.com/helloworld/831311

Hash Table VS Hash Map

• Key - value 구조 및 key에 대한 hash로 value 관리하는 것은 동일
• Hash Table
  • 동기화 지원
  • 멀티 스레드 환경에서 사용하기 좋다.
  • null 값 허용 안함
• Hash Map
  • 동기화 미지원
  • 단일 스레드 환경에서 사용하기 좋은 자료 구조
  • null 값 허용