HASH TABLE LÀ GÌ

     

Giả sử, chúng ta muốn xây cất một hệ thống lưu trữ hồ sơ nhân viên. Mỗi hồ sơ sẽ sở hữu một key (khóa) nhằm định danh bằng cách dùng số năng lượng điện thoại. Bọn họ muốn khối hệ thống đó phải thực hiện các làm việc sau một cách hiệu quả:

1. Tư tưởng của Hashing

Vậy với những yêu ước trên, bạn có thể nghĩ vẫn thiết kế hệ thống sử dụng các cấu trúc dữ liệu như sau đây để tàng trữ số điện thoại cảm ứng kèm thông tin tương ứng:

Một Array (mảng) tàng trữ số điện thoại cảm ứng và hồ sơ.Một Linked List (danh sách liên kết) tàng trữ số điện thoại thông minh và hồ sơ.Một Balanced Binary tìm kiếm Tree (cây search kiếm nhị phân cân nặng bằng) áp dụng số điện thoại thông minh làm key (khóa).Một Direct Access Table (sử dụng thẳng khóa làm chỉ mục vào mảng).

Bạn đang xem: Hash table là gì

Bạn đang xem: Hash table là gì

Với ArrayLinked List, trong thao tác tìm tìm thì bọn họ cần đề xuất tìm kiếm theo kiểu tuyến tính (Linear Search). Nếu danh sách đã được sắp tới xếp, số năng lượng điện thoại có thể được tra cứu theo Binary Search, mà tất cả độ tinh vi thời gian là O(log n). Nhưng chúng ta phải trả giá chỉ cho làm việc thêm bắt đầu và xóa, vì cần luôn gia hạn thứ tự sắp xếp.

Với Balanced Binary search Tree, tất cả các thao tác tìm kiếm, thêm mới, xóa hoàn toàn có thể được đảm bảo an toàn trong thời hạn O(log n).

Với Direct Access Table, họ sẽ tạo thành một mảng khủng và sử dụng số điện thoại cảm ứng làm chỉ mục vào mảng. Mỗi mục vào mảng vẫn là NIL (0 hoặc null) nếu không có thông tin lưu giữ trữ. Với kết cấu dữ liệu này, Time Complexity sẽ cực tốt so với tất cả các cấu trúc trên, chúng ta có thể thực hiện tất cả các thao tác trong thời hạn O(1).

Giải pháp Direct Access Table vào thực tế có không ít hạn chế. Hạn chế dễ thấy tốt nhất là bộ nhớ lưu trữ cần thiết nhằm lưu trữ sẽ tương đối lớn.

Hashing là một phương án để thay thế cho toàn bộ các kết cấu dữ liệu bên trên khi có tác dụng thực tế. Hashing là 1 kỹ thuật cách tân hơn đối với Direct Access Table.

Ý tưởng của Hashing là phân phối các cặp khóa/giá trị bên trên một mảng. Nó áp dụng một hash function (hàm băm) để chuyển đổi các khóa có giá trị to thành giá chỉ trị nhỏ hơn và áp dụng số bé dại hơn đó có tác dụng chỉ mục vào một bảng hotline là hash table (bảng băm).

2. Hash function

Hash function là 1 trong những hàm ánh xạ một dữ liệu có kích cỡ tùy ý (một số nguyên lớn, một chuỗi,…) thành một số nguyên nhỏ để hoàn toàn có thể sử dụng làm cho chỉ mục trong hash table. Quý hiếm trả về của hash function hoàn toàn có thể gọi là hash values, hash codes hoặc dễ dàng và đơn giản là hashes.

Một Hash function giỏi phải đạt được các yêu ước sau:

Dễ tính toánPhân phối đều: quý hiếm trả về từ bỏ hash function sẽ giúp phân phối đều những entries trên hash table, kiêng bị chia thành các cụm.Tránh ít va chạm (collisions): Va chạm xẩy ra khi các cặp bộ phận được ánh xạ tới cùng một hash codes.

Lưu ý: dù việc setup hash function tốt đến đâu đi chăng nữa, thì việc xảy ra va đụng (collisions) là vấn đề không thể kị khỏi. Vày vậy để bảo trì một performance tốt cho hash table, điều đặc biệt quan trọng là phải xử lý các collisions thông qua các kỹ thuật khác nhau.

3. Hash table

Hash table (bảng băm) là một cấu trúc dữ liệu sử dụng mảng để lưu trữ những cặp khóa/giá trị. Mỗi vị trí trong mảng gọi là 1 trong bucket, hoàn toàn có thể null, chứa một, hoặc chứa đựng nhiều cặp khóa/giá trị. Nó sử dụng hash function (hàm băm) để đo lường và tính toán một index trong mảng để chèn hoặc tra cứu kiếm phần tử.


