HASH TABLE LÀ GÌ

Giả sử, bọn họ mong mỏi xây cất một hệ thống tàng trữ làm hồ sơ nhân viên cấp dưới. Mỗi hồ sơ sẽ sở hữu được một key (khóa) để định danh bằng phương pháp cần sử dụng số điện thoại. Chúng ta ước ao khối hệ thống kia nên triển khai các thao tác sau một giải pháp hiệu quả:

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

Vậy với những đề nghị bên trên, chúng ta cũng có thể suy nghĩ vẫn xây cất hệ thống sử dụng những cấu trúc tài liệu nhỏng sau đây để lưu trữ số Smartphone kèm thông tin tương ứng:

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

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

Với Array cùng Linked List, trong thao tác làm việc tìm kiếm thì họ cần được kiếm tìm tìm theo phong cách đường tính (Linear Search). Nếu list đã có thu xếp, số điện thoại cảm ứng thông minh hoàn toàn có thể được kiếm tìm theo Binary Search, cơ mà gồm độ phức tạp thời hạn là O(log n). Nhưng bọn họ yêu cầu trả giá bán mang lại thao tác thêm new và xóa, bởi vì cần luôn gia hạn lắp thêm từ bỏ sắp xếp.

Với Balanced Binary Search Tree, tất cả những thao tác làm việc tìm tìm, thêm new, xóa hoàn toàn có thể được bảo đảm an toàn vào thời gian O(log n).

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

Giải pháp Direct Access Table vào thực tế có khá nhiều hạn chế. Hạn chế dễ thấy duy nhất là bộ lưu trữ quan trọng nhằm lưu trữ đang rất to lớn.

Hashing là 1 giải pháp nhằm sửa chữa đến tất cả các cấu trúc dữ liệu trên khi có tác dụng thực tế. Hashing là một trong chuyên môn cách tân rộng so với Direct Access Table.

Ý tưởng của Hashing là phân păn năn những cặp khóa/quý hiếm bên trên một mảng. Nó thực hiện một hash function (hàm băm) để thay đổi những khóa có mức giá trị mập thành quý giá nhỏ rộng cùng áp dụng số nhỏ tuổi hơn đó có tác dụng chỉ mục trong một bảng điện thoại tư vấn là hash table (bảng băm).

2. Hash function

Hash function là 1 trong những hàm ánh xạ một tài liệu gồm size tùy ý (một số trong những nguim phệ, một chuỗi,…) thành một số trong những nguyên nhỏ tuổi để hoàn toàn có thể áp dụng làm cho chỉ mục trong hash table. Giá trị trả về của hash function có thể gọi là hash values, hash codes hoặc đơn giản dễ dàng là hashes.

Một Hash function xuất sắc cần đạt được những trải nghiệm sau:

Dễ tính toánPhân phối đều: Giá trị trả về từ bỏ hash function để giúp đỡ phân phối phần đa các entries trên hash table, tránh bị tạo thành các cụm.Tránh không nhiều va chạm (collisions): Va chạm xẩy ra Lúc những cặp bộ phận được ánh xạ tới và một hash codes.

Lưu ý: Dù việc cài đặt hash function giỏi mang đến đâu đi chăng nữa, thì Việc xẩy ra va va (collisions) là điều quan yếu tránh ngoài. Vì vậy để gia hạn một performance giỏi đến hash table, điều đặc biệt quan trọng là phải xử lý những collisions trải qua các nghệ thuật khác nhau.

3. Hash table

Hash table (bảng băm) là một trong cấu trúc dữ liệu sử dụng mảng để lưu trữ các cặp khóa/giá trị. Mỗi địa điểm trong mảng Call là một trong những bucket, rất có thể null, chứa một, hoặc chứa nhiều cặp khóa/quý giá. Nó áp dụng hash function (hàm băm) nhằm tính toán một index trong mảng nhằm cyếu hoặc kiếm tìm tìm bộ phận.

Bằng cách setup một hash function xuất sắc, họ sẽ sở hữu một hash table vận động với performance giỏi. Theo những mang thiết lý tưởng phát minh, thời hạn vừa phải cần thiết nhằm tìm kiếm kiếm một trong những phần tử trong hash table là O(1).

