Thay vì duy trì một danh sách đơn với một nút dẫn đầu head chúng ta lưu M danh sách với M nút dẫn đầu danh sách và chúng được khởi động như sau:

Bây giờ ta kết hợp một số thủ tục tìm kiếm trên danh sách cùng với một hàm băm. Ví dụ, listinsert(v, heads[v mod M]) có thể được dùng để thêm vào bảng và t:= listsearch(v, heads[v mod M]) có thể được dùng để tìm thấy mẩu tin đầu tiên với khoá v và tiếp tục gọi t:= listsearch(v,t) cho tới khi t= z để tìm các mẩu tin kế tiếp có khoá v.

Ví dụ các khoá được chèn liên tục vào một bảng khởi tạo trống bằng cách dùng hàm băm như hình 1 ở dưới:

Ta sẽ được kết quả như trong hình 2:

Phương pháp này được gọi là xích ngăn cách (separate chaining) bởi vì các mẩu tin xung đột được “xích” cả lại trong các danh sách rời nhau.

Hiển nhiên, thời gian cho một thao tác tìm kiếm phụ thuộc vào độ dài của danh sách và các vị trí liên quan của các khoá trong chúng. Các danh sách cũng có thể lưu trữ không thứ tự, việc duy trì các danh sách được sắp xếp sẽ không quan trọng cho áp dụng này bởi vì các danh sách khá ngắn.

Với một lần “tìm kiếm không thành công” (tìm kiếm một mẩu tin với một khoá không có trong bảng), chúng ta có thể giả sử rằng hàm băm làm cho mỗi danh sách trong M danh sách có khả năng được truy xuất như nhau và tìm kiếm tuần tự trong mỗi danh sách chỉ duyệt một nửa danh sách về mặt trung bình. Độ dài trung bình của danh sách được kiểm tra (không kể z) đối với tìm không thành công trong ví dụ này là (0+4+2+2+0+4+0+2+2+1+0)/11… 1.55. Đây là thời gian trung bình cho một tìm kiếm không thành công khi mà các danh sách không được sắp thứ tự; khi sắp thứ tự danh sách chúng ta có thể giảm một nửa thời gian.

Với mỗi lần “tìm kiếm không thành công”, chúng ta sẽ giả sử rằng mỗi mẩu tin đều có khả năng được tìm thấy như nhau: bảy khóa sẽ được tìm thấy khi phần tử đầu tiên của mỗi danh sách được kiểm tra, sáu khoá sẽ được tìm thấy khi phần tử thứ hai được kiểm tra, v.v…, vì vậy trung bình là (7.1+6.2+2.3+2.4)/17=1.94 (sự tính toán này giả sử rằng các khoá bằng nhau được phân biệt bởi một chỉ danh duy nhất hay một cách nào đó, và chương trình tìm kiếm được sửa đổi thích hợp để có thể tìm kiếm cho mỗi khoá riêng lẻ).

*** Xích ngăn cách thu hẹp số lần so sánh của tìm kiếm tuần tự xuống M lần (về mặt trung bình) và dùng bộ nhớ trợ giúp cho M liên kết.

Vì mỗi giá trị trong M giá trị băm và “có khả năng như nhau” nên do thiết kế của hàm băm nếu N khoá trong bảng lớn hơn M nhiều thì một xấp xỉ tốt độ dài trung bình của các danh sách là N/M.

Cài đặt nói trên dùng một bảng băm của các liên kết tới các nút dẫn đầu của các danh sách. Một phương pháp khác để lưu M nút dẫn đầu danh sách là khử bỏ các nút dẫn đầu và sửa heads thành một bảng các liên kết tới các khoá đầu tiên trong các danh sách. Điều này sẽ dẫn đến một vài phức tạp trong thuật toán. Ví dụ việc thêm một mẩu tin mới vào đầu của một danh sách sẽ khác với thêm vào vị trí khác của danh sách, vì nó bao gồm sự sửa đổi một đầu vào trong một bảng các liên kết. Mặc dù các cài đặt này tiết kiệm không gian lưu trữ trong một số tình huống, nhưng M thường đủ nhỏ so với N nên sự quy ước dùng các nút trợ giúp dẫn đầu danh sách có lẽ được thừa nhận.

Trong một cài đặt xích ngăn cách, M thường được chọn tương đối nhỏ để không dùng một khối lớn bộ nhớ liên tục. Nhưng có lẽ tốt nhất là chọn M đủ lớn sao cho các danh sách đủ ngắn để sự tìm kiếm tuần tự trở nên hiệu quả. Theo kinh nghiệm thì người ta có thể chọn M khoảng một phần mười số các khoá trong bảng để mỗi danh sách chứa khoảng 10 khoá. Một trong những ưu điểm của xích ngăn cách là quyết định này không nguy hại: nếu có nhiều khoá hơn mong đợi thì các quá trình tìm kiếm sẽ dài hơn một ít, nếu các khoá ít hơn thì có thể dùng phí một ít không gian lưu trữ.

