Bài tập bảng băm phương pháp nối kết trực tiếp năm 2024

Question

[toc] ## Khái niệm - Bảng băm là một CTDL thường được sử dụng như một từ điển: mỗi phần tử trong bảng băm là một cặp <khóa, giá trị>. Ta có thể tìm được giá trị thông qua khóa của nó. - Hàm băm (hash function) là một hàm chuyển đổi các khóa của một tập dữ liệu có kích thước tùy ý thành các giá trị số nguyên thực tế nhỏ để được sử dụng làm chỉ mục (index) trong bảng băm. Các giá trị được trả về bởi hàm băm được gọi là giá trị băm. ![](https://hackmd.io/_uploads/Bk0I7G7_h.png) - Hàm băm đủ tốt: + Tính toán nhanh (không phải là thuật toán) + Các khóa được phân bố đều trong bảng + Ít xảy ra đụng độ + Giải quyết vấn đề băm với các khóa không là số nguyên ## Các dạng hàm băm - **Hàm băm sử dụng Phương pháp chia:** $h(key)=key\%M$ Với $k$ là khóa, $M$ là kích thước của bảng băm. - **Hàm băm sử dụng Phương pháp nhân:** $h(key)=[M*(key*A\%1)]$ Với $A$ là hằng số: $0<A<1$ , $key$ là khóa, $M$ là kích thước của bảng băm. Ví dụ: $key = 12345$ $A = 0.357840$ $M = 100$ $h(12345) = floor[ 100*(12345*0.357840 mod 1)]$ $= floor[ 100 (4417.5348 mod 1) ]$ $= floor[ 100 (0.5348) ]$ $= floor[ 53.48 ]$ $= 53$ ## Các phương pháp giải quyết đụng độ - Khái niệm sự đụng độ: Hiện tượng các khóa khác nhau nhưng băm cùng địa chỉ như nhau. ### 1. Phương pháp nối kết ![](https://hackmd.io/_uploads/B1Q0G63vn.png) - Nối kết trực tiếp + Các khóa bị băm vào cùng một địa chỉ sẽ gom thành danh sách. - Nối kết hợp nhất + Bảng băm trong trường hợp này cũng được cài đặt bằng danh sách liên kết. Nhưng các nút bị xung đột địa chỉ được kết nối với nhau qua danh sách liên kết. ### 2. Phương pháp băm lại (địa chỉ mở) Với hàm băm $h_1(key)=key\%M$ $h(key, i)$ là địa chỉ băm của khóa $key$ nếu tiến hành băm lại lần $i$. - Phương pháp dò tuyến tính: $h(key, i)=(h_1(key)+i)\%M$ - Phương pháp dò bậc hai: $h(key, i)=(h(key)+i^2)\%M$ - Phương pháp băm kép: $h_2(key)=(M-2)-key\%(M-2)$ $h(key, i)=(h_1(key)*i+h_2(key))\%M$ **Ví dụ:** Cho bảng băm ở trạng thái vừa khởi tạo có M = 11 nút, lần lượt thêm các khóa 30, 42, 24, 13, 3, 2, 10, 20 vào bảng theo thứ tự từ trái sang. | Chỉ mục | Khóa - Dò tuyến tính | Khóa - Dò bậc hai | Khóa - Băm kép | | - | ------ | - | -- | | 0 | 20 | 20 | 2 | | 1 | NULL | NULL | NULL | | 2 | 24 | 24 | 24 | | 3 | 13 | 13 | 3 | | 4 | 3 | 3 | NULL | | 5 | 2 | NULL | 20 | | 6 | NULL | 2 | NULL | | 7 | NULL | NULL | 13 | | 8 | 30 | 30 | 30 | | 9 | 42 | 42 | 42 | | 10 | 10 | 10 | 10 |

Nội dung chính Show

Uploaded by
Available Formats
Share this document
Did you find this document useful?
Is this content inappropriate?
Bang Bam - Hash Table
Uploaded by
Reward Your Curiosity
Giải quyết đụng độ
Cấu trúc một nút trong bảng băm
Cấu trúc bảng băm và hàm khởi tạo
Thêm một nút vào bảng băm
Tìm kiếm một khóa trong bảng băm
Xóa một nút ra khỏi bảng băm
Duyệt qua bảng băm
Lưu ý về bảng băm
Tổng kết

Uploaded by

vincevo

0% found this document useful (0 votes)

308 views

22 pages

Copyright

Available Formats

PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

0% found this document useful (0 votes)

308 views22 pages

Bang Bam - Hash Table

Uploaded by

vincevo

