# Thuật toán Algorithms (Phần 22)

Chia sẻ: Tran Anh Phuong | Ngày: | Loại File: PDF | Số trang:10

0
34
lượt xem
3

## Thuật toán Algorithms (Phần 22)

Mô tả tài liệu

Tham khảo tài liệu 'thuật toán algorithms (phần 22)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Thuật toán Algorithms (Phần 22)

1. HASHTNG 203 type link=fnode; node=record key, info: integer; next: link end; var heads: array [O..M] of link; t, z: link; procedure initialize; var i: integer; begin new(z); zt.next:=z; for i:=O to M-l do begin new(heads[i]); heads[i]f.next:=z end; end ; Now the procedures from Chapter 14 can be used as is, with a hash function used to choose among the lists. For example, listinsert(v, heads[v mod M] ) can be used to add something to the table, t:=listsearch(v, heads[v mod M]) to find the first record with key v, and successively set t:=listsearch(v, t) until t=z to find subsequent records with key v. For example if the ith letter in the alphabet is represented with the number i and we use the hash function h(k) = kmod M, then we get the following hash values for our sample set of keys with M = 11: Key: A S E A R C H I N G E X A M P L E Hash: 1 8 5 1 7 3 8 9 3 7 5 2 1 2 5 1 5 if these keys are successively inserted into an initially empty table, the follow- ing set of lists would result: 0 1 2 3 4 5 6 7 8 9 10 A M C E G H I A X N E R S A E L P Obviously, the amount of time required for a search depends on the length of the lists (and the relative positions of the keys in them). The lists could be left unordered: maintaining sorted lists is not as important for this application as it was for the elementary sequential search because the lists are quite short. For an “unsuccessful search” (for a record with a key not in the table) we can assume that the hash function scrambles things enough so that each of