Hash Table
- 고정된 크기의 배열을 만든다
- 해시 함수를 이용해서 Key를 원하는 범위의 자연수로 바꾼다.
- 해시 함수 결과 값 인덱스에 key-value 쌍을 저장한다.
문제점: 같은 인덱스에 서로다른 (key,value)가 충돌(Collision)이 일어날 수 있다.
Hash Table 종류
- 체이닝(Chaning)
- 충돌 발생 시 그림과 같이 연결 리스트로 연결(link)하는 방식
- 가장 전통적인 방식으로, 흔히 해시 테이블이라고 하면 바로 이 방식을 말한다.
- 무한정 저장할 수 있다.
- 오픈 어드레싱(Open Addressing)
- 충돌 발생 시 그림과 같이 탐사를 통해 빈 공간을 찾아나서는 방식
- 전체 슬롯의 개수 이상은 저장할 수 없으며, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다
출처 : ttps://namu.wiki/w/%ED%95%B4%EC%8B%9C
