Recent questions tagged hashing / GATE Overflow for GATE CSE

If we are inserting an element in chaining(outside) hashing technique, then what will be the time complexity in best case, average case and Worst case.

piyushkr

2.5k views

piyushkr asked Dec 23, 2015

0 votes

1 answer

274

Hashing

Himanshu1

779 views

Himanshu1 asked Dec 16, 2015

0 votes

1 answer

275

ME advanced | Probability question HASHING Chaning

Aspi R Osa

406 views

Aspi R Osa asked Dec 15, 2015

14 votes

3 answers

276

Hash table
A Hash table has space for 100 records. Then the probability of collision before the table is 10% full is? A 0.45 B 0.5 C 0.3 D 0.34 (approximately)

A Hash table has space for 100 records. Then the probability of collision before the table is 10% full is?A 0.45B 0.5C 0.3D 0.34 (approximately)

Soumyashree

15.5k views

Soumyashree asked Nov 21, 2015

1 votes

1 answer

277

Hashing function
Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8.If a collision occurs at position 4, then the location which will never be probed is..

Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8.If a collision occurs at position 4, then the lo...

Soumyashree

802 views

Soumyashree asked Nov 21, 2015

1 votes

2 answers

278

Hash table
A hash table can store a max of 10 records, currently, there are records in locations 1,3,4,7,8,9,10. The probability of a new record going into location 2,with a hash function resolving collisions by linear probing is..

A hash table can store a max of 10 records, currently, there are records in locations 1,3,4,7,8,9,10. The probability of a new record going into location 2,with a hash fu...

Soumyashree

9.0k views

Soumyashree asked Nov 21, 2015

5 votes

1 answer

279

Hashing
Let $H$ be a finite collection of hash functions that map a universe $U$ of keys to $\{0,1,2, \ldots ,m-1\}$. $H$ is said to be universal if for each pair of distinct keys, $(k, i) \in U$, the number of hash functions $h\in H$ for which $h(k)=n(i)$ is at most ________ $\dfrac{∣H∣}{m^2}$ $\dfrac{1}{m^2 \log m}$ $\dfrac{∣H∣}{m^2}$ $\dfrac{∣H∣}{m}$

Let $H$ be a finite collection of hash functions that map a universe $U$ of keys to $\{0,1,2, \ldots ,m-1\}$.$H$ is said to be universal if for each pair of distinct keys...

Nishikant kumar

1.5k views

Nishikant kumar asked Oct 17, 2015

5 votes

2 answers

280

Hashing
Consider a hash table with $n$ buckets, where external(overflow) chaining is used to resolve collision. The hash function is such that the probability that a key value is hashed to a particular bucket is $\dfrac 1 n$. The hash table is initially empty and $k$ distinct values are inserted in the table. Q) What is ... $n(n - 1)(n - 2)(n - k - 1)/n^k$ both (a) and (b) none

Consider a hash table with $n$ buckets, where external(overflow) chaining is used to resolve collision. The hash function is such that the probability that a key value is...

Nishikant kumar

1.2k views

Nishikant kumar asked Oct 17, 2015

1 votes

1 answer

281

hashing

Shefali

694 views

Shefali asked Oct 8, 2015

12 votes

6 answers

282

