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.
Homework Answers
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 = 100N
Likelihood of having all objects different = (100*99*98*.....(100-N+1)) / 100N
Likelihood of having two objects same and causing collision = 1 - (100*99*98*.....(100-N+1)) / 100N
so,
= 1 - (100*99*98*.....(100-N+1)) / 100N = 50% = 0.5
= 0.5 = (100*99*98*.....(100-N+1)) / 100N
= 0.5*100N = 100*99*98*....(100-N+1)
This equation is satisfied for N = 13
Add Answer to:
How many objects can you insert into a hash table before you
have a greater than...
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...
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)....
Most questions answered within 3 hours.
-
A 2.5 kg block rests on a 30 ∘ slope and is attached by a string...
asked 5 minutes ago -
In C++ code language please:
1. Created a linked list
2. Insert 5 values: 1, 10,...
asked 9 minutes ago -
By analogy with automobiles, defects in cancer critical genes
have been likened to broken brakes and...
asked 29 minutes ago -
Supposing Delta is an example of a very large US commercial
airline, how does the magnitude...
asked 34 minutes ago -
The total amount of shares that a corporation's charter allows
it to issue is:
Issued.
Authorized....
asked 35 minutes ago -
Which of the following statements is false? Explain what is
wrong with the statement.
a. A...
asked 42 minutes ago -
Vincent Simmons appeals from the trial court's order awarding to
his wife, Dorothy Simmons, a one-half...
asked 43 minutes ago -
A group of researchers has developed a method that they
hypothesize will improve the reading ability...
asked 44 minutes ago -
When 1 Liter volumes of the below solutions are mixed, which
will result in the precipitation...
asked 47 minutes ago -
A truck moving at 45 m/s passes a police car moving at 36 m/s in
the...
asked 46 minutes ago -
By using specific examples, explain how multinational firms
balance (or not as the case may be)...
asked 48 minutes ago -
Given X ~ Exp(1/8), we survey 100 at a time and are interested
in the distribution...
asked 1 hour ago