Hash Table

해시 테이블

• Hash Table: Key와 Value를 1:1로 매핑시켜, Key를 통해 Value값을 도출한다.
• Hash Table은 매우 빠른 평균, 삽입, 삭제, 탐색 연산을 제공한다.

---

해시 함수

• key ---f(key)---> index: f(x)는 해시함수이다. 
• 해시함수의 역할: key값을 작은 범위의 값인hash로 변경한다.
• hash는 저장소에 value와 매핑되어 저장된다.

---

해시함수의 종류와 특징

• 충돌(collision): 서로 다른 여러 key값이 동일한 hash값으로 결과가 되는 경우

      - 충돌을 막기 (최소화 하기) 위한 hash function이 필요하다. 

• open addressing

      - 추가 메모리 공간의 사용 없이, 기존 메모리 공간을 이용한다. 

      - 충돌이 발생했을 때, 빈 공간에 값을 저장한다.

      - linear probing(빈 공간을 찾아 한 칸씩 이동), quadratic probing(제곱으로 뛰면서 빈 칸을 찾음) 등이 대표적이다.

• chaining 

       - 해당 hash에 대한 linked list를 만들어, 노드를 추가하여 value를 삽입

 

• resizing

       - 저장공간이 일정 수준 채워지면(75%), 테이블의 크기를 2배로 증가시킨다.