Consider a hash table with ‘m’ slots that uses chaining for collision resolution.
Consider a hash table with $m$ slots that uses chaining for collision resolution. The table is initially empty. What is the probability that after 4 keys are inserted that at least a chain of size 3 is created? (Assume simple uniform ... $m^{–3} (m – 1)$ $3m^{–1}$

Consider a hash table with $m$ slots that uses chaining for collision resolution. The table is initially empty. What is the probability that after 4 keys are inserted tha...

radha gogia

7.8k views

radha gogia asked Jul 20, 2015

53 votes

4 answers

283

GATE CSE 1989 | Question: 1-vii, ISRO2015-14
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols $S1$ to $S7$ initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is $4$ $5$ $6$ $3$

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols $S1$ to $S7$ initially entered using a hashing function with linear p...

Anu

17.9k views

Anu asked Jun 1, 2015

1 votes

2 answers

284

simple uniform hashing
why in open address hash table with load factor α=n/m<1, the expected number of probes in an unsuccessful search is at most 1/(1-α) assuming uniform hashing ?

why in open address hash table with load factor α=n/m<1, the expected number of probes in an unsuccessful search is at most 1/(1-α) assuming uniform hashing ?

anurag_am

1.7k views

anurag_am asked May 29, 2015

0 votes

1 answer

285

simple uniform hashing
why in a hash table in which collisions are resolved by a chaining , a successful search takes average- case time ⊖(1+load factor) ,under the assumption of simple uniform hashing ?

why in a hash table in which collisions are resolved by a chaining , a successful search takes average- case time ⊖(1+load factor) ,under the assumption of simple unifo...

anurag_am

1.3k views

anurag_am asked May 27, 2015

2 votes

2 answers

286

hashing
In a separate chaining hash table with load factor =0.8, what is the average length of a list ? a) 0.8 b) 1.0 c) 1.25 d) there is not enough information e) there is enough information, but none of the above are correct

In a separate chaining hash table with load factor =0.8, what is the average length of a list ?a) 0.8 b) 1.0 c) 1.25d) there is not enough informatione) there is enough i...

anurag_am

2.0k views

anurag_am asked May 23, 2015

2 votes

2 answers

287

linear probing
How are elements deleted in linear probing ? (a) Deletion is not allowed (b) they are changed to zero (c) they are marked deleted (d) unchecked deallocation (e) None of the above

How are elements deleted in linear probing ?(a) Deletion is not allowed(b) they are changed to zero(c) they are marked deleted(d) unchecked deallocation(e) None of the ab...

anurag_am

927 views

anurag_am asked May 23, 2015

36 votes

4 answers

288

GATE CSE 2015 Set 3 | Question: 17
Given that hash table $T$ with $25$ slots that stores $2000$ elements, the load factor $a$ for $T$ is _________.

Given that hash table $T$ with $25$ slots that stores $2000$ elements, the load factor $a$ for $T$ is _________.

go_editor

9.3k views

go_editor asked Feb 14, 2015

72 votes

4 answers

289

GATE CSE 2015 Set 2 | Question: 33
Which one of the following hash functions on integers will distribute keys most uniformly over $10$ buckets numbered $0$ to $9$ for $i$ ranging from $0$ to $2020$? $h(i) = i^2 \text{mod } 10$ $h(i) = i^3 \text{mod } 10$ $h(i) = (11 \ast i^2) \text{mod } 10$ $h(i) = (12 \ast i^2) \text{mod } 10$

Which one of the following hash functions on integers will distribute keys most uniformly over $10$ buckets numbered $0$ to $9$ for $i$ ranging from $0$ to $2020$?$h(i) ...

go_editor

17.0k views

go_editor asked Feb 12, 2015

1 votes

2 answers

290

GATE FEB7 EVN
1) A 2) B 3) C 4) D

1)A2)B3)C4)D

dmharoon

484 views

dmharoon asked Feb 11, 2015

0 votes

1 answer

291

question

Sahil Gupta

293 views

Sahil Gupta asked Dec 17, 2014

6 votes

2 answers

292

MadeEasy Test Series: Programming & DS - Hashing
Consider a hash table using uniform hashing with number of slots as $m=6$ and number of keys, $k=8$. Collisions are resolved by chaining. Assuming direct hashing is used, what is the expected number of slots that ends not being empty?

Consider a hash table using uniform hashing with number of slots as $m=6$ and number of keys, $k=8$. Collisions are resolved by chaining. Assuming direct hashing is used,...

Isha Karn

3.1k views

Isha Karn asked Dec 5, 2014

0 votes

1 answer

293

Hashing
Consider the following, five binary strings of length 8. 01010010, 11011011, 10011010, 11111011, 01110010 A hash table of size M = 8 (0 to 7) is using open addressing for hashing the binary strings. Assume finding an empty slot directly without collision or after collision is also a probe. Calculate the total number of probes that occur while hashing five strings using linear probing.

