Question

For the input data 30, 20, 56, 75, 31, 19 and hash function h(K) = K mod 11:

Construct the open hash table.
Find the largest number of key comparisons in a successful search in this table.
Find the average number of key comparisons in a successful search in this table.
(it is an open hash table please )

Answer 1

To construct the open hash table, each key is placed in a slot determined by h(K) = K mod 11. The largest number of key comparisons in a successful search would be 3, and the average number of key comparisons would be approximately 1.83.

Step-by-step explanation:

To construct an open hash table using the hash function h(K) = K mod 11, we map each input data to a slot in the table based on the result of the hash function. Here is how the provided data is placed in the hash table:

• 30 mod 11 = 8 —> placed in slot 8
• 20 mod 11 = 9 —> placed in slot 9
• 56 mod 11 = 1 —> placed in slot 1
• 75 mod 11 = 9 —> since slot 9 is taken, place it in the next available slot, which is 10
• 31 mod 11 = 9 —> since slots 9 and 10 are taken, place it in the next available slot, which is 0
• 19 mod 11 = 8 —> since slot 8 is taken, place it in the next available slot, which is also slot 0 (since slot 9 is also taken)

The largest number of key comparisons in a successful search would be for the key that was placed last in the slot with the most collisions. In this case, that would be the key 19, which required 3 comparisons (including the comparison with itself when we finally find it).

The average number of key comparisons in a successful search is calculated by finding the average over all searches. This value would be the total number of comparisons made for each key (when it is searched for) divided by the number of keys:

(1 + 1 + 1 + 2 + 3 + 3) / 6 = 11 / 6 ≈ 1.83 key comparisons on average for a successful search.

Answer 2

To construct an open hash table using the given input data (30, 20, 56, 75, 31, 19) and the hash function h(K) = K mod 11, we'll perform the following steps:

The Steps

Initialize an array (hash table) of size 11.

Apply the hash function to each input number to determine its position in the hash table.

Handle collisions using an open addressing method like linear probing.

Let's illustrate this in Python:

# Function to perform open hashing with linear probing

def open_hashing(keys):

table_size = 11

hash_table = [None] * table_size

for key in keys:

index = key % table_size

while hash_table[index] is not None:

index = (index + 1) % table_size

hash_table[index] = key

return hash_table

# Input data

input_data = [30, 20, 56, 75, 31, 19]

# Construct the open hash table

hash_table = open_hashing(input_data)

print("Open Hash Table:", hash_table)

# Find the largest number of key comparisons in a successful search

largest_comparisons = max([(key % 11) + 1 for key in input_data])

print("Largest number of key comparisons in a successful search:", largest_comparisons)

# Find the average number of key comparisons in a successful search

average_comparisons = sum([(key % 11) + 1 for key in input_data]) / len(input_data)

print("Average number of key comparisons in a successful search:", averag