How many objects can you insert into a hash table before you have a greater than...

Question

Question

How many objects can you insert into a hash table before you have a greater than...

How many objects can you insert into a hash table before you have a greater than 50% chance to have a collision between any two objects if n=100? Assume all hash values are equally likely.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

Considering Entries = N on which there will be more than 50% chance to have collision

Number of ways that objects will be different = 100*99*98*.....(100-N+1)

Number of possible combinations of objects with respect to N entries = 100^N

Likelihood of having all objects different = (100*99*98*.....(100-N+1)) / 100^N

Likelihood of having two objects same and causing collision = 1 - (100*99*98*.....(100-N+1)) / 100^N

so,

= 1 - (100*99*98*.....(100-N+1)) / 100^N = 50% = 0.5

= 0.5 = (100*99*98*.....(100-N+1)) / 100^N

= 0.5*100^N = 100*99*98*....(100-N+1)

This equation is satisfied for N = 13

Add a comment

Answer 2

Similar Homework Help Questions

A hash table is a data structure that supports the storage of subset of keys from...

A hash table is a data structure that supports the storage of subset of keys from a very large set S. To add a key x to a hash table, we use the hash function h: we compute h(x) and store x at location h(x). If two values x and y hash to the same location, we say we have a collision. For the hash table to work efficiently, we want to minimize the probability of collisions. The hash function...
a. Suppose you are given the following set of keys to insert into a hash table...

a. Suppose you are given the following set of keys to insert into a hash table that holds exactly 11 values: 113 , 117 , 97 , 100 , 114 , 123 , 116 , 98 , 99 using the hash function h(item) = item%11 Fill in the following hash table Reference: URL in the Hash tables item 113 is provided since 113%11 = 3 0 1 2 3 4 5 6 7 8 9 10 Hash(item) 113 item b....
Problem 3 Suppose that you have a set of n large, orderable, objects, each of size...

Problem 3 Suppose that you have a set of n large, orderable, objects, each of size q, so that it requires time e(a) to time to compute a hash function h(a) for any object and requires time e(g) to compare any two objects. Describe a compound data structure, built out of a heap and a hash table, that supports the following operations with the specified run times.. elt (x) Is x an element of the set? Expected run time O(g)....

How to write the insert, search, and remove functions for this hash table program? I'm stuck......

How to write the insert, search, and remove functions for this hash table program? I'm stuck... This program is written in C++ Hash Tables Hash Table Header File Copy and paste the following code into a header file named HashTable.h Please do not alter this file in any way or you may not receive credit for this lab For this lab, you will implement each of the hash table functions whose prototypes are in HashTable.h. Write these functions in a...
C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can...

C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can be used to implement a Set ADT. Let's try to use the template below to implement a Set with double hashing. Here we assume the Set contains names with 3 characters long. Since it is a Set, we do not need to have an explicit value for each key. We will use a token value of 1 if a name belongs to the Set....
Please complete the following task: Create a C++ hash table program for generating a hash from a string. Create a hash f...

Please complete the following task: Create a C++ hash table program for generating a hash from a string. Create a hash function then test and evaluate the results. The set of strings are from a "words.txt" file (there are 45,402 words in the file, no repeating words. Map the words to 45,402 buckets using a hash function). Requirements: Create an array of 45,402 integers and initialize each to zero. These will be used to store how many times each index...

I really need assistance with creating a C++ hash table program for generating a hash from a string. Create a hash funct...

I really need assistance with creating a C++ hash table program for generating a hash from a string. Create a hash function then test and evaluate the results. The set of strings are from a "words.txt" file (there are 45,402 words in the file, no repeating words. Map the words to 45,402 buckets using a hash function). Requirements: Create an array of 45,402 integers and initialize each to zero. These will be used to store how many times each index...
I really need assistance with creating a C++ hash table program for generating a hash from a string. Create a hash funct...

I really need assistance with creating a C++ hash table program for generating a hash from a string. Create a hash function then test and evaluate the results. The set of strings are from a "words.txt" file (there are 45,402 words in the file, no repeating words. Map the words to 45,402 buckets using a hash function). Requirements: Create an array of 45,402 integers and initialize each to zero. These will be used to store how many times each index...
Insert elements into a hash table implemented using chain hashing, as an array of linked list...

Insert elements into a hash table implemented using chain hashing, as an array of linked list in which each entry slot is as a linked list of key/value pairings that have the same hash (outcome value computed using certain hash function). You are allowed to use “Hash Function”, h(k) = k % x where, x is the value you will need to decide to use, that you find appropriate for this implementation. The main requirements are the following: 1. Input:...

If the order of objects is not of importance, how many ways can nineteen objects be...

If the order of objects is not of importance, how many ways can nineteen objects be selected three at a time? Why is this result different from the result when order matters?There are blank different ways to select three objects at a time. (Type a whole number.) Explain why this result is different from the result when order matters. Choose the correct answer below. A. When order does not matter, picking the first object before the second object is the...

How many objects can you insert into a hash table before you have a greater than...

Homework Answers

Add Answer to:
How many objects can you insert into a hash table before you have a greater than...

Post as a guest

Earn Coins

A hash table is a data structure that supports the storage of subset of keys from...

a. Suppose you are given the following set of keys to insert into a hash table...

Problem 3 Suppose that you have a set of n large, orderable, objects, each of size...

How to write the insert, search, and remove functions for this hash table program? I'm stuck......

C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can...

Please complete the following task: Create a C++ hash table program for generating a hash from a string. Create a hash f...

I really need assistance with creating a C++ hash table program for generating a hash from a string. Create a hash funct...

I really need assistance with creating a C++ hash table program for generating a hash from a string. Create a hash funct...

Insert elements into a hash table implemented using chain hashing, as an array of linked list...

If the order of objects is not of importance, how many ways can nineteen objects be...

How many objects can you insert into a hash table before you have a greater than...

Homework Answers

Add Answer to: How many objects can you insert into a hash table before you have a greater than...

Post as a guest

Earn Coins

Add Answer to:
How many objects can you insert into a hash table before you have a greater than...