여기서 나누기를 사용한 해싱에 대해 설명합니다. 이를 위해 해시 함수 −
를 사용합니다.ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚
이 해시 함수를 사용하기 위해 배열 A[0, … m – 1]을 유지합니다. 배열의 각 요소는 연결 목록의 헤드에 대한 포인터입니다. 연결 리스트 Li는 배열 요소 A[i]를 가리키며 h(x) =i가 되도록 모든 요소 x를 보유합니다. 이 기술은 연결에 의한 해싱으로 알려져 있습니다.
이러한 해시 테이블에서 요소 x를 늘리려면 O(1) 시간이 걸립니다. 인덱스 i =h(x)를 계산합니다. 그런 다음 목록 Li에 x를 추가하거나 앞에 추가합니다. 요소를 검색하거나 삭제하려는 경우 해당 프로세스가 그리 쉽지 않습니다. 인덱스 i =h(x)를 찾아야 합니다. 그런 다음 목록 Li를 탐색합니다. 원하는 값에 도달하거나 목록이 소진될 때까지. 이 작업은 목록 Li의 크기에 해당하는 시간이 걸립니다. . 세트 S에 0, m, 2m, 3m, ….., nm 요소가 있는 경우 L0에 저장된 모든 요소는 검색 및 삭제에 선형 시간이 걸립니다.
이러한 상황은 매우 드뭅니다. 예를 들어, S가 보편적 집합 U에 균일하고 독립적으로 분포되어 있고 u가 m의 배수이면 각 목록의 예상 크기 Li n/m에 불과합니다. 이 경우 검색 및 삭제가 O 걸립니다. (1 + α) 시간. 언급된 시나리오를 피하려면 m을 현명하게 선택해야 합니다. 일반적으로 m을 2의 거듭제곱으로 사용하지 않습니다. m을 2의 거듭제곱에 너무 가깝지 않은 소수로 사용하는 것이 좋습니다.