Exercise 6 Index   <<   >>


 

Modify function xiyC to use a different hash function hf . What happens to the number of comparisons?






















 z←x (hn xiyCSF hf) y;⎕io;h;hf;i;j;m;n;q
  ...
 :If 2=⎕nc'hf' ⋄ hf←{123457×⍵} ⋄ :EndIf                
                                      ⍝ hash function 
  ...
 :If 2=⎕nc'hn' ⋄ q←2*1+⌈2⍟m ⋄ :Else ⋄ q←hn m ⋄ :EndIf  
                                      ⍝ size of hash table
  ... 


_____________________

   n ← 1000×1 2 4 8 16 32

   {x y←↓?(2,⍵)⍴2e9 ⋄ x xiyC y}¨n
2006 3913 8014 13858 31127 59585

   {x y←↓?(2,⍵)⍴2e9 ⋄ x (⍬ xiyCSF{17×⍵}) y}¨n
1754 3682 7825 14491 29598 59315

   {x y←↓?(2,⍵)⍴2e9 ⋄ x (⍬ xiyCSF{17⊥(4⍴256)⊤⍵}) y}¨n
1783 3714 7396 14658 30369 59151