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 dựa vào vào tốc độ xử lý, nhưng quan trọng đặc biệt hơn nhiều, là kế hoạch thu gọn gàng không gian.

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

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

Hàm băm (Hash function)

Hàm băm là một trong những hàm ánh xạ dữ liệu kỹ thuật số tất cả kích thước ngẫu nhiên thành tài liệu kỹ thuật số có form size cố định. Quý giá trả về của hàm gọi là giá trị băm tuyệt mã băm, với cùng 1 độ 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 núm định, ví dụ điển hình một chuỗi nhị phân 32 bits, rất có thể đại diện cho những số nguyên tiếp tục từ 0 tới 2³²-1, là cơ sở cho quá trình định lượng hóa. Với 1 chiều lâu năm băm với thuật toán băm ưa thích hợp, một hàm băm hoàn toàn có thể được thực hiện để định lượng hóa, tính toán chỉ số để truy vấn ngay tức khắc một bảng dữ liệu size lớn. Thời hạn tìm kiếm bạn dạng ghi không phụ thuộc kích thước của bảng theo số lượng bản ghi, mà lại tính bằng thời lượng giám sát và đo lường băm cùng với thời hạn xử lý một vài chuyên môn sau định lượng. Không gian tìm kiếm trên cơ sở dữ liệu cực to được thu gọn thành một vài bạn dạng ghi, thậm chí là một bản ghi. Một bảng tài liệu với một triệu bạn dạng ghi thu gọn không khí tìm kiếm trở thành một bản ghi sẽ nhanh hơn danh sách tuần tự solo thuần có form size tương đương, một triệu lần. Bảng dữ liệu sử dụng hàm băm như thế gọi là bảng băm.

Bảng băm (Hash table)

Bảng băm áp dụng hàm băm để giám sát chỉ số vào trong 1 mảng. Chỉ số mảng dùng làm địa chỉ đi vào một trong những 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 bạn dạng ghi, hoặc ko có phiên bản ghi nào. Trường hợp không có bạn dạng ghi nghĩa là không có bản ghi nào dành riêng cho add ấy. Mỗi bộ phận của mảng gọi là một khe(slot). Do vậy mảng là mảng của những khe được đánh địa chỉ. Khe rất có thể chứa thẳng một bản ghi, trong trường đúng theo này mảng khe chứa cục bộ dữ liệu của bảng. Trường hợp khác, khe chỉ đựng tham chiếu đến một cấu tạo danh sách cất các phiên bản ghi. Một cấu trúc danh sách “đựng” một vài bản ghi hệt như một dòng “xô”(bucket) đựng bản ghi cùng “treo” vào một địa chỉ cửa hàng trên mảng khe. Khe nào không có bản ghi thì hoặc là không tồn tại xô treo(đó là tham chiếu- nhỏ trỏ trỏ vào null) hay những treo một chiếc xô không(con trỏ trỏ vào một trong những danh sách rỗng). Như vậy theo 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 tài liệu bảng. Phiên bản ghi cần là dữ liệu kiểu tự điển cùng với cặp khóa-giá trị. Vày vậy mảng nằm trong 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ý hiếm băm(hash). Chỉ số(index) sau đó được đo lường và tính toán tùy theo người xây dựng bảng, thường thì lấy phần dư của phép chia hash cho kích thước mảng(array_size)

hash = hashfunc(key)index = hash % array_size

Nếu khuôn khổ mảng là lũy thừa của 2 thì phần dư này có thể đạt được bằng mặt nạ bit, trong ngôn ngữ C, thực hiện phép toán "&" như sau

index = hash & (array_size-1);

Phép toán phương diện nạ bit làm cho tăng vận tốc thực hiện.

Xung bỗng nhiên khóa

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

Xem thêm: Cách Quấn Khăn Rằn Đi Phượt, Cách Quàng Khăn Rằn Nam Bộ Đẹp Và Đơn Giản

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

Hệ số download (load factor)

Các giao diện 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 trưng bày khóa tương đối đồng đều, giá thành thời lượng trung bình cho tìm kiếm bản ghi chỉ phụ thuộc vào số khóa mức độ vừa phải trên một khe, tức là hệ số tải. điểm yếu của cách thức danh sách móc nối chủ quyền là có tác dụng cho chuyển động cache hèn hiệu quả(cache là tàng trữ một bản sao của dữ liệu được tham chiếu trong bộ lưu trữ lưu trữ đặc biệt, để mà lại tái truy cập nhanh hơn). Để khắc phục nhược điểm này, một phương pháp thức đổi mới là đưa bạn dạng ghi đầu tiên của danh sách vào hẳn vào mảng khe thế cho bé trỏ từ bỏ mảng như trước.

Bảng băm với danh sách có bạn dạng ghi đầu tiên chứa trong mảng khe

Nguồn ảnh: wikipedia.org

Bảng băm địa chỉ mở

Minh họa bảng băm địa chỉ cửa hàng mở với thăm dò con đườ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 sau "Sandra Dee" được băm, kết quả là xung thốt nhiên ở showroom 152, dò hỏi phải di chuyển xuống bên dưới 1 đơn vị chức năng và dừng lại ở showroom 153 còn trống. Sau đó "Ted Baker" được băm với hiệu quả 153, bạn dạng thân giá bán trị này sẽ không xung hốt nhiên về băm tuy vậy phương pháp add mở đã sắp xếp "Sandra Dee" làm việc đó, đề nghị "Ted Baker" phải được để xuống bên dưới vào địa chỉ cửa hàng 154 còn trống.

Nguồn ảnh: wikipedia.org

