Bài viết sưu tầm

Các thao tác trên tổ chức tệp băm

Tìm kiếm một bản ghi

          Giả sử cần tìm một bản ghi nào đó có giá trị khóa là x (chú ý rằng trong trường hợp khóa có nhiều hơn một trường thì thứ tự của các trường trong khóa phải là cố định). Để tìm bản ghi có khóa là x, trước hết tính hàm băm h(x). Giả sử h(x) = i, i sẽ là địa chỉ băm của cụm i. Trong bảng chỉ dẫn cụm cho biết con trỏ tới khối đầu tiên (nếu có). Tìm trong khối này xem liệu có bản ghi có khóa x hay không, theo con trỏ ở đầu khối tìm tiếp tới các khối tiếp theo cho tới khi tìm được bản ghi mong muốn hoặc tới khối cuối cùng của cụm i mà không có bản ghi đó.

Thêm  một bản ghi

          Giả sử cần thêm một bản ghi có khóa là x vào tệp, thủ tục được thực hiện giống như tìm kiếm một bản ghi.

nếu trong tệp đã có một bản ghi trùng khóa x, chứng tỏ bản ghi mới là sai (vì khóa là duy nhất)

nếu không có bản ghi trùng khóa, bản ghi có khóa x được thêm vào đầu tiên trong cụm còn chỗ trống. Nếu không còn chỗ trống nào trong mọi khối của cụm, thì phải tạo thêm một khối mới, con trỏ null của khối cuối cùng được trỏ sang khối mới này. Trong trường hợp này bản ghi mới sẽ là bản ghi đầu tiên của khối vừa được thiết lập và khối này trở thành khối cuối cùng.

Xóa một bản ghi

          Để xóa một bản ghi với khóa x, sử dụng thủ tục tìm bản ghi. Nếu bản ghi thuộc một khối nào đó có nhiều bản ghi khác, khi đó bản ghi có khóa x được loại bỏ, nếu bản ghi đó là duy nhất trong khối, khi đó sẽ đồng thời với việc giải phóng khối khỏi cụm chứa khối.

Sửa một bản ghi

          Giả sử cần sửa một hoặc một số trường của một bản ghi có khóa x. Nếu trường cần sửa có tham gia trong khóa x, việc sửa chữa sẽ loại bỏ bản ghi này và thêm vào một bản ghi mới cho tệp (vì rằng khi sửa khóa bản ghi có thể lại thuộc vào một cụm khác). Thủ tục thêm, xóa giống như trên. Nếu trường cần sửa không thuộc khóa, sau khi sử dụng thủ tục tìm bản ghi cần thiết, tiến hành sửa giá trị các trường, nếu bản ghi không tồn tại xem như có lỗi.