알고리즘. 해시 충돌 알아보기

최대 1 분 소요

🌟 해시 충돌

예시로, 1000번까지 데이터 리스트를 생성하고 blog란 단어에 해시 함수를 적용하여 111이란 색인이 생성되면 리스트 111번에 blog 단어를 넣었을 때, 다른 단어를 넣었는데 111이란 색인이 나오면 동일한 색인을 가진다는 문제가 있다.

같은 위치를 공유할 때 문제가 일어나는 듯!

한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는 방법. 모든 자료를 해시테이블에 담는다.

해당 버킷에 데이터가 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현!

링크드 리스트를 이용하는 방식이다.

버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이다. 구현 방법이 다양한데, 가장 간단한 건 Linear probing!

index에 대해 충돌이 발생했을 때, index 뒤에 있는 버킷 중 빈 버킷을 찾아서 데이터를 넣는다.

이외에도 리스크 크기를 재배열 하거나, 해시테이블을 확장하거나, 해시의 비트수를 늘이는 방법도 있다! 자세한 건 아래 블로그…

YJUN IT BLOG