GATE CSE 2007 | Question: 40

Question

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.

• A. $8$, −, −, −, −, −, $10$

• B. $1, 8, 10$, −, −, −, $3$

• C. $1$, −, −, −, −, −, $3$

• D. $1, 10, 8$, −, −, −,$ 3$

Comments

Open Hashing (Separate Chaining): In open hashing, keys are stored in linked lists attached to cells of a hash table. Closed Hashing (Open Addressing): In closed hashing, all keys are stored in the hash table itself without the use of linked lists.

---

closed hashing also called linear probing.

---

i agree, hashing terms are very confusing 😭😭😭

• $\underline{Open \ hasing} = seperate \ chaining \rightarrow$ It's called $\underline{open}$ because the data is allowed to leave the main array and grow out into the open space of your memory using linked lists
   
• also, $\underline{Open \ hashing }= \ \underline{closed \ addressing}$, i.e once you enter a slot you are closed there can't be mapped to any other slot
   
• $\underline{closed \ hasing} \rightarrow$ It's called $\underline{closed}$ because the data is strictly confined (closed in) to the fixed size of the hash table array. If there's a collision, you have to find an open address somewhere else inside the same array.
   
• also, $\underline{closed \ hasing} \rightarrow$ $\underline{Open \  addressing}$

Answer 1

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$.

Comments

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

http://www.dcs.gla.ac.uk/~pat/52219/l04.html

---

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?
or

(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.

---

Closed hashing = Open Addressing

---

@ AspiROsa

which is occupied.
Next will be

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

(3x+4)mod7 +1

Ofcourse second one (3x+4)mod7 +1 or you can also say (3x+4+1)mod 7.

because we are using linear probing. So, nearest slot after that will be checked first.

Answer 2

B

 

Answer 3

https://youtu.be/1maxi3Yq-CU