[알고리즘] 해쉬 테이블(hash table) - Quadratic Probing

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다.

이를 충돌(collision)이라고 부른다.

충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다.

 

쿼드라틱 프로빙은 선형 프로빙의 문제를 부분적으로는 해결해준다. 

아래의 글에서 선형프로빙의 단점(문제점)을 확인할 수 있다. 

2021.12.21 - [알고리즘] - [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing)

[알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing)

 

쿼드라틱 프로빙은 hash function을 수행한 결과값이 동일할 경우 k^2만큼 미루면서 빈칸이 존재한다면 그곳에 저장한다. 여기서 k는 처음에 1이고 k^2만큼 미뤘는데 빈칸이 존재하지 않는다면 k가 1씩 증가하게 된다.