Mixing
After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Consider a hash function that distributes keys uniformly. The hash table size is 20.
Here I am getting answer 11 considering the fact that probability will of collision will be 50% more only when we already have 10 entries in the hash table and we are about to map one more entry in the hash table .
Is this approach correct ?
probability algorithms
asked Aug 2 at 23:50
radhika
31
add a comment |Â
up vote
0
down vote
favorite
Consider a hash function that distributes keys uniformly. The hash table size is 20.
Here I am getting answer 11 considering the fact that probability will of collision will be 50% more only when we already have 10 entries in the hash table and we are about to map one more entry in the hash table .
Is this approach correct ?
probability algorithms
asked Aug 2 at 23:50
radhika
31
1
That's fine, provided you are only looking at the probability of the new key colliding. If you are looking for the probability of a collision having occurred at some point before now, then you might be looking at the birthday problem.
– Brian Tung
Aug 2 at 23:56
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Consider a hash function that distributes keys uniformly. The hash table size is 20.
Here I am getting answer 11 considering the fact that probability will of collision will be 50% more only when we already have 10 entries in the hash table and we are about to map one more entry in the hash table .
Is this approach correct ?
probability algorithms
asked Aug 2 at 23:50
radhika
31
Consider a hash function that distributes keys uniformly. The hash table size is 20.
Here I am getting answer 11 considering the fact that probability will of collision will be 50% more only when we already have 10 entries in the hash table and we are about to map one more entry in the hash table .
Is this approach correct ?
probability algorithms
asked Aug 2 at 23:50
radhika
31
asked Aug 2 at 23:50
radhika
31
asked Aug 2 at 23:50
radhika
31
asked Aug 2 at 23:50
radhika
31
31
1
That's fine, provided you are only looking at the probability of the new key colliding. If you are looking for the probability of a collision having occurred at some point before now, then you might be looking at the birthday problem.
– Brian Tung
Aug 2 at 23:56
add a comment |Â
1
That's fine, provided you are only looking at the probability of the new key colliding. If you are looking for the probability of a collision having occurred at some point before now, then you might be looking at the birthday problem.
– Brian Tung
Aug 2 at 23:56
1
1
That's fine, provided you are only looking at the probability of the new key colliding. If you are looking for the probability of a collision having occurred at some point before now, then you might be looking at the birthday problem.
– Brian Tung
Aug 2 at 23:56
That's fine, provided you are only looking at the probability of the new key colliding. If you are looking for the probability of a collision having occurred at some point before now, then you might be looking at the birthday problem.
– Brian Tung
Aug 2 at 23:56
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
The probability of collision in each entry will be $dfrac120$
After inserting $k$ values the probability becomes $dfrac12$
Then we have $dfrac120times k=dfrac12$
Therefore, $k=10$
answered Aug 3 at 0:14
Key Flex
3,683422
Not quite -- the probablity at $k=10$ will be lower than $frac12$ due to the risk that there may be collisions among the first $10$ keys.
– Henning Makholm
Aug 3 at 0:35
Don't we consider here the probability of collision among the first 10 keys ?
– radhika
Aug 4 at 9:12
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
The probability of collision in each entry will be $dfrac120$
After inserting $k$ values the probability becomes $dfrac12$
Then we have $dfrac120times k=dfrac12$
Therefore, $k=10$
answered Aug 3 at 0:14
Key Flex
3,683422
Not quite -- the probablity at $k=10$ will be lower than $frac12$ due to the risk that there may be collisions among the first $10$ keys.
– Henning Makholm
Aug 3 at 0:35
Don't we consider here the probability of collision among the first 10 keys ?
– radhika
Aug 4 at 9:12
add a comment |Â
up vote
0
down vote
accepted
The probability of collision in each entry will be $dfrac120$
After inserting $k$ values the probability becomes $dfrac12$
Then we have $dfrac120times k=dfrac12$
Therefore, $k=10$
answered Aug 3 at 0:14
Key Flex
3,683422
Not quite -- the probablity at $k=10$ will be lower than $frac12$ due to the risk that there may be collisions among the first $10$ keys.
– Henning Makholm
Aug 3 at 0:35
Don't we consider here the probability of collision among the first 10 keys ?
– radhika
Aug 4 at 9:12
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
The probability of collision in each entry will be $dfrac120$
After inserting $k$ values the probability becomes $dfrac12$
Then we have $dfrac120times k=dfrac12$
Therefore, $k=10$
answered Aug 3 at 0:14
Key Flex
3,683422
The probability of collision in each entry will be $dfrac120$
After inserting $k$ values the probability becomes $dfrac12$
Then we have $dfrac120times k=dfrac12$
Therefore, $k=10$
answered Aug 3 at 0:14
Key Flex
3,683422
answered Aug 3 at 0:14
Key Flex
3,683422
answered Aug 3 at 0:14
Key Flex
3,683422
answered Aug 3 at 0:14
Key Flex
3,683422
3,683422
Not quite -- the probablity at $k=10$ will be lower than $frac12$ due to the risk that there may be collisions among the first $10$ keys.
– Henning Makholm
Aug 3 at 0:35
Don't we consider here the probability of collision among the first 10 keys ?
– radhika
Aug 4 at 9:12
add a comment |Â
Not quite -- the probablity at $k=10$ will be lower than $frac12$ due to the risk that there may be collisions among the first $10$ keys.
– Henning Makholm
Aug 3 at 0:35
Don't we consider here the probability of collision among the first 10 keys ?
– radhika
Aug 4 at 9:12
Not quite -- the probablity at $k=10$ will be lower than $frac12$ due to the risk that there may be collisions among the first $10$ keys.
– Henning Makholm
Aug 3 at 0:35
Not quite -- the probablity at $k=10$ will be lower than $frac12$ due to the risk that there may be collisions among the first $10$ keys.
– Henning Makholm
Aug 3 at 0:35
Don't we consider here the probability of collision among the first 10 keys ?
– radhika
Aug 4 at 9:12
Don't we consider here the probability of collision among the first 10 keys ?
– radhika
Aug 4 at 9:12
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870603%2fafter-hashing-of-how-many-keys-will-the-probability-that-any-new-key-hashed-coll%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
That's fine, provided you are only looking at the probability of the new key colliding. If you are looking for the probability of a collision having occurred at some point before now, then you might be looking at the birthday problem.
– Brian Tung
Aug 2 at 23:56