Xem thêm: Tên Thật Của Ji Hyo "Running Man" Khoe Vẻ Đẹp Bất Chấp Thời Gian

Giải ưng ý hình minh họa:

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

Nếu những kết quả của hàm hash được phân bổ hầu như, những bucket sẽ có được form size giao động nhau. Giả sử số bucket đủ bự, mỗi buckets vẫn chỉ bao gồm một vài thành phần vào bọn chúng. Điều này tạo cho việc đào bới tìm kiếm tìm hết sức kết quả.

4. Độ phức tạp

Gọi:

n là số bộ phận ta phải giữ vào Hash tablek là số bucket

Giá trị α = n / k được Gọi là load factor (số bộ phận vừa phải được lưu lại ngơi nghỉ mỗi bucket).

lúc load factor nhỏ (xấp xỉ 1), và cực hiếm của hash function phân bổ phần đông, thì độ tinh vi của các thao tác làm việc trên Hash table là O(1).

5. Collision Handling

Vì hash function giúp chuyển đổi một khóa có mức giá trị mập thành một trong những nhỏ đề nghị đang có công dụng 2 khóa sẽ có cùng một cực hiếm băm (hash codes). Collision là một trường hợp khi thêm mới một trong những phần tử vào một trong những vị trí nhưng sẽ trường thọ 1 phần tử không giống trong hash table, từ bây giờ ta đề nghị giải pháp xử lý va đụng bởi một trong những kỹ thuật:

5.1. Separate Chaining

Tư tưởng là setup thêm những Linked List (danh sách liên kết) ngơi nghỉ những bucket để lưu trữ các phần tử gồm thuộc quý giá hash code.

Ưu điểm:

Kỹ thuật này thiết lập đơn giảnHash table vẫn cực nhọc bị đậy đầy, vì các quý hiếm bao gồm cùng hash code ta đã nối chế tạo linked menu.Nó chủ yếu được áp dụng lúc không biết tất cả bao nhiêu với gia tốc những khóa có thể được cyếu hoặc xóa.

Nhược điểm:

Tốn bộ nhớ lưu trữ vị 1 phần của hash table ko bao giờ được thực hiện, và tốn thêm cả bộ nhớ tàng trữ cho linked danh mục.Nếu Linked List quá nhiều năm, thì thời gian tra cứu kiếm hoàn toàn có thể là O(n) trong worse case.Hiệu suất của bộ lưu trữ cache không giỏi.

Độ phức tạp:

Time Complexity nhằm tiến hành các thao tác search/insert/delete là: O(1 + α)

1 là triển khai hash function với truy vấn tới địa chỉ vào hash tableα là chăm bẵm qua danh sách sống từng địa chỉ.

Giải ưng ý hình minch họa:

Mỗi bucket là một trong những danh sách liên kếtJohn Smith với Sandra Dee thuộc có mức giá trị hàm hash là 152, cần ngơi nghỉ bucket 152, ta có 1 list link đựng 2 thành phần.

5.2. Open Addressing

Tư tưởng của Open Addressing là khi xẩy ra Hash collision, ta lưu vào trong 1 địa chỉ tiếp theo vào hash table. Tức là, hash table yêu cầu đủ vị trí nhằm lưu toàn bộ những phần tử. Vì vậy, kích cỡ của hash table luôn >= tổng cộng khóa, xuất xắc Load factor buộc phải nhỏ hơn 1.

Việc tìm địa chỉ tiếp sau để lưu giữ khóa hoàn toàn có thể được thực hiện bằng một vài bí quyết sau:

Linear ProbingQuadratic ProbingDouble Hashing

Minch họa việc tìm và đào bới vị trí tiếp theo sau của khóa theo Linear Probing:

Trong hình minc họa:

John Smith cùng Sandra Dee đều phải có giá trị Hash là 152. Vì ta vẫn lưu lại John Smith vào bucket 152, cần ta đề nghị lưu lại Sandra Dee vào bucket 153.Ted Baker có mức giá trị Hash là 153, nhưng mà từ bây giờ bucket 153 đã giữ thông tin của Sandra Dee, đề xuất ta cần lưu lại 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/