menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Hashing

1 vote
489 views
Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful search respectively?
in Algorithms 489 views
0
for successful search $\frac{2}{10}$

unsuccessful search $\frac{8}{10}$
0
unsuccessful searches = 5

successful searches = 2 (approx)

1 Answer

0 votes
10/8 ln 5 and 5 for successful and unsuccessful search respectively.

If X is load factor.

Successful search = $(1/X) log (1/(1-x))$

Unsuccessful search = $1/(1-x)$
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →

Related questions

0 votes
0 answers
1
150 views
hashing
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
asked Dec 28, 2018 in DS Rahul_Rathod_ 150 views
1 vote
0 answers
2
189 views
Hashing
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is used.
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is used.
asked Aug 9, 2018 in DS hrcule 189 views
13 votes
2 answers
3
1.4k views
Hashing
Using open addressing with linear probing, we sequentially insert three distinct keys k1, k2 and k3 into a hash table of size m. Assuming simple uniform hashing, what is the probability that we will need three probes, when inserting the third key, k3? 3/m 2/m2 3/m2 2/m Please explain the solution.
Using open addressing with linear probing, we sequentially insert three distinct keys k1, k2 and k3 into a hash table of size m. Assuming simple uniform hashing, what is the probability that we will need three probes, when inserting the third key, k3? 3/m 2/m2 3/m2 2/m Please explain the solution.
asked Nov 2, 2016 in Algorithms agoh 1.4k views
3 votes
1 answer
4
346 views
Hashing+Probaility
asked Oct 8, 2016 in DS Rahul Jain25 346 views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...