The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

Consider a hash table of size seven, with starting index zero, and a hash function $(3x + 4)\mod 7$. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence $1, 3, 8, 10$ is inserted into the table using closed hashing? Note that − denotes an empty location in the table.

  1. $8$, −, −, −, −, −, $10$

  2. $1, 8, 10$, −, −, −, $3$

  3. $1$, −, −, −, −, −, $3$

  4. $1, 10, 8$, −, −, −,$ 3$

asked in DS by Veteran (52k points)
edited by | 2.1k views
since they didn't mention collision resolution it need assumption like-
"closed" always refers to some sort of strict guarantee, like when we guarantee that objects are always stored directly within the hash table (closed hashing). Then, the opposite of "closed" is "open", so if you don't have such guarantees, the strategy is considered "open".

3 Answers

+19 votes
Best answer

The answer is (B).

$1$ will occupy location $0, 3$ will occupy location $6, 8$ hashed to location $0$ which is already occupied so, it will be hashed to one location next to it. i.e. to location $1$.

Since $10$ also clashes, so it will be hashed to location $2$.

answered by Boss (19.9k points)
edited by

Yes. But the rehashing method is not stated in the question. We need to assume linear rehashing.

closed hashing can do rehashing if necessary , is there any problem if not stated in the question?
We do rehashing, but what method to use? we can go to next slot (linear probe), slots in quadratic order (quadratic probe) or even do double hashing. I guess its fine to assume linear probe by default.
how will linear probing will be done for 8?

(3x+4)mod 7= 0

which is occupied.
Next will be

(3(x+1) + 4 mod)7?

(3x+4)mod7 +1
As, linear probing is not mentioned. So Why are we not simply not replacing the slots ?
@arjun sir then shouldnt it be c ? only there is no where you written linear probing is default method of rehasing !!
They mention closed hashing.

But dosent mention any scheme which one to consider..

Closed Hashing

A closed hash table keeps the members of the set in the bucket table rather than using that table to store list headers. Consequently only one element is in any bucket. So, what happens if hash(x) = hash(y) when x and y are different? That is, what happens when we have a collision? We have a "rehash strategy". A "collision" occurs when we have i = hash(x) and the ith element of the table is already occupied (by something other than x). The rehash strategy chooses a sequence of alternative locations, hash-1(x), hash-2(x), hash-3(x), ..., within the table. We try each one of these locations in turn until we encounter an empty (unoccupied) location. If none exists, and we have exhausted the rehash strategy, we assume that the table is full and that we cannot insert x.

A simple rehashing strategy, called "linear rehashing" is as follows:

             hash-i(x) = (hash(x) + i) mod B

where there are B buckets in the hash table.

Initially the table is empty, and each bucket holds a special value "empty", ie a value different from any value that we might insert into the table.

0 votes
answered by (175 points)
–3 votes
Option c
answered by Junior (667 points)

Related questions

Quick search syntax
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
49,541 questions
54,084 answers
70,994 users