Quadratic probing là gì?

Dò bậc hai (quadratic probing) là một phương pháp của băm địa chỉ mở (open addressing) trong lập trình máy tính để giải quyết xung đột băm (hash collision) trong bảng băm (hash table). Trong đó chúng ta tìm kiếm slot thứ i² trong lần lặp thứ i nếu giá trị băm (hash value) x đã cho xung đột trong bảng băm.

Gọi hash(x) là chỉ số (index) của slot được tính bằng hàm băm (hash function).

• Nếu hash(x) % S đầy, thì chúng ta thử (hash (x) + 1 * 1) % S.
• Nếu (hash (x) + 1 * 1) % S cũng đầy, thì chúng ta thử (hash (x) + 2 * 2) % S.
• Nếu (hash (x) + 2 * 2) % S cũng đầy, thì chúng ta thử (hash (x) + 2 * 2) % S.
• Quá trình này được lặp lại cho tất cả các giá trị của i cho đến khi tìm thấy một slot trống.

Ví dụ: Chúng ta hãy coi một hàm băm đơn giản là "key mod 7" và chuỗi các khóa là 50, 700, 76, 85, 92, 73, 101.

Dò bậc hai (quadratic probing) có thể là một thuật toán hiệu quả hơn trong băm địa chỉ mở, vì nó tránh tốt hơn vấn đề phân cụm (clustering) có thể xảy ra với dò tuyến tính (linear probing).

Dưới đây là code việc triển khai (implementation) phương pháp trên trong C++:

// C++ implementation of
// the Quadratic Probing
#include 
using namespace std;
 
// Function to print an array
void printArray(int arr[], int n)
{
    // Iterating and printing the array
    for (int i = 0; i 

Output:

700 50 85 73 101 92 76