Hash function uniformly distributes n keys over the tables

Assignment Help Basic Computer Science

Reference no: EM13244893

1. If a hash table contains tablesize positions and n records currently occupy the table, the load factor lf is defined as n/tablesize. Suppose a hash function uniformly distributes n keys over the tablesize positions of the table and lf is the load factor of the table. Show that upon insertion, (n-1)* lf/2 of the keys in the table collide with a previously entered key.

2. Assume that n random positions of a tablesize- element hash table are occupied, using hash and rehash functions that are equally likely to produce any index in the table. Show that the average number of comparisons needed to insert a new element is (tablesize + 1)/(tablesize-n+1). Explain why linear probing does not satisfy this condition.
Required minimum-1 page

Reference no: EM13244893

Questions Cloud

Explain the molar mass of citric acid : A student used 22.0 mL of 0.1035 M NaOH to titrate 20 mL of orange juice. How many grams of citric acid were present in the sample? The molar mass of citric acid, H3C6H5O7, is 192.12 g/mol.

What is the magnitude of electric field of the baseline : Three point charges are placed at the corners of an isosceles triangle. At the left and right end points of the base are 6 micro coulomb and 6 micro coulombrespectively, What is the magnitude of the electric field at the midpoint of the baseline

Calculate probability function and probability distribution : Calculate the probability function and the probability distribution of X and identify the space of results and the underlined X random variable

A concentrations of sodium will produce the effective buffer : A buffer is to be prepared by adding solid sodium acetate to 0.10 M CH3COOH. Which of the following concentrations of sodium will produce the most effective buffer

Hash function uniformly distributes n keys over the tables : If a hash table contains tablesize positions and n records currently occupy the table, the load factor lf is defined as n/tablesize. Suppose a hash function uniformly distributes n keys over the tablesize positions of the table and lf is the load fac..

How many grams of carbon dioxide can form by a mixture : How many grams of carbon dioxide (CO2) can form when a mixture of 4.95 g of ethylene (C2H4) and 3.25 g of oxygen is ignited. Assume complete combustion to CO2 and H2O.

Calculate the electric field in term of q and r : A small conducting spherical shell withinner radius a and outer radius b is concentric with a larger conducting spherical shell with inner radius c and outer radiusd, calculate the electric field (magnitude and direction) in termsof..

Explain what is the total pressure in a flask of h2 : What is the total pressure in a 11.0 L flask 20.0°C, which contains 0.127 moles of H2 and 0.288 moles of N2

Two problems in lisp : 1. Define a function foo(A,L), where A is an integer and L is a list that will remove each A in L. This is a shallow function.

User Account

All Pages