[알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing)
오늘은 오픈 어드레싱 중에서 선형 프로빙(linear probing)에 대해 알아보겠습니다. 해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있습니다. 이를 충돌(collision)이라고 부릅니다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있습니다. 오픈 어드레싱은 충돌을 피하기 위해 key를 해쉬 테이블에 직접 저장하는 방법입니다. 오픈 어드레싱에는 선형 프로빙(linear probing), 이차식 프로빙(quadratic probing), 이중 해싱(double hashing)이 있습니다. 그 중에서 선형 프로빙(linear probing)은 hash function을 수행한 결과값은 동일할 경우 뒤로 한 칸씩 미루면서..
알고리즘
2021. 12. 21. 20:52
