[알고리즘] 해시테이블_구현

220617 작성

<본 블로그는 Abdul Bari님의 유튜브를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=mFY0J5W8Udk 

 

 

1. hash function

h(x) = x %  size hash table

충돌 발생!

 

 

2. collision

- open hasing

chaining

: 동일한 해쉬 함수 사용하여 키 매핑할 대!

: 새 체인을 추가

: 체인 내부의 인덱스 생성

 

- closed hashing

linear probing

: 충돌하면 그다음 여유 공간에 넣기

: 새로운 해시 함수 정의

h'(x) = [h(x) + h(i)] % size

f(i) = i

: 보수적인 위치에서 요소 찾기!!

: 빈 공간에 도달할 때가지 검색

: 클러스터링 문제 야기

 

quadratic probing (2차 탐색)

: 클러스터링 문제 해결

: 새로운 해시 함수 정의

h'(x) = [h(x) + h(i)] % size

but f(i) = i^2