Hash table là gì

Mở đầu Mở đầu Hàng đợi ưu tiên Hàng hóng ưu tiên Heap Giới thiệu về Heap, max heap Min Heap Sắp xếp heap sort Bảng băm - Hash table Bảng băm - Hash table Giải quyết xung chợt - Separate chaining

Giới thiệu về hashing

Hashing là một trong những chuyên môn dùng để làm xác minh tuyệt nhất một đối tượng ví dụ từ bỏ một nhóm các đối tượng người sử dụng tựa như nó. Một vài ví dụ về hashing trong cuộc sống thường ngày thực tế:

Mỗi cuốn nắn sách trong thư viện cũng được gán cho 1 ID tốt nhất, tự ID này ta có thể biết được địa chỉ đúng đắn của nó vào thư viện hoặc những người dùng đang mượn nó.

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

Trong những ví dụ trên, sách với sinh viên đã có mã hóa với một ID nhất, nghệ thuật đó Hotline là hashing.

bởi vậy ta cũng hoàn toàn có thể khái niệm hashing là chuyên môn biến đổi một khóa (key) thay đổi một số trong những nguyên ổn bằng cách dùng những công thức tân oán học. Công thức toán thù học tập này được triển khai trong một hàm gọi là hash function (hàm băm). Một key Khi qua cách xử lý của hàm băm sẽ sinh ra một trong những nguim duy nhất được call là mã băm (hash code).

Giả sử rằng bạn tất cả một đối tượng người sử dụng, cùng chúng ta một gán đến nó một ID nhằm dễ quản lý. Lúc gán mang lại đối tượng người sử dụng một ID thì một cặp key/value được hiện ra, cùng với key là ID cơ mà chúng ta gán cùng value đó là đối tượng người dùng được gán đến ID kia.

Để thực hiện Việc bên trên, dễ dàng là chúng ta có thể cần sử dụng mảng, trong lúc này key đó là chỉ số của mảng, chỗ lưu trữ đối tượng người tiêu dùng (value). Tuy nhiên, trong trường hòa hợp khi key quá to thì Việc cần sử dụng key thẳng làm chỉ số của mảng không còn tác dụng nữa, với bạn nên dùng hashing.

Sau khi hashing, cặp key/value (key đang dược chuyển đổi) được chứa vào một cấu tạo dữ liệu là bảng băm (hash table). Bằng phương pháp thực hiện key trong bảng băm, bạn cũng có thể truy vấn các phần tử trong bảng này vào thời gian O(1).

Hashing hoàn toàn có thể được thực hiện trong nhì bước:

Chuyển thay đổi khóa (key) thành số ngulặng (khóa bé dại hơn) dùng hàm băm. Khóa sau thời điểm thay đổi có thể được sử dụng như chỉ số nhằm đựng thành phần lúc đầu phía bên trong bảng băm.

Phần tử được chứa trong bảng băm rất có thể được truy vấn nhanh chóng qua khóa đã có được chuyển đổi.

hash_code = hash_function(key)

index = hash % array_size

Với phương pháp chuyển đồi này, hash_code là chủ quyền cùng với kích cỡ của mảng, kế tiếp quý giá của chính nó được thay đổi về index (index có mức giá trị từ 0 cho tới array_form size - 1).

Hàm băm (hash function)

Hàm băm là 1 hàm bất kỳ có thể được thực hiện để ánh xạ một cỗ tài liệu tất cả size tùy ý tới một bộ dữ liệu có kích cỡ cố định và thắt chặt bên trong bảng băm. Giá trị trả về bởi vì hàm băm được Điện thoại tư vấn là mã băm (hash code hoặc hash value).

Để đạt được một lý lẽ hashing tốt, ta cần được có một hàm băm giỏi cùng với phần đa ĐK cơ bạn dạng nlỗi sau:

Dễ tính toán thù.

Phân phối hận đồng nhất: Mỗi vị trí vào bảng được phân pân hận đếu cho mỗi key (khóa băm).

Ít xung đột: Sự xung hốt nhiên (collision) xẩy ra khi mà lại bao gồm những cặp phần tử không giống nhau được ánh xạ tới bình thường một mã băm.

Sự xung thốt nhiên vào bảng băm gây ảnh hưởng Khủng tới tính năng của nhiều loại cấu tạo dữ liệu này, cho nên vì vậy với bảng băm, bài toán sử dụng các chuyên môn để sút xung đột vào bảng là cực kỳ quan trọng đặc biệt.

Cùng coi ví dụ sau giúp thấy tại sao họ nên một hàm băm tốt

Giả sử bọn họ đề xuất đựng các chuỗi sau vào một bảng băm, sử dụng nghệ thuật hashing: "abcdef", "bcdefa", "cdefab" , "defabc".

Để tính toán thù các chỉ số mang đến câu hỏi lưu trữ các chuỗi, ta áp dụng hàm băm với các giải pháp thực hiện nlỗi sau.

Xem thêm: Mua Bán Xe Future Neo Fi 125 Cực Xinh, Giảm Giá, Khuyến Mãi Hấp

Cách triển khai sản phẩm công nghệ nhất:

Chỉ số cho từng chuỗi bởi tổng giá trị mã ASCII của mỗi phần cam kết trường đoản cú vào chuỗi.

call quý giá mã ASCII của một cam kết tự x là aval(x), istr(s) là tổng mức vốn mã ASCII của chuỗi s, ta có:

istr(abcdef) = aval(a) + aval(b) + aval(c) + aval(d) + aval(e) + aval(f) = 599

istr(bcdefa) = aval(b) + aval(c) + aval(d) + aval(e) + aval(f) + aval(a) = 599

