BẢNG BĂM LÀ GÌ

Giải vấn đề là tìm kiếm lãi giải. Kết quả tìm kiếm nhờ vào vào tốc độ xử lý, nhưng quan trọng hơn nhiều, là chiến lược thu gọn gàng không gian.

Bạn đang xem: Bảng băm là gì

Bạn sẽ xem: Bảng băm là gìBạn đã xem: Bảng băm là gì

Hàm băm (Hash function)

Hàm băm là 1 trong hàm ánh xạ tài liệu kỹ thuật số có kích thước bất kỳ thành dữ liệu kỹ thuật số có size cố định. Giá trị trả về của hàm điện thoại tư vấn là cực hiếm băm tuyệt mã băm, với cùng một độ dài tài liệu gọi là chiều dài băm.

Một cực hiếm băm cùng với chiều dài gắng định, ví dụ điển hình một chuỗi nhị phân 32 bits, có thể đại diện cho những số nguyên thường xuyên từ 0 tới 2³²-1, là cơ sở cho quá trình định lượng hóa. Với cùng 1 chiều dài băm với thuật toán băm ưng ý hợp, một hàm băm hoàn toàn có thể được áp dụng để định lượng hóa, thống kê giám sát chỉ số để truy vấn tức thì một bảng dữ liệu kích cỡ lớn. Thời hạn tìm kiếm phiên bản ghi không phụ thuộc vào kích thước của bảng theo số lượng bản ghi, nhưng tính bởi thời lượng đo lường và thống kê băm cộng với thời hạn xử lý một vài nghệ thuật sau định lượng. Không khí tìm kiếm trên cửa hàng dữ liệu cực đại được thu gọn gàng thành một vài bạn dạng ghi, thậm chí còn một phiên bản ghi. Một bảng dữ liệu với một triệu phiên bản ghi thu gọn không khí tìm kiếm vươn lên là một bạn dạng ghi sẽ nhanh hơn list tuần tự đối kháng thuần có kích cỡ tương đương, một triệu lần. Bảng tài liệu sử dụng hàm băm như vậy gọi là bảng băm.

Bảng băm (Hash table)

Bảng băm sử dụng hàm băm để đo lường chỉ số vào một trong những mảng. Chỉ số mảng cần sử dụng làm showroom đi vào một vùng tài liệu của bảng, rất có thể là một bạn dạng ghi, một vài phiên bản ghi, hoặc không có bản ghi nào. Trường thích hợp không có phiên bản ghi nghĩa là chưa có bản ghi nào dành riêng cho showroom ấy. Mỗi thành phần của mảng gọi là 1 trong khe(slot). Như vậy mảng là mảng của những khe được tiến công địa chỉ. Khe rất có thể chứa thẳng một bạn dạng ghi, trong trường hòa hợp này mảng khe chứa toàn cục dữ liệu của bảng. Trường phù hợp khác, khe chỉ cất tham chiếu mang đến một cấu trúc danh sách chứa các bản ghi. Một kết cấu danh sách “đựng” một vài phiên bản ghi hệt như một chiếc “xô”(bucket) đựng bản ghi và “treo” vào một showroom trên mảng khe. Khe nào không có bản ghi thì hoặc là không có xô treo(đó là tham chiếu- bé trỏ trỏ vào null) hoặc là treo một chiếc xô không(con trỏ trỏ vào một danh sách rỗng). Như vậy theo như hình dung call mảng khe là mảng xô cũng được. Không giống nhau là, mảng khe hàm ý mảng địa chỉ, còn mảng xô hàm ý mảng dữ liệu bảng. Bạn dạng ghi bắt buộc là tài liệu kiểu từ bỏ điển cùng với cặp khóa-giá trị. Vày vậy mảng thuộc dạng mảng kết hợp(associative array).

Tính toán chỉ số

Với mỗi khóa vào(key), hàm băm sẽ tạo ra một quý giá băm(hash). Chỉ số(index) sau đó được đo lường và thống kê tùy theo người xây đắp bảng, thông thường lấy phần dư của phép phân chia hash cho kích thước mảng(array_size)

hash = hashfunc(key)index = hash % array_size

Nếu cỡ mảng là lũy quá của 2 thì phần dư này rất có thể đạt được bởi mặt nạ bit, trong ngôn từ C, sử dụng phép toán "&" như sau

index = hash và (array_size-1);

Phép toán khía cạnh nạ bit làm cho tăng tốc độ thực hiện.

Xung đột khóa

Xung bỗng dưng khóa là ko tránh ngoài khi các khóa được băm ngẫu nhiên vào bảng. Mặc dù rằng phân phối khóa là đồng mọi trong bảng, như chúng ta đã biết về vấn đề sinh nhật, trường hợp 2500 khóa được băm vào một trong những triệu khe thì phần trăm gần 96% có tối thiểu hai khóa được băm vào và một khe. Bạn cũng có thể vận dụng cách làm (*) trong bài trước và tiện ích kcalc nhằm tính thử. Kết quả đúng chuẩn hơn là 95.6%. Bởi vì vậy những bảng băm phần đông cần các biện pháp cách xử lý xung bỗng dưng khóa.

