Giả sử, họ mong muốn thi công một khối hệ thống lưu trữ hồ sơ nhân viên. Mỗi làm hồ sơ sẽ sở hữu một key (khóa) để định danh bằng cách sử dụng số điện thoại. Chúng ta mong muốn hệ thống kia đề xuất tiến hành các làm việc sau một bí quyết hiệu quả:

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

Vậy với những thử khám phá trên, bạn có thể nghĩ về đang xây đắp hệ thống áp dụng những cấu trúc tài liệu nhỏng sau đây nhằm tàng trữ số điện thoại thông minh kèm thông báo tương ứng:

Một Array (mảng) tàng trữ số điện thoại cảm ứng và làm hồ sơ.Một Linked List (danh sách liên kết) tàng trữ số điện thoại thông minh cùng hồ sơ.Một Balanced Binary Search Tree (cây kiếm tìm tìm nhị phân cân bằng) sử dụng số điện thoại làm 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ì

quý khách đang xem: Hash table là gì

Với Array cùng Linked List, vào thao tác tìm kiếm tìm thì bọn họ cần được tìm tìm theo kiểu tuyến đường tính (Linear Search). Nếu list đã có thu xếp, số điện thoại cảm ứng hoàn toàn có thể được tìm kiếm theo Binary Search, nhưng mà tất cả độ tinh vi thời gian là O(log n). Nhưng bọn họ phải trả giá cho làm việc thêm mới với xóa, do cần luôn gia hạn đồ vật tự sắp xếp.

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

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

Giải pháp Direct Access Table trong thực tiễn có rất nhiều tinh giảm. Hạn chế dễ thấy nhất là bộ nhớ quan trọng để lưu trữ đang không hề nhỏ.

Hashing là 1 trong phương án nhằm sửa chữa thay thế cho tất cả những cấu tạo tài liệu bên trên lúc làm cho thực tiễn. Hashing là 1 kỹ thuật cải tiến rộng so với Direct Access Table.

Ý tưởng của Hashing là phân pân hận các cặp khóa/quý giá bên trên một mảng. Nó sử dụng một hash function (hàm băm) nhằm biến hóa các khóa có giá trị béo thành giá trị nhỏ tuổi hơn và thực hiện số nhỏ dại hơn kia làm cho chỉ mục trong một bảng Gọi 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 kích thước tùy ý (một trong những nguyên béo, một chuỗi,…) thành một số nguyên nhỏ để rất có thể thực hiện có tác dụng chỉ mục vào hash table. Giá trị trả về của hash function có thể hotline là hash values, hash codes hoặc dễ dàng là hashes.

Một Hash function xuất sắc phải dành được các tận hưởng sau:

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

Lưu ý: Dù câu hỏi cài đặt hash function xuất sắc cho đâu đi chăng nữa, thì câu hỏi xẩy ra va chạm (collisions) là vấn đề tất yêu tách khỏi. Vì vậy để gia hạn một performance tốt cho hash table, điều đặc biệt quan trọng là buộc phải cách xử trí những collisions thông qua các nghệ thuật khác nhau.

3. Hash table

Hash table (bảng băm) là 1 trong những kết cấu tài liệu sử dụng mảng nhằm lưu trữ những cặp khóa/giá trị. Mỗi địa chỉ vào mảng hotline là 1 trong những bucket, rất có thể null, đựng một, hoặc đựng được nhiều cặp khóa/giá trị. Nó sử dụng hash function (hàm băm) để tính tân oán một index trong mảng nhằm chèn hoặc search kiếm bộ phận.


*

Giải phù hợp hình minh họa:

Ta phải tàng trữ biết tin của 3 người, với key (khóa) là tên gọi, còn cực hiếm là số năng lượng điện thoại:John Smith: 521-1234Lisa Smith: 521-8976Sandra Dee: 521-9655Giá trị Hash của 3 tín đồ này theo thứ tự là: 1, 2 với 14.Sau lúc tính giá tốt trị Hash của 3 người, ta giữ vào những bucket tương ứng là một trong những, 2 với 14.

Xem thêm: Put In Place Nghĩa Là Gì Trong Tiếng Việt? Put In Place Là Gì

Nếu các công dụng của hàm hash được phân bố đông đảo, các bucket sẽ sở hữu kích cỡ xê dịch nhau. Giả sử số bucket đủ Khủng, từng buckets sẽ chỉ tất cả một vài ba bộ phận vào chúng. Vấn đề này khiến cho việc tìm và đào bới kiếm cực kỳ tác dụng.

4. Độ phức tạp

Gọi:

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

Giá trị α = n / k được call là load factor (số thành phần trung bình được lưu ở mỗi bucket).

lúc load factor nhỏ (dao động 1), và quý giá của hash function phân bố phần đông, thì độ phức tạp của các làm việc trên Hash table là O(1).

5. Collision Handling

hash function góp chuyển đổi một khóa có giá trị to thành một số nhỏ cần vẫn có tác dụng 2 khóa sẽ có được và một quý hiếm băm (hash codes). Collision là một trường hợp Lúc thêm mới một phần tử vào trong 1 vị trí mà lại vẫn trường tồn 1 phần tử khác trong hash table, từ bây giờ ta đề xuất giải pháp xử lý va đụng bởi một số trong những kỹ thuật:

5.1. Separate Chaining

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

Ưu điểm:

Kỹ thuật này thiết lập đối chọi giảnHash table đã nặng nề bị đậy đầy, vị các quý giá tất cả cùng hash code ta sẽ nối cung cấp linked các mục.Nó đa phần được sử dụng khi không biết gồm từng nào cùng gia tốc những khóa có thể được cyếu hoặc xóa.

Nhược điểm:

Tốn bộ nhớ vị một trong những phần của hash table không khi nào được thực hiện, và tốn thêm cả bộ nhớ lưu trữ tàng trữ cho linked menu.Nếu Linked List vượt nhiều năm, thì thời gian tìm kiếm tìm rất có thể là O(n) trong worse case.Hiệu suất của bộ nhớ cađậy không tốt.

Độ phức tạp:

Time Complexity nhằm triển khai những thao tác làm việc search/insert/delete là: O(1 + α)

1 là tiến hành hash function và truy vấn cho tới địa điểm trong hash tableα là phê duyệt qua list ngơi nghỉ từng địa chỉ.
*

Giải say đắm hình minc 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, buộc phải sinh hoạt bucket 152, ta có một list link cất 2 bộ phận.

5.2. mở cửa Addressing

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

Việc tìm địa chỉ tiếp theo để lưu giữ khóa hoàn toàn có thể được thực hiện bởi một trong những 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 minch họa:

John Smith với Sandra Dee đều có quý giá Hash là 152. Vì ta vẫn giữ John Smith vào bucket 152, nên ta yêu cầu lưu Sandra Dee vào bucket 153.Ted Baker có mức giá trị Hash là 153, nhưng lại hôm nay bucket 153 vẫn lưu đọc tin của Sandra Dee, nên ta bắt buộc lưu quý giá 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/

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *