Hash Table

Hash Table이 뭐에요?

해시 테이블은 어떤 특정 값을 받으면 해시 함수를 통해서 나온 index에 저장하는 자료구조 이다.

직접주소테이블은 공간낭비가 심함

해시 테이블은 반면 공간낭비가 적다

해시의 출동

충돌의 해결법

1. 개방 주소법
   해시 충돌 발생시 새로운 주소를 탐사 후 비어있는곳에 입력

   1. 선형 탐사법
   (일차 군집화문제 발생)
   2. 제곱 탐사법
   (이차 군집화문제 발생)
   3. 이중 해싱

2. 분리 연결법
   해쉬 테이블 버킷에 값이 아니라 링크드리스트 , 트리를 사용

테이블 크기 재할당(Resizing)