Kiểu bảng này được hotline là bảng băm địa chỉ cửa hàng mở (Open addressing). Toàn bộ các bản ghi được chứa trong mảng khe. Khi 1 khóa new được chèn, khóa sẽ được băm vào trong 1 khe. Giả dụ khe này là trống thì showroom khe này vẫn là địa chỉ cửa hàng của khóa mới, ví như không, một chuỗi thăm dò triển khai kiểm tra những khe tính đến khi một khe trống được search thấy, và showroom cho khóa được xác định. Địa chỉ nhìn bao quát không được xác định bởi băm và gồm tính “mở” như vậy nên được gọi là add mở. Đối với chuyển động tìm kiếm bạn dạng ghi, các khe cũng rất được quét theo trình từ tương tự, cho tới khi bạn dạng ghi kim chỉ nam được tìm thấy, hoặc search kiếm đi vào một trong những khe trống, cho biết rằng không tồn tại khóa như vậy trong bảng. Tất cả 3 loại thăm dò

Bảng băm loại chim Cúc cu

Kiểu bảng này là 1 biến thể của giải pháp add mở. Trong trường phù hợp xấu nhất, thời gian tra cứu là hằng số. Hằng số này được hình thành vì chưng tích lũy dần dần trong quá trình tạo lập bảng, gây ra bởi những chuỗi vận động chèn cùng xóa các bản ghi như tế bào tả chi tiết dưới đây. Bảng gia hạn hai hay các hàm băm. Để dò search một bản ghi, hàm băm trước tiên được sử dụng. Nếu khóa không được tìm thấy, hàm băm thứ hai được sử dụng, và cứ thế. Lúc chèn vào một phiên bản ghi, hàm băm thứ nhất được sử dụng, ví như khóa được băm vào một trong những khe trống, phiên bản ghi bắt đầu này coi như tạm thời nằm sinh sống đó. Nếu khóa được băm vào trong 1 khe đã được chỉ chiếm chỗ do một bạn dạng ghi khác trước đây đó, nghĩa là tất cả xung bỗng nhiên xảy ra, thì hàm băm đồ vật hai được thực hiện để ánh xạ nó tới một khe khác. Nếu tất cả các hàm băm đã được sử dụng cho tới hàm băm sau cuối mà xung đột vẫn còn đó xảy ra, thì khóa xung bỗng nhiên trong khoảng cuối này đã bị di chuyển để nhường nhịn chỗ đến khóa mới. Bọn họ nhớ rằng trên thời điểm đó khóa bắt đầu đã sử dụng hết hàm băm. Tuy thế điều này hoàn toàn có thể là khác đối với khóa cũ bị dịch rời và khóa này hoàn toàn có thể có cơ hội tìm được một địa điểm trống, nhưng phiên bản thân nó không nhận thức được vấn đề đó và nó dễ dàng và đơn giản lần lượt sử dụng những hàm băm bước đầu từ hàm băm trang bị nhất, bên cạnh hàm băm mà chuyển nó cho tới vị trí bây giờ đang xung bỗng thì được tính là sử dụng rồi, nhằm tìm nơi trú chân khác. Nếu như xung chợt lại liên tiếp xảy ra thì những chuỗi cách xử lý cứ như thế thường xuyên lặp lại cho tới khi không hề xung đột. Chúng ta hình dung là các phiên bản ghi bị di chuyển (bị xóa và chuyển đi vị trí khác) theo dây chuyền. Những chuỗi vượt trình này còn có xu phía dồn các bạn dạng ghi vào chỗ trống. Test tưởng tượng một viễn ảnh tồi tệ, đó là một trong vòng lặp quẩn quanh xảy ra, một vài khóa cứ xoay đi quay lại vị trí cũ. Đó là có một trong những khóa đồng thời bị chập trên toàn bộ các hàm băm, và số khóa này to hơn số hàm băm, mặc dù giả sử mỗi hàm băm bảo đảm an toàn băm một khóa khăng khăng vào những vị trí khác nhau, như vậy cũng không được chỗ mang đến số khóa như vậy, và quy trình cứ trao đi thay đổi lại địa chỉ 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 cực hiếm băm thiên nhiên xung hốt nhiên thì dễ nhưng để một quý giá băm thứ cha cũng xung bỗng nhiên vào giá trị băm ấy lúc này đã được xem như là xác định, là sự việc Sinh nhật “Cùng ngày sinh như bạn”, gồm xác suất bé dại đáng kể. Rứa thì sự xung đột đồng thời trên toàn bộ các hàm băm của tổng thể số khóa này là một biến cố đa số không xảy ra. Với số hàm băm đầy đủ lớn, sẽ không có vấn đề, nghĩa là các khóa đang tìm địa điểm trú cùng sử dụng tất cả các khe của bảng. Lúc này nếu còn yêu cầu thêm khóa mới, bảng đang được đổi khác kích cỡ, tùy chỉnh cấu hình lại. đẳng cấp bảng này tận dụng không khí bảng buổi tối ưu. Tình huống xấu tốt nhất về thời gian tra cứu vớt một phiên bản ghi là để tìm được bạn dạng ghi này, sự tra cứu yêu cầu đi qua toàn bộ các hàm băm, đó là thời gian hằng số với tất cả các ngôi trường hợp vì thế vì tống số hàm băm là ko đổi.

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

Vì bảng băm giỏi chỉ có tối đa 3 khóa bên trên một khe mà tiêu chuẩn tương xứng Pearson yêu mong tần số quan gần kề ≥ 5 nên bọn họ nhóm từng 5 khe thành một khoảng. Để dễ dàng và đơ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 thông 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.