Suppose there are n keys and m values for hash function h. for example, if n = 1

Question

Suppose there are n keys and m values for hash function h. for example, if n = 10, m = 10, we have keys and relative hash value as following:

X = 8, h(x) = 1
X =12, h(x) =0
X = 14, h(x)=1
X = 17, h(x)=3
X = 33, h(x)=9
X = 41, h(x)=0
X =43, h(x)=2
X = 47, h(x)=1
X = 60, h(x)=7
X =88, h(x)=4

Suppose we have a Java function h(x) for keys x which are integers, and where h(x)?{0,1,…,m-1} for all x, so m is the table size. Suppose key is a Java array of size n declared as int[] key = new int[n] that contains the given keys key[j] to be hashes, 0<=j<=n

Write a Java method that runs in linear time in n and return the number of colliding pairs for the keys in the array key. Assume that the hash function h and its number m of values are given globally.

Explanation / Answer

// hash function
public static double h(int x);

// m is table size, key is given keys to be hashed
public int countCollisions(int[] key, int m)
{
// store counts of mappings
int[] counts = new int[m];
for(int x : key)
counts[h(x)]++;
// add collisions to output
int output = 0;
for(int y : counts)
if(y > 1)
output += y-1;
return output;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.