Finding average # of probes for linear hashing.

Question

Nicholas Colburn 2013-3-20

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/67878-finding-average-of-probes-for-linear-hashing

So I'm trying to find the average # of probes for inserting elements into a hash table using linear hashing; a probe being the amount of spaces on the table the hash function has to visit. I'm pretty sure my coding is correct, but I'm posting it here to have someone with more experience gleam over it. Here is the code for the average probing:

      %Inputs: seq1, array of size m generated from random numbers on interval [0 c] with       c=10000 
      %      : seq2, array of size m generated from random numbers on interval [c 2c]
      %      : hash, the specified hashing type either 'linear' or 'double'
      %      : a, (alpha) the specified load-factor where a<1
      %      : m, hashtable size where m=9973
      function [ avProbe ] = FindAveragePrb4Insert(seq1,seq2,a,hash,m)
      hash1 = MakeAHashTable(seq1,a,m); %creates 2 hashtables of load alpha
      hash2 = MakeAHashTable(seq1,a,m);
      probes = zeros();
      index = 1;
      numPrb = 1;
      if strcmp(hash,'linear')    
          while index <= m
              for i=0:m
                  k = seq2(index);
                  j = mod(k+i,m)+1;
                  if mod(index,2) ~= 0
                      if isnan(hash2(j)) == true
                          hash2(j) = k;
                          index = index+1;
                          probes(end+1) = numPrb;
                          numPrb = 1;
                          break;
                      else
                          numPrb = numPrb+1;
                      end
                  else
                      if isnan(hash1(j)) == true
                          hash1(j) = k;
                          index = index+1;
                          probes(end+1) = numPrb;
                          numPrb = 1;
                          break;
                      else 
                          numPrb = numPrb+1;
                      end 
                  end
              end
          end
          avProbe = sum(probes)/(length(probes)-1);
      end
      if strcmp(hash,'double')
          while index <= m
              for i=0:m
                  k = seq2(index);
                  j = mod(k+(i.*(1+mod(k,m-1))),m)+1;
                  if mod(index,2) ~= 0
                      if isnan(hash2(j)) == true
                          hash2(j) = k;
                          index = index+1;
                          probes(end+1) = numPrb;
                          numPrb = 1;
                          break;
                      else
                          numPrb = numPrb+1;
                      end
                  else
                      if isnan(hash1(j)) == true
                          hash1(j) = k;
                          index = index+1;
                          probes(end+1) = numPrb;
                          numPrb = 1;
                          break;
                      else 
                          numPrb = numPrb+1;
                      end 
                  end
              end
          end
          avProbe = sum(probes)/(length(probes)-1);
      end

**CODE FOR MAKEAHASHTABLE FUNCTION****

%Inputs: seq1, array of size m generated from random numbers on interval [0 c] with c=10000
%      : a, (alpha) the specified load-factor where a<1
%      : m, hashtable size where m=9973
%Outputs: T, hashtable created from seq1 and load-factor a
function [ T ] = MakeAHashTable(seq1,a,m)
n = floor(a.*m);
T = NaN(1,m); %creates table T of size m filled with NaNs
i=0;
index=1;
while i<=m && n>0
    k = seq1(index);
    j = mod(k+i,m)+1; %calculates hash key from the function (k+i)mod m
    if isnan(T(j))    %check for empty table slot
        T(j) = k;
        n=n-1;
        i=0;
        index=index+1;
    else i=i+1;
    end
end  
end