Khác biệt giữa bản sửa đổi của “Bảng băm”

n
chú thích, replaced: {{cite book → {{chú thích sách (2)
n (chú thích, replaced: {{cite book → {{chú thích sách (2))
Trong [[khoa học máy tính]], '''bảng băm''' là một cấu trúc dữ liệu sử dụng [[hàm băm]] để ánh xạ từ giá trị xác định, được gọi là khóa (ví dụ như tên của một người), đến giá trị tương ứng (ví dụ như số điện thoại của họ). Do đó, bảng băm là một [[mảng kết hợp]]. Hàm băm được sử dụng để chuyển đổi từ khóa thành chỉ số (giá trị băm) trong mảng lưu trữ các giá trị tìm kiếm.
 
Trong trường hợp lý tưởng, hàm băm luôn chuyển đổi các khóa khác nhau đến các chỉ số khác nhau. Tuy nhiên trong thực tế, điều này hiếm khi xảy ra (trừ khi các khóa là cố định: không có thêm khóa mới nào được bổ sung vào bảng sau khi tạo bảng). Thay vào đó, hầu hết các thiết kế bảng băm đều giả sử các khóa khác nhau có thể được băm vào cùng một giá trị (gọi là va chạm băm), và cung cấp cách giải quyết va chạm.
 
Trong một bảng băm có kích thước đủ lớn, thời gian trung bình cho mỗi lần tra cứu là độc lập với số lượng phần tử trong bảng. Nhiều thiết kế bảng băm cũng cho phép chèn thêm và xóa bỏ tùy ý của cặp khóa-giá trị trong thời gian trung bình (hoặc trừ dần) không đổi cho mỗi thao tác.<ref name="knuth">
{{citechú bookthích sách
| author = [[Donald Knuth]]
| title = The Art of Computer Programming'
| pages = 513–558
}}
</ref><ref name="CLRS">{{citechú bookthích sách
| authorlink = Thomas H. Cormen
| first = Thomas H.
==Ghi chú==
{{reflist}}
 
[[Thể loại:Giải thuật tìm kiếm]]
 
<!--Interwikies-->
 
[[Thể loại:Giải thuật tìm kiếm]]
 
[[ar:جدول هاش]]
986.568

lần sửa đổi