Ở đây chúng ta sẽ thảo luận về phép băm với phép chia. Đối với điều này, chúng tôi sử dụng hàm băm -
ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚
Để sử dụng hàm băm này, chúng ta duy trì một mảng A [0,… m - 1]. Trong đó mỗi phần tử của mảng là một con trỏ đến phần đầu của danh sách được liên kết. Danh sách liên kết Li được trỏ tới phần tử mảng A [i] chứa tất cả các phần tử x sao cho h (x) =i. Kỹ thuật này được gọi là băm bằng cách chuỗi.
Trong bảng băm như vậy, nếu chúng ta muốn tăng một phần tử x, điều này sẽ mất O (1) thời gian. chúng tôi tính chỉ số i =h (x). Sau đó thêm hoặc thêm x vào danh sách Li. Nếu chúng ta muốn tìm kiếm hoặc xóa một phần tử, quá trình đó không dễ dàng như vậy. Chúng ta phải tìm chỉ số i =h (x). Sau đó đi ngang qua danh sách Li. Cho đến khi chúng tôi đạt được giá trị mong muốn hoặc danh sách đã hết. Thao tác này cần thời gian tương ứng với kích thước của danh sách L i . Nếu tập hợp S của chúng ta có các phần tử 0, m, 2m, 3m,…., Nm, thì tất cả các phần tử được lưu trữ trong L0 sẽ mất thời gian tuyến tính để tìm kiếm và xóa.
Trường hợp này rất hiếm. Ví dụ, nếu S được phân bố đồng nhất và độc lập trong tập phổ quát U và u là bội số của m, thì kích thước dự kiến của mỗi danh sách L i là chỉ n / m. Trong trường hợp này, việc tìm kiếm và xóa sẽ mất O (1 + α) lượng thời gian. Để tránh trường hợp đã đề cập, chúng ta phải chọn m một cách khôn ngoan. nói chung, chúng tôi tránh lấy m là lũy thừa của 2. Nên lấy m là số nguyên tố không quá gần với lũy thừa của 2.