search
Log In

Recent questions tagged hashing

0 votes
1 answer
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$
asked Apr 2 in DS Lakshman Patel RJIT 66 views
1 vote
1 answer
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
asked Apr 2 in DS Lakshman Patel RJIT 54 views
0 votes
2 answers
3
1 vote
2 answers
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
asked Mar 31 in Algorithms Lakshman Patel RJIT 145 views
0 votes
2 answers
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$
asked Mar 31 in Algorithms Lakshman Patel RJIT 128 views
1 vote
1 answer
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)
asked Mar 31 in Algorithms Lakshman Patel RJIT 163 views
1 vote
4 answers
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$
asked Mar 24 in DS jothee 218 views
6 votes
3 answers
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_____________.
asked Feb 12 in Algorithms Arjun 2.9k views
1 vote
2 answers
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$
asked Jan 13 in DS Satbir 481 views
6 votes
4 answers
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}$
asked May 5, 2019 in DS srestha 459 views
0 votes
0 answers
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.
asked Apr 4, 2019 in Algorithms akash.dinkar12 126 views
0 votes
0 answers
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.
asked Apr 4, 2019 in Algorithms akash.dinkar12 73 views
0 votes
0 answers
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$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 72 views
0 votes
0 answers
14
Write pseudo code for $HASH-DELETE$ as outlined in the text, and modify $HASHINSERT$ to handle the special value $DELETED.$
asked Apr 4, 2019 in Algorithms akash.dinkar12 41 views
0 votes
0 answers
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$+$($k$ $mod$ $(m-1)$)$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 64 views
0 votes
0 answers
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.
asked Apr 4, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
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|}$
asked Apr 4, 2019 in Algorithms akash.dinkar12 82 views
0 votes
1 answer
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.
asked Apr 4, 2019 in Algorithms akash.dinkar12 152 views
0 votes
0 answers
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.
asked Apr 4, 2019 in Algorithms akash.dinkar12 38 views
0 votes
0 answers
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 ?
asked Apr 4, 2019 in Algorithms akash.dinkar12 37 views
0 votes
0 answers
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 ?
asked Apr 4, 2019 in Algorithms akash.dinkar12 34 views
0 votes
0 answers
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}))$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 53 views
0 votes
0 answers
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)$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 46 views
0 votes
0 answers
24
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?
asked Apr 4, 2019 in Algorithms akash.dinkar12 53 views
0 votes
0 answers
25
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?
asked Apr 4, 2019 in Algorithms akash.dinkar12 114 views
0 votes
0 answers
26
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$.$
asked Apr 4, 2019 in Algorithms akash.dinkar12 34 views
...