Hash Table
TIL
594
hashtable
3
White

nguyenduyhao1111 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

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

nguyenduyhao1111

12 bài viết.
39 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
17 2
Mở đầu Khi bạn đi sâu vào thế giới linux , bạn tìm thấy nhiều điều khó có thể hiểu ngay lập tức. Và 1 trong những thứ này là khái niệm socket. Tô...
nguyenduyhao1111 viết hơn 1 năm trước
17 2
White
12 0
Trước khi so sánh khác nhau về HDFS và HDFS2. Chúng ta đi tìm hiểu về HDFS là cái gì, kiến trúc thế nào? Vì sao điều này lại quan trọng. Bởi vì đâ...
nguyenduyhao1111 viết gần 2 năm trước
12 0
White
10 0
Khái niệm : Mapreduce là một mô hình lập trình, thực hiện quá tình xử lý tập dữ liệu lớn. Mapreduce gồm 2 pha : map và reduce. Hàm Map : Các xử l...
nguyenduyhao1111 viết gần 2 năm trước
10 0
Bài viết liên quan
White
0 2
fCC: Technical Documentation Page note So I have finished the HTML part of this exercise and I want to come here to lament about the lengthy HTML ...
HungHayHo viết 1 tháng trước
0 2
White
19 1
Toán tử XOR có tính chất: + A XOR A = 0 + 0 XOR A = A Với tính chất này, có thể cài đặt bài toán sau với độ phức tạp O(N) về runtime, và với O(1)...
kiennt viết gần 2 năm trước
19 1
White
1 1
Chào mọi người, hôm nay mình viết một bài TIL nhỏ về cách lấy độ phân giải của màn hình hiện tại đang sử dụng. xdpyinfo | grep dimensions Kết quả...
namtx viết 12 tháng trước
1 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
12 bài viết.
39 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!