Jump to Page

You are on page 1of 22

Search inside document

Reward Your Curiosity

Everything you want to read.

Anytime. Anywhere. Any device.

No Commitment. Cancel anytime.

Bảng băm hay HashTable là một cấu trúc mà khi người dùng thực hiện truy xuất một phần tử qua khóa thì nó sẽ được ánh xạ vào thông qua hàm băm (Hash function).

Quá trình ánh xạ khóa vào bảng băm được thực hiện thông qua hàm băm (Hashing). Một bảng băm tốt cần phải có hàm băm tốt. Bảng băm là một mảng có M vị trí được đánh số từ 0 đến M – 1.

Có rất nhiều cách cài đặt kết nối của bảng băm như trực tiếp, dò tuyến tính, dò bậc hai, băm kép… Trong bài viết này mình sẽ giới thiệu đến các bạn phương pháp kết nối dò trực tiếp. Nhưng trước tiên, ta cần tìm hiểu hàm băm trước đã vì như mình đã nói, một bảng băm tốt khi nó có hàm băm tốt.

Trước khi vào bài, phương pháp kết nối trực tiếp là phương pháp sử dụng danh sách liên kết đơn, do đó, bạn nào chưa biết gì về danh sách liên kết đơn thì hãy xem lại bài Danh sách liên kết đơn trong C++ để hiểu rõ hơn nha.

Hàm băm hay là Hash function là hàm thực hiện việc ánh xạ khóa k nào đó vào trong bảng băm (h(k)). Một hàm băm tốt thỏa mản các tiêu chí sau:

Tốc độ tính toán nhanh
Các khóa được phân bố đều trong bảng
Ít xảy ra đụng độ

Mình sẽ giới thiệu đến các bạn các phép băm thường được sử dụng nhất là phương pháp chia và nhân.

Đối với phương pháp chia, mình sẽ ánh xạ khóa theo hàm h(k) = k % M, với k là khóa và M là kích thước của bảng băm.

Đối với phương pháp nhân, hàm ánh xạ h(k) = M * (k*A % 1), với k là khóa, M là kích thước bảng băm và A là số thực 0 < A < 1. Theo phương pháp nhân này, sự hiệu quả phụ thuộc vào việc lựa chọn A, theo như nhà khoa học máy tính Knuth, chọn A = (sqrt(5) – 1) / 2 là hiệu quả nhất (xấp xỉ 0.618033987).

Thông thường, mình sử dụng phương pháp chia cho dễ cài đặt. Tuy nhiên, không thể nào tránh khỏi đụng độ dù có dùng hàm băm nào đi nữa, do đó, chúng ta cần giải quyết đụng độ.

Giải quyết đụng độ

Đối với việc sử dụng phương pháp kết nối trực tiếp, các phần tử bị đụng độ sẽ được thêm vào danh sách liên kết tại h(k) trong bảng băm.

Như bạn có thể thấy trong hình, các khóa như 7, 17 đụng độ nhau thì chúng sẽ được thêm vào danh sách liên kết ở h(k) = M. Tương tự các khóa 4, 19 cũng bị đụng và được thêm vào danh sách liên kết ở h(k) = 2…

Bây giờ chúng ta hãy cùng bắt đầu cài đặt bảng băm vào trong trong C++ nha.

Cấu trúc một nút trong bảng băm

Như đã nói, phương pháp kết nối trực tiếp dùng danh sách liên kết đơn, các phần tử bị đụng độ tại phần tử i trong bảng băm thì sẽ được thêm vào danh sách liên kết đơn tại i trong bảng băm. Do đó, một phần tử trong bảng băm có cấu trúc như một nút trong danh sách liên kết đơn.

struct Node  
{  
    int key;  
    Node* next;  
};

Cấu trúc bảng băm và hàm khởi tạo

Một bảng băm là một mảng chứa các nút, giả sử mình có 100 phần tử, vậy mình sẽ định nghĩa một HashTable như sau:


# define M 100
typedef Node *HashTable[M];

Như vậy, chúng ta có thể khai báo một bảng băm như sau:

HashTable mHashTable;

Các bạn có thể dễ dàng thấy một nút trong bảng là một con trỏ trỏ đến một Node, như vậy, chúng ta cần phải khởi tạo chúng bằng NULL để tránh gặp lỗi. Mình sẽ có hàm khởi tạo bảng như sau:

void InitHashTable(HashTable &HT)  
{  
    for (int i = 0; i < M; i++)  
        HT[i] = NULL;  
}

Hàm băm

Như đã nói ở trên, để đơn giản mình sẽ sử dụng hàm băm theo phép chia:

