Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Bảng băm

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

87
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Bảng băm" cung cấp cho người học các kiến thức: Bảng băm mở (Bảng băm, hàm băm, xung đột, một số hàm băm thông dụng), bảng băm đóng (Băm lại tuyến tính, băm lại bình phương, băm lại bằng cách tạo vùng mới). Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Bảng băm

26/03/12 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CHƢƠNG V: BẢNG BĂM 1. Bảng băm mở 1.1. Bảng băm 1.2. Hàm băm 1.3. Xung đột 1.4. Một số hàm băm thông dụng 2. Bảng băm đóng 2.1. Băm lại tuyến tính. 2.2. Băm lại bình phương 2.3. Băm lại bằng cách tạo vùng mới 1
26/03/12 1. Bảng băm mở 1. Bảng băm mở Hash Tables - Structure  Bảng băm (Hash Table): • Simplest case: - Mảng B gồm m phần tử • Assume items have integer keys in the range 1 .. m • Use the value of the key itself -Lưu trữ chỉ số định vị phần tử dữ liệu có khóa to select a slot in a direct access table phân biệt thuộc tập số nguyên { 0,1,2…m-1} in which to store the item • To search for an item with key, k, just look in slot k • If there’s an item there, you’ve found it • If the tag is 0, it’s missing. • Constant time, O(1) 1. Bảng băm mở 1. Bảng băm mở Hash Tables - Relaxing the constraints  Hàm băm • Keys are integers (Hash function): • Need a hash function h( key )  integer H(x) cho giá trị là một chỉ số phần tử của B ie one that maps a key to an integer • Applying this function to the key produces an address • If h maps each key to a unique integer in the range 0 .. m-1 then search is O(1) 2
26/03/12 1. Bảng băm mở 1. Bảng băm mở  Xung đột (collision): Xung đột: Tables - Hash Collision handling – x1x2 nhưng H(x1)=H(x2) • Collisions • Occur when the hash function maps two different keys to the same address • The table must be able to recognise and resolve this • Recognise • Store the actual key with the item in the hash table • Compute the address • k = h( key ) • Check for a hit • if ( table[k].key == key ) then hit else try next entry We’ll look at various • Resolution “try next entry” schemes • Variety of techniques 1. Bảng băm mở 1. Bảng băm mở Xung đột: Hash Tables - Linked lists  Giải quyết: • Collisions - Resolution  Linked list attached – liên kết các danh sách có các khóa khác to each primary table slot nhau nhưng có cùng giá trị hàm băm • h(i) == h(i1) • h(k) == h(k1) == h(k2) thành một danh sách • Searching for i1 • Calculate h(i1) – liên kết trong bẳng băm B sẽ trỏ tới danh • Item in table, i, sách đầu tiên. doesn’t match • Follow linked list to i1 • If NULL found, key isn’t in table 3
26/03/12 1. Bảng băm mở 1. Bảng băm mở  Hàm gấp chia số nguyên đó thành một số Một số hàm băm thông dụng: đoạn tùy chọn, sau đó kết hợp  Hàm cắt bỏ bỏ bớt một phần nào đó của  Ví dụ: Số các hàng lẻ: 465 và số các hàng khóa. chẵn: 821, vậy H(x)=465+821=1286. – Ví dụ: x=842615, bỏ bớt chẳng hạn các – Nhận xét: Tính chất thứ hai có thể thỏa mãn tốt chữ số hàng lẻ (1,3,5…), số còn lại sẽ là hơn 821. Vậy H(x) = H(842615) = 821. – Nhận xét: khó có phân bố đều. 1. Bảng băm mở 1. Bảng băm mở  Hàm phần dƣ của phép chia x/m Hash Tables - Reducing the range to [ 0, m )  Nên chọn m là số nguyên tố.  Division • Use a mod function h(k) = k mod m – Nhận xét: Các cách lấy phần dư cho khả năng • Choice of m? • Powers of 2 are generally not good! tránh hiện tượng xung đột h(k) = k mod 2n k mod 28 selects these bits selects last n bits of k 0110010111000011010 • All combinations are not generally equally likely • Prime numbers close to 2n seem to be good choices eg want ~4000 entry table, choose m = 4093 4
26/03/12 2. Bảng băm đóng 2. Bảng băm đóng  Bảng băm mở: chỉ dùng để lưu trữ các liên Các phƣơng pháp xử lý: kết trỏ đến các thành phần dữ liệu có khóa a) Băm lại tuyến tính tương ứng. Hi (x) = (H(x)+i) mod m  Bảng băm đóng: bảng băm mà mỗi thành – Nhận xét: Các giá trị hàm băm xếp phần của nó lưu trữ chính các thành phần thành từng đoạn con, nên việc tìm kiếm dữ liệu. ví trí rỗng sẽ rất chậm. 2. Bảng băm đóng 2. Bảng băm đóng Hash Tables - Re-hash functions b) Băm lại bình phương  The re-hash function Hi(x) = ( H(x)+i2) mod m • Many variations Hash Tables - Re-hash functions • Linear probing  The re-hash function • h’(x) is +1 • Many variations • Go to the next slot • Quadratic probing until you find one empty • h’(x) is c i2 on the ith probe • Avoids primary clustering • Secondary clustering occurs • Can lead to bad clustering • All keys which collide on h(x) follow the same sequence • Re-hash keys fill in gaps • First between other keys and exacerbate • a = h(j) = h(k) the collision problem • Then a + c, a + 4c, a + 9c, .... • Secondary clustering generally less of a problem 5
26/03/12 2. Bảng băm đóng c) Băm lại bằng cách tạo vùng mới  Ngoài bảng B cần tạo ra một vùng không gian mới Hash Tables - Overflow area  Overflow area • Linked list constructed in special area of table called overflow area • h(k) == h(j) • k stored first • Adding j • Calculate h(j) • Find k • Get first slot in overflow area • Put j in it • k’s pointer points to this slot • Searching - same as linked list 6