search
Log In

Recent questions tagged hashing

2 votes
1 answer
1
Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys: There is a main hash table of size $4$. The $2$ least significant bits of a key is used to index into the main hash table. Initially, the main hash table entries are empty. Thereafter, when more keys are hashed into it, to resolve ... in decimal notation)? $5,9,4,13,10,7$ $9,5,10,6,7,1$ $10,9,6,7,5,13$ $9,5,13,6,10,14$
asked Feb 18 in Algorithms Arjun 719 views
0 votes
2 answers
2
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, 2020 in DS Lakshman Patel RJIT 339 views
2 votes
0 answers
3
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, 2020 in DS Lakshman Patel RJIT 233 views
0 votes
1 answer
4
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
asked Apr 1, 2020 in Algorithms Lakshman Patel RJIT 248 views
1 vote
2 answers
5
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, 2020 in Algorithms Lakshman Patel RJIT 391 views
0 votes
2 answers
6
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, 2020 in Algorithms Lakshman Patel RJIT 433 views
1 vote
1 answer
7
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, 2020 in Algorithms Lakshman Patel RJIT 382 views
1 vote
4 answers
8
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, 2020 in DS jothee 453 views
8 votes
2 answers
9
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, 2020 in Algorithms Arjun 5.8k views
2 votes
2 answers
10
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, 2020 in DS Satbir 894 views
6 votes
4 answers
11
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 1.9k views
0 votes
0 answers
12
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 156 views
0 votes
0 answers
13
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 105 views
0 votes
0 answers
14
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 107 views
0 votes
0 answers
15
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 70 views
0 votes
0 answers
16
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 118 views
0 votes
0 answers
17
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 64 views
0 votes
0 answers
18
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 138 views
0 votes
1 answer
19
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 200 views
0 votes
0 answers
20
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 57 views
0 votes
0 answers
21
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 63 views
0 votes
0 answers
22
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 53 views
0 votes
0 answers
23
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 81 views
...