# Recent questions tagged hashing 1
A hash table with $10$ buckets with one slot per bucket is depicted. The symbols, $S1$ to $S7$ are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is $6$ $5$ $4$ $3$
1 vote
2
The average search time of hashing, with linear probing will be less if the load factor is far less than one equals one is far greater than one none of these
3
The average search time for hashing with linear probing will be less if the load factor Is far less than one Equals one Is far greater than one None of the above
1 vote
4
The average search time of hashing, with linear probing will be less if the load factor : is far less than $1$ equals $1$ is far greater than $1$ none of the options
5
A hash function $f$ defined as $f(\text{key})=\text{key mod }7$, with linear probing, insert the keys $37,38,72,48,98,11,56$ into a table indexed from $11$ will be stored in the location $3$ $4$ $5$ $6$
1 vote
6
A hash table has space for $100$ records. Then the probability of collision before the table is $10\%$ full, is $0.45$ $0.5$ $0.3$ $0.34$ (approximately)
1 vote
7
If $h$ is chosen from a universal collection of hash functions and is used to hash $n$ keys into a table of size $m$, where $n \leq m$, the expected number of collisions involving a particular key $x$ is less than __________. $1$ $1/n$ $1/m$ $n/m$
8
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.
1 vote
9
In linear hashing, if blocking factor $bfr$, loading factor $i$ and file buckets $N$ are known, the number of records will be $cr= i+bfr+N$ $r=i-bfr-N$ $r=i+bfr-N$ $r=i ^{\ast} bfr ^{\ast} N$
10
Consider a hash table with $N$ slots. It is given that the collision resolution technique used in chaining. Assume simple uniform hashing, what is the probability that the last $k$ slots are unfilled after the first $’r’$ insertions? $A)\left ( 1-\frac{N}{k} \right )^{r}$ $B)\left ( 1-\frac{k}{N} \right )^{r}$ $C)\left ( 1+\frac{N}{k} \right )^{r-1}$ $D)\left ( 1-\frac{k}{N} \right )^{r-1}$
11
Consider an open-address hash table with a load factor $\alpha$ Find the nonzero value $\alpha$ for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search.
12
Suppose that we use double hashing to resolve collisions--that is, we use the hash function $h(k,i) = (h_1(k) + ih_2(k))$ $mod$ $m$.Show that if $m$ and $h_2(k)$ have greatest common divisor $d\geq 1$ for some key $k$,then an unsuccessful search for key $k$ examines ... to slot $h_1(k)$.Thus, when $d=1$, so that $m$ and $h_2(k)$ are relatively prime, the search may examine the entire hash table.
13
Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is $3/4$ and when it is $7/8$.
14
Write pseudo code for $HASH-DELETE$ as outlined in the text, and modify $HASHINSERT$ to handle the special value $DELETED.$
15
Consider inserting the keys $10, 22, 31, 4,15,28,17,88,59$ into a hash table of length $m =11$ using open addressing with the auxiliary hash function $h’(k) =k$. Illustrate the result of inserting these keys using linear probing, using quadratic probing with $c_1 =1$ and $c_2=3$ and using double hashing with $h_1(k) =k$ and $h_2(k)$ $=$ $1$+$($kmod(m-1)$)$.
16
Let $U$ be a set of $n-tuples$ of values drawn from$\mathbb{\ Z_p}$ , let $B$ $=$ $\mathbb{\ Z_p}$ , where p is prime. Define the hash function $h_b :U \rightarrow B$ for $b$ $\in$\mathbb{\ Z_p}$on an input$n-$tuple$ ... = $\{h_b: b\in \mathbb{\ Z_p}\}$ Argue that $\mathscr{H}$ is $n(n-1)/p$- universal according to the definition of the $\epsilon$ universal.
17
Define a family $\mathscr{H}$ of hash functions from a finite set $U$ to a finite set $B$ to be universal if for all pairs of distinct elements $k$ and $l$ in $U$, $Pr\{h(k) = h(l)\} \leq \epsilon$ where the probability is over the choice of the hash function $h$ ... $\mathscr{H}$. Show that an $\epsilon-$universal family of hash functions must have $\epsilon \geq \frac{1}{|B|} - \frac{1}{|U|}$
18
Consider a hash table of size $m =1000$ and a corresponding hash function $h(k) =$ $\lfloor$ $m$($kA$ $mod$ $1$)$\rfloor$ for $A = \frac{(\sqrt{5} – 1)}{2}$ .Compute the locations to which the keys $61, 62, 63, 64,$ and $65$ are mapped.
19
Consider a version of the division method in which $h(k) =k$ $mod$ $m$, where $m = 2^p-1$ and $k$ is a character string interpreted in $radix$ $2^p$. Show that if we can derive string $x$ from string $y$ by permuting its characters, then $x$ and $y$ hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.
20
Suppose that we hash a string of $r$ characters into $m$ slots by treating it as a $radix-128$ number and then using the division method. We can easily represent the number $m$ as a $32-bit$ computer word, but the string of $r$ characters, ... division method to compute the hash value of the character string without using more than a constant number of words of storage outside the string itself ?
21
Suppose we wish to search a linked list of length $n$, where each element contains a key $k$ along with a hash value $h(k)$. Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key ?
22
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time $\mathcal{O}(L*(1+\frac{1}{\alpha}))$.
23
Suppose that we are storing a set of $n$ keys into a hash table of size $m$. Show that if the keys are drawn from a universe $U$ with $|U| > nm$, then $U$ has a subset of size $n$ consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is $\Theta(n)$.
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in $\mathcal{O}(1)$expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?
Demonstrate what happens when we insert the keys $5,28,19,15,20,33,12,17,10$ into a hash table with collisions resolved by chaining. Let the table have $9$ slots, and let the hash function be $h(k) = k$ $mod$ $9$.\$