Chaining là gì?

Chaining là một phương pháp để giải quyết xung đột băm (collision) trong bảng băm (hash table). Trong phương pháp này bảng băm (hash table) sẽ là một mảng các danh sách được liên kết (linked list). Mỗi chỉ mục (index) có danh sách liên kết riêng của nó. Tất cả các khóa (key) ánh xạ (map) tới cùng một chỉ mục (index) sẽ được lưu trữ dưới dạng các nút (node) của danh sách được liên kết tại chỉ mục đó.

Dưới đây là một số ưu điểm của phương pháp chaining:

• Thông qua chaining, việc chèn trong bảng băm luôn xảy ra ở O(1) vì danh sách liên kết cho phép chèn có thời gian không đổi (constant time).
• Bảng băm có thể phát triển vô hạn miễn là có đủ không gian (space).
• Một bảng băm sử dụng chaining sẽ không bao giờ cần phải thay đổi kích thước.

Trong lập trình hướng đối tượng (object-oriented programming), chuỗi (chaining) đề cập đến chuỗi phương thức (method chaining).