*

Giải say mê hình minh họa:

Ta bắt buộc lưu trữ tin tức của 3 người, với key (khóa) là tên, còn quý giá là số điện thoại:John Smith: 521-1234Lisa Smith: 521-8976Sandra Dee: 521-9655Giá trị Hash của 3 người này theo lần lượt là: 1, 2 cùng 14.Sau khi tính được giá trị Hash của 3 người, ta lưu giữ vào các bucket tương xứng là 1, 2 với 14.

Xem thêm: Cách Phân Biệt Các Loại Key Retail Là Gì ? Thế Nào La Volume License Và Retail

Nếu các hiệu quả của hàm hash được phân bố đều, những bucket vẫn có kích thước xấp xỉ nhau. Giả sử số bucket đầy đủ lớn, từng buckets đã chỉ có một vài phần tử trong chúng. Điều này làm cho cho việc tìm và đào bới kiếm siêu hiệu quả.

4. Độ phức tạp

Gọi:

n là số thành phần ta phải lưu trong Hash tablelà số bucket

Giá trị α = n / k được điện thoại tư vấn là load factor (số bộ phận trung bình được lưu giữ ở mỗi bucket).

Khi load factor nhỏ tuổi (xấp xỉ 1), và quý hiếm của hash function phân bố đều, thì độ phức hợp của các thao tác trên Hash table là O(1).

5. Collision Handling

hash function giúp biến đổi một khóa có giá trị khủng thành một số nhỏ dại nên sẽ có tác dụng 2 khóa sẽ có cùng một quý giá băm (hash codes). Collision là một tình huống khi thêm mới một phần tử vào một vị trí cơ mà đã tồn tại một trong những phần tử không giống trong hash table, bây giờ ta yêu cầu xử lý va va bằng một số trong những kỹ thuật:

5.1. Separate Chaining

Tư tưởng là thiết lập thêm những Linked List (danh sách liên kết) ở các bucket để lưu trữ các bộ phận có cùng quý hiếm hash code.

Ưu điểm:

Kỹ thuật này cài đặt đơn giảnHash table sẽ cạnh tranh bị che đầy, vì những giá trị tất cả cùng hash code ta đang nối cung cấp linked list.Nó hầu hết được sử dụng lúc không biết có bao nhiêu và tần suất những khóa có thể được chèn hoặc xóa.

Nhược điểm:

Tốn bộ nhớ lưu trữ vì 1 phần của hash table không lúc nào được sử dụng, với tốn thêm cả bộ nhớ lưu trữ lưu trữ đến linked list.Nếu Linked danh sách quá dài, thì thời gian tìm kiếm hoàn toàn có thể là O(n) trong worse case.Hiệu suất của bộ nhớ cache không tốt.

Độ phức tạp:

Time Complexity để triển khai các làm việc search/insert/delete là: O(1 + α)

1 là tiến hành hash function và truy vấn tới vị trí trong hash tableα là chú ý qua danh sách ở từng vị trí.
*

Giải thích hợp hình minh họa:

Mỗi bucket là một trong những danh sách liên kếtJohn Smith cùng Sandra Dee cùng có mức giá trị hàm hash là 152, yêu cầu ở bucket 152, ta có 1 danh sách liên kết chứa 2 phần tử.

5.2. Open Addressing

Tư tưởng của Open Addressing là khi xảy ra Hash collision, ta lưu vào một trong những vị trí tiếp theo sau trong hash table. Tức là, hash table đề nghị đủ vị trí nhằm lưu toàn bộ các phần tử. Bởi vậy, size của hash table luôn >= toàn bô khóa, tuyệt Load factor phải nhỏ tuổi hơn 1.

Xem thêm: To Whom It May Concern Là Gì ? To Whom It May Concern

Việc search vị trí tiếp theo để lưu giữ khóa có thể được tiến hành bằng một vài cách sau:

Linear ProbingQuadratic ProbingDouble Hashing

Minh họa việc tìm vị trí tiếp theo của khóa theo Linear Probing:


*

Trong hình minh họa:

John Smith với Sandra Dee đều phải có giá trị Hash là 152. Bởi ta sẽ lưu John Smith vào bucket 152, bắt buộc ta cần lưu Sandra Dee vào bucket 153.Ted Baker có giá trị Hash là 153, nhưng lúc này bucket 153 vẫn lưu thông tin của Sandra Dee, bắt buộc ta nên lưu cực hiếm của Ted Baker vào bucket 154.

Đọc thêm:

https://en.wikipedia.org/wiki/Hash_table

https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/