Hash

Hash

데이터의 효율적 관리를 위해 고정된 길이의 데이터로 매핑 하는 것

하지만 아무리 좋은 해시 함수를 적용해도 결국 Collision 현상은 피할 수 없다.

하지만 역시 해시 테이블은 적은 자원으로 데이터를 효율적으로 관리 가능

시간 복잡도 O(1)

Collision 문제

체이닝

• 해당 값에 LinkedList 형식으로 노드를 추가해 가는 방식
  • Memory 문제

Open Addressing

• 해당 주소에 이미 Data가 있다면 다른 값에 저장
  • 만약 3001번지에 Data가 있다면 3002번지에 저장
  • 3003, 3004로 이동

선형 탐사

• 정해진 고정 폭으로 이동해서 Open Addressing 을 적용한다.

제곱 탐사

• 정해진 고정 제곱 수로 이동해서 Open Addressing 을 적용한다.

하지만 이러한 방법 모두 결국 HashMap의 성능을 떨어트릴 가능성이 높음…

Hash buket 동적 확장

• 그냥 Hash buket이 충분이 크면 된다!
• 대게 load factor 70% ~ 80% 차기 시작한다면 buket의 크기를 확장 하는 전략을 사용
  • load factor : 할당 된 키의 개수 / 해시 버킷의 크기
• 동적 확장시 모든 데이터들은 리해싱 작업을 거친다.