C++: MÔ TẢ BÀI TOÁN

Hãy viết chương trình thực hiện thao tác “Nhập xuất cơ bản một bảng băm chứa các số nguyên” với những yêu cầu sau:

- Giải quyết xung đột bằng phương pháp băm lại. Thường cài đặt bảng băm bằng ARRAY
- Nếu băm bị xung đột thì băm lại. Quá trình băm lại diễn ra cho đến khi không còn xung đột nữa. Các phép băm lại (rehash function) thường sẽ chọn địa chỉ khác cho các phần tử.

- PHƯƠNG PHÁP DÒ BẬC HAI
Hàm băm lại của phương pháp dò bậc hai là truy xuất các địa chỉ cách bậc 2
    fj(key) = ( f(key) + j^2 ) % M, với f(key) là hàm băm chính của bảng băm
+ Khi thêm 1 nút có khóa key, f(key) sẽ xác định địa chỉ i:
+ Nếu chưa bị xung đột thì thêm nút mới tại địa chỉ d này.
+ Nếu bị xung đột thì băm lại lần 1, f1 sẽ xét địa chỉ  (i+ 1^2)%M,
+ Nếu lại bị xung đột thì băm lại lần 2, f2 xét địa chỉ cách (i+ 2^2)%M, ...
+ Tiếp tục cho đến khi tìm được địa chỉ trống để thêm vào.
 

LƯU Ý: 1 GIẢI PHÁP TRIỆT ĐỂ CẦN PHẢI XỬ LÝ NHỮNG TRƯỜNG HỢP ĐẶC BIỆT SAU:

Vòng lặp băm lại bị vô tận,  số lần băm lại lớn quá dẫn đến i*i quá lớn và bị tràn số (vượt khỏi miền giá trị của int)

1. Nhận biết băm lại vô tận: băm lại hoài mà chỉ trả về cùng 1 giá trị, hoặc là quay lại những giá trị trước đó (tức có 1 chu kỳ quanh đi quẩn lại 1 số giá trị nào đó), hoặc là đã thăm qua hết các địa chỉ  hoặc băm lại M lần rồi mà vẫn không thêm được. Nhiều tài liệu tham khảo ghi là "hàm insert tiến hành probing và dừng khi i==M)

2. Khi bị lặp vô tận thì chỉ cần kết luận "quá trình băm lại bị lặp vô tận và chọn phương án xử lý "

Cách 1: ghi error " không thêm được"

Cách 2: thêm theo 1 quy luật nào đó để có thể tìm lại được. Ví dụ, thêm vào vị trí trống đầu tiên từ cuối mảng/hoặc đầu mảng, nhưng cẩn thận là khi tìm thì xử lý sao cho ko tốn kém nhiều chi phí

Cách 3-cách làm phổ biến nhất trong thực tế: tạo bảng băm mới, add lại hết các số cũ sau đó xóa bảng cũ đi, xem như là thay đổi bảng băm

Tuy nhiên, do bài này chỉ ở mức level1  nên cô không yêu cầu xử lý  trường hợp trên, sv không cần xử lý vẫn pass được các test.

Những bài tập khác của Bảng băm là có yêu cầu, nhưng chưa cho SV làm

INPUT

 - Số nguyên đầu tiên là n (0<=n<=10000). Đây là số lượng phần tử sẽ được lưu trữ vào bảng băm

- n số nguyên tiếp theo là các (giá trị) khóa của các phần tử được lưu vào bảng băm, có giá trị không quá 2 tỷ.

 **SV không cần kiểm tra điều kiện nhập

OUTPUT

- Xuất theo template

- Khi bảng băm bị đầy thì xuất thông báo cout<<"\nBang bam bi day, khong them duoc";
Template:
/*###Begin banned keyword - each of the following line if appear in code will raise error. regex supported
define
include
using
->
###End banned keyword*/

#include <iostream>
#include <cstring>
#include <string>
#define M 10		// M là số nút có trên bảng băm, đủ để chứa các nút nhập vào bảng băm
#define NULLKEY -1
using namespace std;

//###INSERT CODE HERE -

int main()
{
    Hash H;
    initHash(H);

    int n,x;cin>>n; // n la so luong gia tri can phai luu tru
    for (int i = 1; i<=n;i++)
    {
        cin>>x;
        cout<<"\nInsert "<<x;
        insertHash(H,x); // them 1 gia tri du lieu vao bang bam
    }
    cout<<"\nCreated Hash:"<<endl;
    traverseAllHash(H);

    return 0;
}

Exam input:
9
44
9
27
57
36
17
22
73
91

Exam output:
Insert 44
Insert 9
Insert 27
Insert 57
Insert 36
Insert 17
Insert 22
Insert 73
Insert 91
Created Hash:
0
1 --> 17
2 --> 22
3 --> 73
4 --> 44
5 --> 91
6 --> 36
7 --> 27
8 --> 57
9 --> 9