Finding average # of probes for linear hashing.
2 views (last 30 days)
Show older comments
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
0 Comments
Answers (0)
See Also
Categories
Find more on Dictionaries in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!