int Hash(int k)  
{  
    return k % M;  
}

Thêm một nút vào bảng băm

Để thêm một nút, ta cần xác định vị trí sẽ thêm qua hàm băm h(k), sau đó thêm vào danh sách liên kết ở vị trí h(k) đó. Việc đụng độ sẽ được giải quyết do nếu đụng độ thì khóa sẽ được tự thêm vào sau danh sách liên kết đơn. Mình sẽ có hàm thêm như sau:

void InsertNode(HashTable &HT, int k)  
{  
    int i = Hash(k);  
    AddTail(HT[i], k);  
}

Hàm AddTail thì trong danh sách liên kết đơn, mình đã có bài viết về nó rồi, các bạn có thể đọc lại.

void AddTail(Node *&l, int k)  
{  
    Node *newNode = new Node{k, NULL};  
    if (l == NULL)  
    {  
        l = newNode;  
    }  
    else  
    {  
        Node* p = l;  
        while (p != NULL && p->next != NULL)  
            p = p->next;  
        p->next = newNode;  
    }  
}

Tìm kiếm một khóa trong bảng băm

Để tìm kiếm một khóa trong bảng băm, ta cũng thực hiện xác định vị trí h(k), sau đó ta thực hiện tìm kiếm trong danh sách liên kết tại vị trí h(k) trong bảng băm.

Node *SearchNode(HashTable HT, int k)  
{  
    int i = Hash(k);  
    Node *p = HT[i];  
    while (p != NULL && p->key != k)  
        p = p->next;  
    if (p == NULL)  
        return NULL;  
    return p;  
}

Xóa một nút ra khỏi bảng băm

Để xóa một phần tử ra khỏi bảng băm, đầu tiên ta cũng phải xác định h(k), sau đó tìm xem nó nằm ở đâu trong danh sách liên kết đơn tại vị trí h(k) đó rồi thực hiện xóa nó đi.

void DeleteNode(HashTable &HT, int k)  
{  
    int i = Hash(k);  
    Node *p = HT[i];  
    Node *q = p;  
    while (p != NULL && p->key != k)  
    {  
        q = p; // Lưu lại địa chỉ của phần tử trước đó  
        p = p->next;  
    }  
    if (p == NULL)  
        cout << k << " not found!" << endl;  
    else if (p == HT[i])  
        DeleteHead(HT[i]); // Nút cần xóa là phần tử đầu của DSLK  
    else  
        DeleteAfter(q); // Xóa nút sau nút q  
}

Hai hàm DeleteHead và DeleteAfter cũng đã được mình trình bày trong bài Danh sách liên kết đơn trong C++ rồi nên mình sẽ không giả thích gì thêm.

void DeleteHead(Node *&l)  
{  
    if (l != NULL)  
    {  
        Node *p = l;  
        l = l->next;  
        delete p;  
    }  
}
void DeleteAfter(Node *&q)  
{  
    Node *p = q->next;  
    if (p != NULL)  
    {  
        q->next = p->next;  
        delete p;  
    }  
}

Duyệt qua bảng băm

Duyệt qua bảng băm rất đơn giản, bạn chỉ cần duyệt qua mảng, mỗi phần tử của mảng là một danh sách liên kết đơn, vậy thì duyệt danh sách liên kết đơn nữa là xong.


# define M 100
typedef Node *HashTable[M];

0

Lưu ý về bảng băm

Đối với dữ liệu lớn, việc cấp phát một mảng quá lớn sẽ gây lãng phí bộ nhớ không đáng có, tuy nhiên, việc M lớn đảm bảo việc đụng độ ít xảy ra do các khóa phân bố đều. Ngược lại, nếu M nhỏ để tiết kiệm bộ nhớ, việc này sẽ làm giảm hiệu suất của bảng băm do việc đụng độ xảy ra với tần suất cao hơn.

Do vậy, khi thao tác với bảng băm, các bạn cần phải cân nhắc giữa hiệu suất và dung lượng lưu trữ.

Tổng kết

Như vậy là trong bài viết này, mình đã giới thiệu đến các bạn về bảng băm trong C++, cách cài đặt bảng băm bằng phương thức kết nối trực tiếp dùng danh sách liên kết đơn. Nếu các bạn có bất kỳ ý kiến, đóng góp nào, đừng ngần ngại comment phía bên dưới bài viết nha. Cảm ơn các bạn đã theo dõi bài viết!

mẹo hay Khỏe Đẹp Bài tập Học Tốt Phương pháp Bảng băm Bảng băm Python Mảng băm