istr(cdefab) = aval(c) + aval(d) + aval(e) + aval(f) + aval(a) + aval(b) = 599

istr(defabc) = aval(d) + aval(e) + aval(f) + aval(a) + aval(b) + aval(c) = 599

Với aval(a) = 97, aval(b) = 98, aval(c) = 99, aval(d) = 100, aval(e) = 101, aval(f) = 102

Và chỉ số được tính oán thù bằng phương pháp phân chia đem phần dư istr(s) mang đến số ký tự có trong chuỗi s.

gọi chỉ số của chuỗi s là idx(s) ta có:

idx(abcdef) = idx(bcdefa) = idx(cdefab) = idx(defabc) = 599 % 6 = 5

do vậy 4 chuỗi nghỉ ngơi bên trên sẽ được ánh xạ vào bình thường một chỉ số vào bảng băm.

Bởi bởi chỉ số của tất cả các chuỗi là giống nhau, bắt buộc bạn cũng có thể tạo thành một danh sách liên kết cùng với chỉ số đó nhằm cnhát những chuỗi vào.

*

Hình 1: Bảng băm ko tối ưu

Với bảng băm nghỉ ngơi trên, ta có thể nhận biết rằng nhằm truy cập vào trong 1 chuỗi trong bảng thì trong ngôi trường hòa hợp xấu duy nhất ta sẽ mất thời hạn là O(N). Do vậy cùng với bí quyết triển khai đầu tiên ta gồm một hàm băm không về tối ưu.

Cách tiến hành sản phẩm công nghệ 2:

Ta vẫn dùng bí quyết không giống nhằm tính toán thù chỉ số cho các chuỗi, với phương pháp này, chỉ số của một chuỗi sẽ bởi tổng mã ASCII của từng ký kết từ bỏ nhân cùng với lắp thêm tự thu xếp của cam kết trường đoản cú đó vào chuỗi. Rồi lấy tổng đó phân tách cho số nguyên tố bất kỳ. Trong bài này số được chọn là 2069 (số nguyên tố lớn nhất của tổng bé nhất).

Chuỗi

Tính toán trong hàm băm

Chỉ số

abcdef

(97*1 + 98*2 + 99*3 + 100*4 + 101*5 + 102*6) % 2069

38

bcdefa

(98*1 + 99*2 + 100*3 + 101*4 + 102*5 + 97*6) % 2069

23

cdefab

(99*1 + 100*2 + 101*3 + 102*4 + 97*5 + 98*6) % 2069

14

defabc

(100*1 + 101*2 + 102*3 + 97*4 + 98*5 + 99*6) % 2069

11

*

Hình 2: Bảng băm tối ưu hơn

Bảng băm - Hash table

Bảng băm là một loại cấu trúc dữ liệu được dùng để chứa cặp key/value. Nó sử dụng hàm băm để tính toán chỉ số, chỉ số này được dùng đến việc chèn hoặc tìm kiếm dữ liệu được suôn sẻ hơn. Với một bảng băm có một hàm băm được thực hiện xuất xắc thì trong trường hợp lý tưởng, việc tìm kiếm các phần tử vào bảng có thời gian là O(1).

Ta hãy cùng xem xét ví dụ sau:

Yêu cầu: Đếm số lần xuất hiện của các ký tự trong chuỗi sau: “ababcd”.

Cách tiếp cận đối chọi giản

Ta sẽ duyệt qua toàn bộ các phần tử của chuỗi và đếm số lần xuất hiện của từng ký tự. Độ phức tạp về thời gian của cách tiếp cận này là O(26*N) với N là độ dài của chuỗi và 26 là số ký tự có thể có trong chuỗi (số lượng ký tự vào bảng chữ cái tiếng anh).

string S = "ababcd"void countChar(string S){ for(char c = "a"; c Kết quả sau khoản thời gian chạy xác minh tại https://www.onlinegdb.com/online_c++_compiler .

*

Mã nguồn hoàn chỉnh để chạy cmùi hương trình ở bên trên có thể tìm thấy tại phía trên.

Cách tiếp cận tối ưu hơn

Sử dụng kỹ thuật hashing cho bài toán này. Ta dùng một mảng có kích thmong là 26 để chứa quý hiếm là số lần xuất hiện của một ký tự trong chuỗi.

Dùng hàm băm để tính toán ra chỉ số của ký tự vào chuỗi.

Duyệt qua toàn bộ chuỗi, và tăng giá trị của phần tử mảng có chỉ số tương ứng bằng với chỉ số của ký tự vừa được tính ở bcầu bên trên.

#include using namespace std;int C<26>;/* Hàm băm tính toán chỉ số của ký tự vào chuỗi */int hash_function(char c) return (c - "a");/* Hàm đếm số lần xuất hiện của một ký tự vào chuỗi */void count_char(string S) { for (int i = 0; i

Kết quả sau khoản thời gian chạy cmùi hương trình bên trên.

*

kết luận

Bởi vì hàm băm trả về một khóa có mức giá trị nhỏ tuổi hơn khóa gốc (là một số ngulặng to hoặc một chuỗi dài), vấn đề này dẫn đến sự việc hai khóa rất có thể gồm chung một quý giá.

Xem thêm: Chuyên Mua Bán Loa Bose Chính Hãng Hàng Cũ Bãi Hát Hay Giá Bán Rẻ Nhất

Tình huống Khi một phần tử bắt đầu được ckém vào bảng băm gồm khóa ánh xạ tới một vị trí đang bao gồm tài liệu (ánh xạ tới tầm thường một quý hiếm với một khóa khác) được Hotline là việc xung bỗng nhiên. Và bọn họ buộc phải giải quyết và xử lý vụ việc này bằng các chuyên môn giải quyết xung đột.


Chuyên mục: Blogs