Nếu bộ nhớ thực sự là một tài nguyên giới hạn, việc chọn M thích hợp sẽ sự thực hiện được M lần.

2. Dò tuyến tính

nếu số phần tử được đặt trong bảng băm có thể được ước lượng trước và đủ bộ nhớ liên tục để lưu tất cả cá khoá thì có lẽ không đáng để dùng các liên kết trong bảng băm. Nhiều phương pháp đề nghị lưu trữ n mẩu tin trong một bảng kích thước MN, dựoc voà các nơi trống trong bảng để giải quyết tranh chấp. Các phương pháp như thế được gọi là các phương pháp băm địa chỉ mở (open - addressing).

Phương pháp địa chỉ mở đơn giản nhất được là dò tuyến tính (linear probing): khi có một sự tranh chấp (khi chúng ta băm đến một nơi trong bảng mà đã bị chiếm và khóa ở nơi đó không bằng với khoá tìm kiếm) thì dò đến vị trí kế tiếp trong bảng, nghĩa là so sánh khoá trong mẩu tin đó với khoá tìm kiếm. Có ba khả năng trong quá trình dò: nếu các khoá bằng nhau thì quá trình tìm kết thúc thành công; nếu không có mẩu tin ở đó thì quá trình tìm kết thúc không thành công; trường hợp ngược lại dò đến vị trí kế tiếp, tiếp tục tới khi hoặc khoá tìm kiếm được thấy hoặc có một vị trí chưa dùng trong bảng. Nếu một mẩu tin chứa khoá tìm kiếm được chèn vào sau một quá trình tìm kiếm không thành công thì có thể dễ dàng đặt vào vị trí trống của bảng nơi mà quá trình tìm kết thúc. Phương pháp này dễ dàng được cài đặt như sau:

Dò tuyến tính đòi hỏi một giá trị khác đặc biệt để đánh dấu một vị trí trống trong bảng: chương trình trên dùng maxint cho mục đích đó. Sự tính toán tương ứng x:=(x+1) mod M nhằm để kiểm tra vị trí kế tiếp (quay ngược trở lại từ đầu khi đến cuối của bảng). Chú ý rằng chương trình không kiểm tra bảng có khả năng bị lắp đầy hay không.

Sự cài đặt hashsearch tương tự như hashinsert: chỉ cần thêm điều kiện “a[x].key <>v” vào vòng lặp while và xoá lệnh lưu trữ v liền sau đó. Khi gọi thủ tục này, để biết quá trình tìm kiếm thành công hay không, ta kiểm tra xem giá trị trả về là v (thành công), hay là maxint (không thành công). Các quy ước khác cũng có thể được dùng, chẳng hạn như hashsearch có thể trả về M tìm kiếm không thành công. Với một số lý do, phương pháp địa chỉ mở sẽ không thích hợp nếu phải xử lý một số lượng lớn các mẩu tin có khoá bằng nhau, nhưng hashsearch có thể sửa lại dễ dàng để xử lý trường hợp các khoá bằng nhau và mỗi khoá có một chỉ danh duy nhất.

Kích thước bảng cho việc dò tính thì lớn hơn so với xích ngăn cách, vì chúng ta phải có MN, nhưng tổng số lượng bộ nhớ cần dùng lại nhỏ hơn bởi vì không sử dụng các liên kết.

*** Về mặt trung bình, dò tuyến tính sử dụng ít hơn 5 lần dò đối với một bảng băm mà chưa đầy đến hai phần ba.

Công thức chính xác cho số lần dò trung bình, tính theo “hệ số nạp” a= N/M của bảng băm, là ½+ 1/[2(1-a)2 cho trường hợp tìm kiếm không thành công và ½ + 1/[2(1-a)] cho trường hợp tìm kiếm thành công. Do đó nếu chọn a=2/3 chúng ta có năm lần dò cho trường hợp tìm kiếm không thành công và hai lần cho trường hợp thành công. Tìm kiếm không thành công luôn đắt giá hơn tìm kiếm thành công và một lần tìm kiếm thành công sẽ yêu cầu ít hơn năm lần dò đến khi bảng đầy khoảng 90%. Khia bảng gần đầy (a gần bằng 1) những số này trở nên rất lớn; Điều này không nên cho xảy ra trong thực tế như chúng ta sẽ thảo luận sau này.

School@net