Chọn hàm băm tốt

Yêu cầu cơ phiên bản là hàm băm phải đảm bảo an toàn phân phối đồng đều các giá trị băm. Cung cấp không đồng đều gây ra tăng xung đột nhiên và giảm công dụng của bảng do rất nhiều khóa bị dồn vào một trong những khe hoặc hiện tượng tụ đám của những khóa tiếp tục trong lúc lại thừa khoảng không chỗ không giống (hiện tượng tụ đám của các khóa tiếp tục làm giảm công dụng của bảng kiểu add mở được trình bày bên dưới). Việc phân phối cũng cần để ý đến sự nhất quán trong tổ chức cơ cấu bảng, chẳng hạn với bảng cần form size là lũy thừa của 2 thì không phù hợp cho thuật toán băm chỉ băm mọi khi kích thước bảng là số nguyên tố. Hàm băm mật mã là hàm băm xuất sắc cho bảng băm tuy rằng đề xuất trả giá về ngân sách tính toán.

Tính đồng đều phân phối khóa nhiều lúc khó bảo đảm an toàn trong thi công nhưng có thể đánh giá kết quả sử dụng bởi kiểm tra thống kê, như chu chỉnh Chi-bình phương theo tiêu chuẩn phù hợp Pearson với trả thiết qui luật pháp phân bố xác suất đồng phần đông rời rạc. Nội dung chi tiết kiểm định được trình diễn bên dưới.

Xem thêm: Người Tuổi Thìn Sinh Năm Bao Nhiêu? ? Là Con Gì? Phong ThủY Mã U SắC TuổI Thã¬N 2021

Hệ số mua (load factor)

Các vẻ bên ngoài bảng băm thông dụng

Bảng băm với list móc nối độc lập

Bảng băm với danh sách độc lập

Nguồn ảnh: wikipedia.org

Nếu phân phối khóa tương đối đồng đều, túi tiền thời lượng trung bình đến tìm kiếm phiên bản ghi chỉ dựa vào vào số khóa trung bình trên một khe, tức là hệ số tải. điểm yếu kém của phương pháp danh sách móc nối hòa bình là làm cho hoạt động cache kém hiệu quả(cache là tàng trữ một bạn dạng sao của dữ liệu được tham chiếu trong bộ nhớ lưu trữ lưu trữ sệt biệt, để cơ mà tái truy vấn nhanh hơn). Để tương khắc phục yếu điểm này, một bí quyết thức cải tiến là đưa phiên bản ghi đầu tiên của danh sách vào hẳn trong mảng khe nắm cho nhỏ trỏ trường đoản cú mảng như trước.

Bảng băm với danh sách có bản ghi trước tiên chứa trong mảng khe

Nguồn ảnh: wikipedia.org

Bảng băm showroom mở

Minh họa bảng băm địa chỉ cửa hàng mở với thăm dò tuyến đường tính(bước dò hỏi =1). Đầu tiên "John Smith" được băm vào địa chỉ 152 vốn trước sẽ là trống. Tiếp theo "Sandra Dee" được băm, hiệu quả là xung hốt nhiên ở showroom 152, dò hỏi phải dịch rời xuống dưới 1 đơn vị và tạm dừng ở địa chỉ 153 còn trống. Tiếp nối "Ted Baker" được băm với kết quả 153, phiên bản thân giá trị này không xung bỗng về băm tuy thế phương pháp showroom mở đã sắp xếp "Sandra Dee" sinh sống đó, đề xuất "Ted Baker" cần được để xuống dưới vào địa chỉ 154 còn trống.

Nguồn ảnh: wikipedia.org

Kiểu bảng này được gọi là bảng băm địa chỉ mở (Open addressing). Toàn bộ các bản ghi được chứa trong mảng khe. Lúc 1 khóa mới được chèn, khóa sẽ tiến hành băm vào một khe. Nếu khe này là trống thì add khe này sẽ là showroom của khóa mới, ví như không, một chuỗi thăm dò tiến hành kiểm tra những khe cho tới khi một khe trống được tra cứu thấy, và địa chỉ cửa hàng cho khóa được xác định. Địa chỉ nhìn toàn diện không được xác minh bởi băm và bao gồm tính “mở” như vậy nên được gọi là add mở. Đối với vận động tìm kiếm bản ghi, các khe cũng được quét theo trình từ bỏ tương tự, cho tới khi phiên bản ghi phương châm được tìm thấy, hoặc search kiếm đi vào một trong những khe trống, cho thấy thêm rằng không tồn tại khóa như vậy trong bảng. Có 3 các loại thăm dò

Bảng băm mẫu mã chim Cúc cu

