Primary clustering là gì?

Khi đề cập đến đụng độ (collision) trong bảng băm (hash table), một vấn đề tiềm ẩn với dò tuyến tính (linear probing) là phân cụm (clustering), trong đó các đụng độ được giải quyết bằng dò tuyến tính khiến các nhóm vị trí liên tiếp trong bảng băm bị chiếm dụng. Mỗi nhóm được gọi là một cụm (cluster) và hiện tượng được gọi là phân cụm sơ cấp (primary clustering).

Phân cụm sơ cấp (primary clustering) là xu hướng của một lược đồ giải quyết đụng độ (collision resolution scheme) như dò tuyến tính (linear probing) để tạo ra các dải dài slot được lấp đầy gần vị trí băm (hash) của các khóa (key). Nếu chỉ mục băm chính (hash index) là x, các lần dò (probe) tiếp theo sẽ chuyển đến x + 1, x + 2, x + 3, v.v., điều này dẫn đến phân cụm sơ cấp (primary clustering).