COMP1927 13s1

COMP1927 13s1 Final Exam

Computing 2

Question 8 (8 marks)

Consider a hash table of size 13 and a hash function:

int hash(int k) { return (k % 13); }

Consider inserting the following key values into an initially empty hash table in the order specified:

3  26  16  4  29  12  25  13  7  20

Show the final contents of the hash table for each of the following strategies for handling collisions:

1. Chaining

2. Linear probing

3. Double hashing, with a second hash function:

   int hash2(int k) { return (7 - (k % 7)); }
   

Now consider the following hash function which converts character strings to integer values in the range 0..N-1:

int hash3(char *k, int N)
{
	char *c;  int h = 0;

	for (c = k; *c != '\0'; c++) {
		h = h | *c;
	}
	return (h % N);
}

4. Explain briefly what is wrong with this hash function? What would be the result of using it on a hash table of size N=127?

Type the answer to this question into the file called q8.txt and submit it using the command:

submit q8