题目内容

Hash table size = 10 buckets; number of unique insertions = 100Expected average length of the list for each bucket =______

查看答案

搜索结果不匹配？点我反馈

更多问题

Hash table size = 10 buckets; number of unique insertions = 20Expected average length of the list for each bucket =______

Imagine we implement a dictionary, all of whose keys are U.S. social security numbers (9 digit numbers). If we used a list with 109 elements to represent the dictionary, we could do lookups in constant time. Of course, if the dictionary contained entries for only 20 people (or, for that matter, only 3∗108 people), this would waste quite a lot of space.Which gets us to the subject of hash functions. A hash function maps a large space of inputs (e.g., all natural numbers) to a smaller space of outputs (e.g., the natural numbers between 0 and 5000). The space of possible outputs should be much smaller than the space of possible inputs!A hash function is "many-to-one", that is, multiple different inputs are mapped to the same output. When two inputs are mapped to the same output, it is called a collision. A good hash function produces a uniform distribution, i.e., every output in the range is equally probable, which minimizes the probability of collisions.Remember the intDict code from the previous video? intDict uses a simple hash function (modulus) to implement a dictionary with integers as keys. The basic idea is to represent instances of class intDict by a list of buckets, where each bucket is a list of (key, value) tuples. By making each bucket a list, we handle collisions by storing all of the values that hash to that bucket.Collisions are inevitable when implementing hash tables, because generally we are mapping a really big set of inputs to a much smaller set of buckets. Thinking about the way that intDict implements hashing - making each bucket a list, and assigning each element to one bucket's list - what is the expected average length of the list in each bucket of the hash table when the hash table is 10 buckets big for the following number of unique insertions (that is, no two elements inserted are equal)?Hash table size = 10 buckets; number of unique insertions = 10Expected average length of the list for each bucket =______

For this problem, download intDictTests.py, a file that contains some simulations that will help us examine the properties of hashing.Read through the extra functions to understand what they do; call the appropriate function with the right parameters to answer the following questions.If our hash table has 1000 buckets and we perform 50 insertions, what is the calculated probability of a collision? Answer to at least 3 decimal places.______

You have a bucket with 3 red balls and 3 green balls. This time, assume you don't replace the ball after taking it out. What is the probability of drawing 3 balls of the same color? Answer in reduced fraction form - eg 1/5 instead of 2/10.______