Hash Table

TIL

781

hashtable

3

hell nguyen viết ngày 19/11/2017

Quick lookup are often really important.

Với lý do này, chúng ta sử dụng arrays O(1) - time lookups) thường xuyên hơn linked lists (O(i)-time lookups).
Ví dụ, chúng ta muốn đếm mỗi ký tự ASCII xuất hiện bao nhiêu lần trong câu truyện Romeo và Juliet. Chúng ta sẽ lưu trữ như thế nào?
Chúng ta có thể sử dụng các array ở đây.
Nhớ là các ký tự là các số. Trong ASCII 'A' là 65, 'B' là 66,...
Vì vậy chúng ta có thể sử dụng ký tự (giá trị số) là các index trong array của chúng ta, và lưu giữ count tại các index trong array.

Với array này, chúng ta có thể tìm và sửa count với bất cứ ký tự nào trong 1 thời gian cố định.
Đôi khi chúng ta gặp được điều thú vị - array này không chỉ đơn giản là một list các giá trị.
Array này lưu trữ 2 thứ :

• các ký tự
• các số đếm

Các ký tự ngầm định là các index.
Vì vậy chúng ta có thể nghĩ một array là một table với 2 cột.

Nếu chúng ta muốn đưa bất kỳ giá trị nào trong cột và vẫn có được tìm kiếm nhanh chóng...

Giả định chúng ta muốn đếm số lần xuất hiện của từ "lies" trong Romeo và Juliet.
Chúng ta có thể sử dụng mảng?
Chuyển đổi một ký tự thành một mảng index rất dễ dàng.
Nhưng chúng ta sẽ làm vài thứ thông minh hơn để chuyển
đổi "lies" - một string thành một mảng array index...

Ở đây có một cách như sau:
Gom các giá trị của mỗi ký tự như sau:
"l" => 108
"i" => 105
"e" => 101
"s" => 115
108 + 105 + 101 + 115 = 429
Kết quả là 429. Nhưng nếu chúng ta chỉ có 30 slots cho mảng? Chúng ta sẽ dùng mẹo sau: Dùng modulus operator(%).
429 % 30 = 9

Hashing function

Đó là cách chúng ra lấy ta một từ (hoặc một string) thành một index trong array.
Cấu trúc dữ liệu này được gọi là một hash table hoặc hash map.
Trong bảng hash table, counts là các values và words( ví dụ: "lies") là các keys (là các index của array).
Quá trình chúng ta sử dụng để chuyển đổi một key thành một giá trị index array được gọi là
hashing function.

==> NOTE:
Các hashing function được sử dụng trong hệ thống phức tạp - cách chúng ta sử dụng ở đây là ví dụ đơn giản.

Tìm kiếm nhanh chóng chỉ có 1 chiều

Chúng ta có thể nhanh chóng lấy một value là key, nhưng cách duy nhất lấy key từ một values là chúng ta phải duyệt hết, tất cả các key và values. Điều này tương tự với các arrays - chúng ta có thể tìm nhanh chóng giá trị tại một index, nhưng chỉ có 1 cách để lấy được index từ giá trị là đi duyệt toàn bộ trong array.

Hash collision

Một vấn đề - nếu có 2 key mà cùng đưa ra 1 index trong
array? Ví dụ : "lies" và "foes":

Chúng đều có tổng là 429.
Vì vậy chúng ta sẽ có chung 1 kết quả 429 % 30 = 9
Vì vậy hashing functions của chúng ra đưa ra 1 output mà 2 input hoàn toàn khác nhau.
Đây gọi là hash collision.
Do đó cần một chút thay đổi. Đây là 1 cách cơ bản: thay vì lưu các actual values trong mảng chúng ta, để mỗi array slot chứ một pointer đến một linked list lưu count cho các từ mà có index đó.

Một vấn đề - làm thế nào mà chúng ta biết đâu là count của "lies" và đâu là count của "foes"?
Để sửa điều này, chúng ta sẽ lưu word với mỗi node trong linked list là một count.

Tìm kiếm trung bình vẫn là O(1)?

Nhưng khoan, chúng ta có thể nghĩ: Vậy lúc này việc tìm kiếm trong hash table của chúng ta là O(n) trong trường hợp xấu nhất.
Đó là sự thật, trường hợp xấu nhất là mọi key được tạo ra một hash collision, vì vậy hash table trở thành một linked list.
Và chúng ta thường nghe nói là các xung đột ở mức vừa đủ để time tìm kiếm trung bình vẫn là O(1).
Và các thuật toán giữ cho số lần conllisions thấp và giữ độ dài danh sách liên kết tốt và ngắn.
Bạn có thể tìm kiếm đủ nhanh ngoại trừ một số trường hợp có thể lâu. Và tất nhiên bạn chỉ tìm kiếm nhanh chóng theo 1 chiều - còn việc lấy key từ 1 value vẫn tốn O(n) time.

Note: Nội dung lấy từ https://www.interviewcake.com/article/python/data-structures-coding-interview

nguyenduyhao1111 20-11-2017