Finding average # of probes for linear hashing.
2 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
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 Commenti
Risposte (0)
Vedere anche
Categorie
Scopri di più su Dictionaries in Help Center e File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!