Bản đồ băm nodejs

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ử thông qua khóa thì nó sẽ được ánh xạ vào thông qua hàm băm (Hàm băm)

  1001 Mẹo. Con trỏ và hàm (Con trỏ & Hàm) trong C++

  C Token là gì?

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 trùm tốt cần phải có hàm băm tốt. Bảng trùm là một mảng có M vị trí được đánh số từ 0 đến M – 1

HashTable

Có rất nhiều cách cài đặt kết nối của bảng trùm như trực tiếp, dò tuyến tính, dò bậc hai, trù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 trực tiếp. Nhưng mà 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 cái bàn rau tốt khi nó có hàm rau 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 đơn, làm vậy bạn nào chưa biết gì về danh sách liên đơn thì xem lại bài Danh sách liên đơn trong C++ để hiểu nhé

hash

Hàm băm hay là Hàm băm là hàm thực hiện ánh xạ từ khóa k nào vào trong bảng băm (h(k)). Một hàm gấu trùm đầu của các tiêu chí sau

• Tốc độ tính toán nhanh
• Các từ khoá được phân bố đều trong bảng
• Xảy ra xung đột

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

Đối với phương pháp chia sẻ, mình sẽ ánh xạ từ 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 trù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, 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 sẻ để dễ cài đặt. Tuy nhiên, không thể tránh xung đột dù có sử dụng hàm băm nào đi nữa, do đó, chúng ta cần giải quyết xung đột

Giải pháp quyết định

Đố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ị xung đột sẽ được thêm vào danh sách liên kết tại h(k) trong bảng trùm

Chuỗi HashTable

Nếu bạn có thể thấy trong hình, các từ khóa như 7, 17 xung quanh 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 key 4, 19 cũng bị xung đột 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 C++ nha

Constructor a node in the hash table

Như đã nói, phương pháp kết nối trực tiếp sử dụng danh sách liên kết đơn, các phần tử bị xung đột 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 hình bảng băm cấu trúc và khởi tạo hàm

Một bảng trù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 tìm thấy một nút trong bảng là một con trỏ trỏ đến một nút, do đó, chúng ta cần phải khởi động chúng bằng NULL để tránh gặp lỗi. Mình sẽ có chức năng khởi tạo bảng như sau

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

hash

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

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

Add a node to the table

Để thêm một nút, ta cần xác định vị trí định vị sẽ bổ sung qua hàm băm h(k), sau đó thêm vào danh sách liên kết ở vị trí h(k) đó. Xung đột sẽ được giải quyết nếu xung đột thì khóa sẽ được tự động thêm vào sau danh sách liên kết đơn. Mình sẽ có thêm chức năng 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 từ khóa trong bảng băm

Để tìm kiếm một 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;
}

Delete a node to from the hash table

Để 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

________số 8_______

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 tên

Đố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 chắc chắn xung quanh mức độ í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 điện năng cho bộ nhớ, công việc này sẽ làm giảm hiệu suất của bảng băm do công việc xung đột xảy ra với tần suất cao hơn

Do đó, khi thao tác với bảng băm, các bạn cần 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 với 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 sử 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 thì đừng ngại comment phía dưới bài viết nha. Cảm ơn các bạn đã theo dõi bài viết