Consider the following, five binary strings of length 8.01010010, 11011011, 10011010, 11111011, 01110010A hash table of size M = 8 (0 to 7) is using open addressing for h...

Keith Kr

1.1k views

Keith Kr asked Nov 26, 2014

22 votes

3 answers

294

GATE IT 2005 | Question: 16
A hash table contains $10$ buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is $\text{key}\%10$. If the values $43, 165, 62, 123, 142$ are inserted in the table, in what location would the key value $142$ be inserted? $2$ $3$ $4$ $6$

A hash table contains $10$ buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is $\text{key}\%10$. If the value...

Ishrat Jahan

6.6k views

Ishrat Jahan asked Nov 3, 2014

5 votes

1 answer

295

The number of different insertion sequences on the numbers
The number of different insertion sequences on numbers {1, 14, 26, 44, 60, 71} on an initially empty hash table H of size 6 and a hash function x%6 with linear probing scheme for collision resolution such that the end hash table should look like 60, 1, 14, 26, 44, 71 (The indices of numbers from left to right are 0 to 5) are ________

The number of different insertion sequences on numbers {1, 14, 26, 44, 60, 71} on an initially empty hash table H of size 6 and a hash function x%6 with linear probing sc...

Arjun

2.0k views

Arjun asked Nov 2, 2014

28 votes

6 answers

296

GATE IT 2006 | Question: 20
Which of the following statement(s) is TRUE? A hash function takes a message of arbitrary length and generates a fixed length code. A hash function takes a message of fixed length and generates a code of variable length. A hash function may give the same hash value for distinct messages. I only II and III only I and III only II only

Which of the following statement(s) is TRUE?A hash function takes a message of arbitrary length and generates a fixed length code.A hash function takes a message of fixed...

Ishrat Jahan

12.2k views

Ishrat Jahan asked Oct 31, 2014

62 votes

11 answers

297

GATE IT 2007 | Question: 28
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$. $5$ $6$ $7$ $10$

Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collide...

Ishrat Jahan

29.3k views

Ishrat Jahan asked Oct 29, 2014

16 votes

4 answers

298

GATE IT 2008 | Question: 48
Consider a hash table of size $11$ that uses open addressing with linear probing. Let $h(k) = k \mod 11$ be the hash function used. A sequence of records with keys $43 \ 36 \ 92 \ 87 \ 11 \ 4 \ 71 \ 13 \ 14$ is inserted into an initially empty ... which are indexed from zero to ten. What is the index of the bin into which the last record is inserted? $3$ $4$ $6$ $7$

Consider a hash table of size $11$ that uses open addressing with linear probing. Let $h(k) = k \mod 11$ be the hash function used. A sequence of records with keys$43 \ 3...

Ishrat Jahan

5.9k views

Ishrat Jahan asked Oct 28, 2014

24 votes

4 answers

299

GATE CSE 1996 | Question: 15
Insert the characters of the string $K \ R \ P \ C \ S \ N \ Y \ T \ J \ M$ into a hash table of size $10$. Use the hash function $h(x)=( ord (x) – ord (\text{“}a\text{”}) + 1) \mod 10$ and linear probing to resolve collisions. Which insertions cause collisions? Display the final hash table.

Insert the characters of the string $K \ R \ P \ C \ S \ N \ Y \ T \ J \ M$ into a hash table of size $10$.Use the hash function$$h(x)=( ord (x) – ord (\text{“}a\tex...

Kathleen

6.2k views

Kathleen asked Oct 9, 2014

39 votes

6 answers

300

GATE CSE 1996 | Question: 1.13
An advantage of chained hash table (external hashing) over the open addressing scheme is Worst case complexity of search operations is less Space used is less Deletion is easier None of the above

An advantage of chained hash table (external hashing) over the open addressing scheme isWorst case complexity of search operations is lessSpace used is lessDeletion is ea...

Kathleen

13.8k views

Kathleen asked Oct 9, 2014

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true