Write a java program to implement the following algorithms for Open Addressing technique Hash Table data structure. (Use a simple array of integers to store integer key values only). HASH-INSERT(T,k) HASH-SEARCH(T, k) i = 0 repeat j = h(k, i) if T[j] == NIL T[j] = k return j else i = i + 1 until i == m 661 i = 0 repeat j = h (k, i) if T[j] == k return j i=i+1 until T[j] == NIL or i = m return NIL
Write a java program to implement the following algorithms for Open Addressing technique Hash Table data structure. (Use a simple array of integers to store integer key values only). HASH-INSERT(T,k) HASH-SEARCH(T, k) i = 0 repeat j = h(k, i) if T[j] == NIL T[j] = k return j else i = i + 1 until i == m 661 i = 0 repeat j = h (k, i) if T[j] == k return j i=i+1 until T[j] == NIL or i = m return NIL
Related questions
Question
![Task - 1:
Write a java program to implement the following algorithms for Open Addressing techniques for
Hash Table data structure. (Use a simple array of integers to store integer key values only).
HASH-SEARCH(T, k)
HASH-INSERT (T, k)
i = 0
repeat
j = h (k, i)
if T[j] == NIL
T[j] = k
return j
else i = i + 1
●
i = 0
repeat
until i == m
error “hash table overflow"
For both algorithms, to compute the index j, write the following methods:
getLinear ProbIndex (key, i)
getQuadraticProbIndex
● get DoubleHash (key, i)
(key, i)
j = h (k, i)
if T[j] == k
return j
i = i + 1
until T[j] == NIL or i = m
return NIL
Linear Probing index is computed using following hash function:
h(k, i) = (h₁(k) + i) mod m
h₁(k)= k mod m
Quadratic probing index is computed using following hash function:
h(k, i) = (h₁(k) + i²) mod m
h₁(k)= k mod m
Double hashing index is computed using following hash function:
h(k, i) = (h₁(k) + i h₂(k)) mod m
h₁(k)= k mod m
h₂(k) = 1 + (k mod m - 1)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F9b63d5f0-a313-4df7-92fd-2acb696a8a17%2Faddbe216-d580-4801-ad34-8b79cd4208cd%2Fhxksjks_processed.png&w=3840&q=75)
Transcribed Image Text:Task - 1:
Write a java program to implement the following algorithms for Open Addressing techniques for
Hash Table data structure. (Use a simple array of integers to store integer key values only).
HASH-SEARCH(T, k)
HASH-INSERT (T, k)
i = 0
repeat
j = h (k, i)
if T[j] == NIL
T[j] = k
return j
else i = i + 1
●
i = 0
repeat
until i == m
error “hash table overflow"
For both algorithms, to compute the index j, write the following methods:
getLinear ProbIndex (key, i)
getQuadraticProbIndex
● get DoubleHash (key, i)
(key, i)
j = h (k, i)
if T[j] == k
return j
i = i + 1
until T[j] == NIL or i = m
return NIL
Linear Probing index is computed using following hash function:
h(k, i) = (h₁(k) + i) mod m
h₁(k)= k mod m
Quadratic probing index is computed using following hash function:
h(k, i) = (h₁(k) + i²) mod m
h₁(k)= k mod m
Double hashing index is computed using following hash function:
h(k, i) = (h₁(k) + i h₂(k)) mod m
h₁(k)= k mod m
h₂(k) = 1 + (k mod m - 1)
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
