Draw the hash table from Exercise using a table size of 17 and open addressing using linear probing.

Question:

Draw the hash table from Exercise using a table size of 17 and open addressing using linear probing.

Exercise

Draw the hash table that results from adding the following integers (34 45 3 87 65 32 1 12 17) to a hash table of size 11 using the division method and linked chaining.

Answer:

Step: 1 of 5

The hash function using division method is defined as:

Hashcode(key) = Math.abs (key) % p

Where p is the size of the table, 17.

The open addressing method uses linear probing for handling collisions. When an element hashes to a position x that is already occupied, then the position (x + 1) % s is tried. Here, s indicates the size of the table (17). If the obtained position has also been occupied then the position (x + 2) % s is tried. The hashing continues by adding the numbers in a series to the position x until an empty cell is obtained.

Step: 2 of 5

Following are the hash codes for the keys (34 45 3 87 65 32 1 12 17)

Hashcode(34) = Math.abs(34) % 17

= 0

Hashcode(45) = Math.abs(45) % 17

= 11

Hashcode(3) = Math.abs(3) % 17

= 3

Hashcode(87) = Math.abs(87) % 17

= 2

Hashcode(65) = Math.abs(65) % 17

= 14

Hashcode(32) = Math.abs(32) % 17

= 15

Hashcode(1) = Math.abs(1) % 17

= 1

Hashcode(12) = Math.abs(12) % 17

= 12

Hashcode(17) = Math.abs(17) % 17

= 0

Position 0 is occupied, so hash code is calculated for next position.

Hashcode(17) = Math.abs(0 + 1) % 17

= 1

Step: 3 of 5

Position 1 is occupied, so hash code is calculated for next position.

Hashcode(17) = Math.abs(0 + 2) % 17

= 2

Position 2 is occupied, so hash code is calculated for next position.

Hashcode(17) = Math.abs(0 + 3) % 17

= 3

Position 3 is occupied, so hash code is calculated for next position.

Step: 4 of 5

Hashcode(17) = Math.abs(0 + 4) % 17 = 4

Step: 5 of 5

Hash table obtained by adding the keys to the hash table using linear probing:

Click to Rate This Answer!
[Total: 0 Average: 0]

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.