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

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ả | HASHING 203 type Hnk node node record key info integer next link end var heads array of link t z link procedure initialize var i integer begin new z z .next z for i 0 to M-l do begin new heads i heads i 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 Ustsea rch y heads v mod M to find the first record with key v and successively set 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 ASEARCHINGEXAMPLE Hash 18517389375212515 if these keys are successively inserted into an initially empty table the following set of lists would result 0 12 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 204 CHAPTER 16 the M lists is equally likely to be searched and as in sequential list searching that the list searched is only traversed halfway on the average . The average length of the list examined not counting z in this example for unsuccessful search is 0- -4 2 2- -0 4 0 2 2 H-0 ll . This would be the average time for an unsuccessful search were the lists unordered by keeping them ordered we cut the time in half. For a successful search for one of the records in the table we assume that each record is equally likely to be sought seven of the keys would be found as the