TAILIEUCHUNG - PHÉP BIẾN ĐỔI KHÓA – HÀM BĂM part 2

. - Giá trị của hàm trả về vị trí của phần tử thêm vào hoặc 0 nếu bảng băm đầy. - Nếu đã có khóa k ở trong bảng thì hàm cho biết vị trí của khóa này trong bảng băm mà không thêm vào khóa này. - Phần tử ở vị trí 0 luôn là vị trí trống, nó được sử dụng để đảm bảo việc tìm kiếm luôn kết thúc thành công, nó đống vai trò như phần tử cầm canh. Function | - Procedure Initialize var i integer Begin For i 0 to M do T i .key free R M 1 End c. Thêm một khóa vào bảng băm. - Hàm THEM_KHOA k integer thực hiện việc thêm khóa k vào bảng băm. - Giá trị của hàm trả về vị trí của phần tử thêm vào hoặc 0 nếu bảng băm đầy. - Nếu đã có khóa k ở trong bảng thì hàm cho biết vị trí của khóa này trong bảng băm mà không thêm vào khóa này. - Phần tử ở vị trí 0 luôn là vị trí trống nó được sử dụng để đảm bảo việc tìm kiếm luôn kết thúc thành công nó đống vai trò như phần tử cầm canh. Function THEM_KHOA k integer integer Var i j integer Begin I H k 1 0 i M If T i .key k and T i .key free then begin ddungj độ timf đến phần tử kế tiếp repeat j i i T i .next until i 0 or T i .key k if i 0 then begin không tìm thấy repeat timf vị trí trúng r r-1 until T i .key free if r 0 then T j .next r i r end end if i 0 and T i .key k then begin T i .key k T i .next 0 End THEM_KHOA i End c Phương pháp băm kép Ví dụ ta có thể dùng một mảng các con trỏ chỉ đến các nút gốc của các cây tìm kiếm nhị phân và dúng các thủ tục chèn và tìm kiếm ở phần trước. Một sơ đồ phổ biến khác gọi là băm kép sẽ được mô tả tương tự như phương pháp dò tuyến tính chỉ khác là thay vì kiểm tra mỗi phần tử liên tiếp tại vị trí xung đột đó do đó số lần dò sẽ giảm đi so với dò tuyến tính chúng ta dùng một hàm băm thứ hai. Chú ý hàm băm thứ hai h2 phải được chọn cẩn thận ở một vài khía cạnh nếu không thì chương trình có thể không hoạt động tốt. Yếu tố thứ ba trong việc thiết kế bảng băm là việc chọn bảng băm. Dĩ nhiên là dáng điệu của hàm này ảnh hưởng đến tần số va chạm. Ví dụ hàm băm h Name Name 1 ở ví dụ trước không phải là sự chọn lựa tốt vì một vài kí tự như các chữ đầu của tên xuất hiện nhiều lần hơn các kí tự khác. Do đó danh sách liên kết của các tên bắt đầu bằng S sẽ dài hơn nhiều so với các danh sách chứa những tên bắt đầu bằng Z . Hiệu ứng chùm này làm cho việc tìm kiếm các tên bắt đầu bằng S lâu hơn bắt đầu bằng Z. Một hàm băm tốt hơn phân phối đến các tên trong bảng băm .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.