Kiểu bảng này là 1 biến thể của giải pháp địa chỉ cửa hàng mở. Trong trường hợp xấu nhất, thời hạn tra cứu là hằng số. Hằng số này được hình thành bởi tích lũy dần trong quy trình tạo lập bảng, tạo ra bởi các chuỗi hoạt động chèn và xóa các phiên bản ghi như mô tả chi tiết dưới đây. Bảng bảo trì hai hay các hàm băm. Để dò tìm kiếm một phiên bản ghi, hàm băm đầu tiên được sử dụng. Nếu như khóa ko được search thấy, hàm băm thiết bị hai được sử dụng, và cứ thế. Lúc chèn vào một bạn dạng ghi, hàm băm đầu tiên được sử dụng, giả dụ khóa được băm vào trong 1 khe trống, bạn dạng ghi new này coi như tạm thời nằm ngơi nghỉ đó. Giả dụ khóa được băm vào trong 1 khe đã được chỉ chiếm chỗ bởi vì một bạn dạng ghi khác trước đó, nghĩa là có xung đột nhiên xảy ra, thì hàm băm sản phẩm hai được áp dụng để ánh xạ nó cho tới một khe khác. Nếu toàn bộ các hàm băm đã được sử dụng tính đến hàm băm cuối cùng mà xung đột vẫn còn đấy xảy ra, thì khóa xung tự dưng trong khoảng cuối này vẫn bị di chuyển để nhịn nhường chỗ đến khóa mới. Chúng ta nhớ rằng tại thời đặc điểm đó khóa new đã áp dụng hết hàm băm. Mà lại điều này có thể là khác đối với khóa cũ bị dịch chuyển và khóa này hoàn toàn có thể có thời cơ tìm được một nơi trống, nhưng phiên bản thân nó không nhận thức được vấn đề này và nó đơn giản lần lượt sử dụng những hàm băm bước đầu từ hàm băm vật dụng nhất, không tính hàm băm mà chuyển nó tới vị trí lúc này đang xung đột nhiên thì được xem là sử dụng rồi, nhằm tìm khu vực trú chân khác. Giả dụ xung bỗng dưng lại liên tục xảy ra thì các chuỗi giải pháp xử lý cứ như thế tiếp tục lặp lại cho tới khi không hề xung đột. Họ hình dung là các bạn dạng ghi bị dịch chuyển (bị xóa và gửi đi vị trí khác) theo dây chuyền. Các chuỗi vượt trình này còn có xu hướng dồn các bản ghi vào khu vực trống. Thử tưởng tượng một viễn cảnh tồi tệ, đó là 1 trong vòng lặp lẩn quẩn xảy ra, một vài khóa cứ quay đi trở lại vị trí cũ. Đó là có một vài khóa bên cạnh đó bị chập trên toàn bộ các hàm băm, cùng số khóa này to hơn số hàm băm, mặc dù giả sử từng hàm băm bảo vệ băm một khóa khăng khăng vào các vị trí không giống nhau, như thế cũng không được chỗ cho số khóa như vậy, và quá trình cứ trao đi đổi lại vị trí với vòng lặp vô tận. Tuy nhiên bọn họ biết rằng với vấn đề Sinh nhật, hai quý giá băm tự dưng xung thốt nhiên thì dễ tuy nhiên để một quý hiếm băm thứ ba cũng xung bỗng nhiên vào quý giá băm ấy lúc này đã được xem như là xác định, là vụ việc Sinh nhật “Cùng ngày sinh như bạn”, có xác suất nhỏ tuổi đáng kể. Cụ thì sự xung tự dưng đồng thời trên toàn bộ các hàm băm của toàn bộ số khóa này là 1 trong những biến cố hầu hết không xảy ra. Cùng với số hàm băm đầy đủ lớn, sẽ không có vấn đề, nghĩa là những khóa đã tìm vị trí trú cùng sử dụng tất cả các khe của bảng. Bây giờ nếu còn nhu cầu thêm khóa mới, bảng vẫn được biến đổi kích cỡ, tùy chỉnh cấu hình lại. Phong cách bảng này tận dụng không khí bảng buổi tối ưu. Tình huống xấu nhất về thời hạn tra cứu giúp một bạn dạng ghi là nhằm tìm được bản ghi này, sự tra cứu đề xuất đi qua toàn bộ các hàm băm, đó là thời gian hằng số đối với cả các ngôi trường hợp do vậy vì tống số hàm băm là không đổi.

Kiểm định thống kê bảng băm

Vì bảng băm xuất sắc chỉ tất cả tối nhiều 3 khóa trên một khe mà lại tiêu chuẩn tương xứng Pearson yêu ước tần số quan tiếp giáp ≥ 5 nên bọn họ nhóm mỗi 5 khe thành một khoảng. Để đơn giản cho ví dụ, bọn họ xem xét một bảng nhỏ có 80 khóa, 40 khe, như vậy hệ số tải là 80/40=2. Bảng có kiểu list móc nối. Chia không khí bảng thành 8 khoảng, mỗi khoảng trung bình 10 khóa.