GATE CSE 1996 | Question: 15

Question

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.

• A. Which insertions cause collisions?

• B. Display the final hash table.

Comments

The question is not clear. ord() returns ascii values but according to this question, the string given should be considered all small letters of ascii range(97-122) and not capital(65-90), if we want to derive the right answer.

---

I think They hadn't given definitions clearly

Answer 1

Here $Order(x)-Order$ ('$a$') means count the number of characters between character $'x'$ and $'a'$.

Assuming  $a = 0, b = 1$ & so on.

1. $J \ \& \ M$ cause collusion.
2. Final Hash Table

$$\begin{array}{|l|l|} \hline \textbf{Index} &  \textbf{key}\\\hline \text{0}  & \text{T} \\\hline \text{1} & \text{K} \\\hline \text{2} & \text{J}  \\\hline \text{3} & \text{C} \\\hline \text{4} & \text{N} \\\hline \text{5} & \text{Y} \\\hline \text{6} & \text{P} \\\hline \text{7} & \text{M} \\\hline \text{8} & \text{R} \\\hline \text{9} & \text{S} \\\hline  \end{array}$$

Comments

What does Ord(x) mean

---

you can assume any numeric value where.. ord(b) = ord(a)+1. and so on ...

or you can think of ascii value for characters .. where ord(a)= 97,  ord(b) = 98 ..and so on.

---

Is only J and M causing collision?

T also causing collision with J. rt?

---

^ see, here J is colliding with T but not T with J.

Here, J is first colliding with T at 0th index.

And M is first colliding with C at 3rd index.

??

---

hm, correct

---

@vijay I tagged u in a question

could u chk it once.

---

^ sorry .. : p.. but could not see that .. can you please share that link again... or tell date so that I can search.. ??

---

https://gateoverflow.in/18749/tifr2010-b-26
this one :)

---

ord is method in the python(math library) if you write ord(A) then it will return the ascii value of A you can think that way that it will return you the ascii value of the character but no need to go in that much deep  just solve with any random number and choose accordingly like if a=10 then c=12 and so on

---

A) If we use {a=1,b=2.....x=24} we will get          same collision " J & M "

B) Hash table will change when value of a start with 1 instead of 0

---

@Prateek,No has table wont change.I did by taking a as 1 and got the same result. What change did u get by starting from 1?

The difference between order of x and order of "a" remains constant.

Lets us say k=11 if you start from 1 and a=1. now K-a+1=11-1+1=11

Lets us say k=10 if you start from 0 and a=0 now K-a+1=10-0+1=11

You can start from any index but offset/difference between an alphabet from a is fixed.adding +1 to that is same.So answer should be same

---

@vijaycs

For K: (ascii value of 'K'-ascii value of 'a')+1 mod 10

(75-97+1)%10=-21%10=9

please explain why its 1?

---

Similar question asked in isro'17

https://gateoverflow.in/182100/isro-dec2017-50?show=211012

---

They should give the definitions clearly.

---

@pratik2404 The instructions are clear. You don’t need ASCII values (or the knowledge of ord) for this q. 

$( ord (x) – ord (\text{“}a\text{”}) + 1)$ The position of the element x in the alphabet series

[Eg: C =3, J =10, K = 11]

---

@Abhrajyoti00 So ord(“a”)  is same as ord(“A”)..?

---

@pratik2404 definitely not. But it does not matter because ord(“a”) is just like a constant (say 0). So if you subtract all letters from the constant value, they will still be in alphabetical order right?

---

@Abhrajyoti00 Yes. I got your point, actually it is relative positioning that’s why here ascii & other things doesn’t matter & it is obvious; if they aren’t mentioning about ascii then you can assign any value to any letter & others will get relative value of that letter, so final hash function value will be same. I think instead of Ord(“a”) they should mention Ord(“A”), then it will be more clear, again this is my personal opinion. By the way thanks!

---

total number of collision is $6$, please verify it.

Answer 2

Ord(x)-Means ordinal values of character x.

A string can be mapped to a hash table based on some function of which works upon the ordinal values of the characters involved in the string.

According to various sources I searched, ordinal values of a character is nothing but an ASCII Value.

References :

https://cs.nyu.edu/courses/spring99/A22.0002.002/lecture_notes/lecture5/node17.html

https://cs.nyu.edu/courses/spring99/A22.0002.002/lecture_notes/lecture5/node16.html

https://stackoverflow.com/questions/19174563/what-is-an-ordinal-value-of-a-string

So, Ord('a')=97

But here we have to be cautious because the given input is in Capital letters and hash function uses Ord('a')

So, A-Z has ordinal values from 65-90.

So h('K') = (ord('K')-ord('a') +1)mod 10 = (22+1)mod 10=3

So, hash locations are

Input	Hash Index
K	3
R	6
P	8
C	1
S	5
N	0
Y	9
T	4
J	4
M	1

The marked entries cause collision.

Final hash table

0	N
1	C
2	M
3	K
4	T
5	S
6	R
7	J
8	P
9	Y

Comments

Question is incomplete as meaning for ord is not mentioned!! If we consider ASCII value then T and  J will collide and C and M will collide as well.

---

@vijaycs

For K: (ascii value of 'K'-ascii value of 'a')+1 mod 10

(75-97+1)%10=-21%10=9

please explain why its 1?

---

The question is not clear. ord() returns ascii values but according to this question, the string given should be considered all small letters of ascii range(97-122) and not capital(65-90), if we want to derive the right answer.

Answer 3

Hash function h(x) = ((ord(x) – ord(A) + 1)) %10

Given string is K R P C S N Y T J M. Take alphabetic ordering of each character is worth saving time to solve these questions. Therefore,

K will be inserted at index (11-1+1)%10 = 1

R at index (18-1+1) %10 = 8

P at index (16-1+1) % 10 = 6

C at index (3-1+1) % 10 = 3

S at index (19-1+1) % 10 = 9

N at index (14-1+1) % 10 = 4

Y at index (25-1+1) %10 = 5

T at index (20-1+1) % 10 = 0

J at index (10-1+1) %10 = 0 (Ist collision occurs, because 0th index is already filled by T).

M at index (13-1+1) % 10 = 3 (2nd collision occurs, because 3rd index is already filled by C).

Only J and M causes collision.

Final Hash table will be:

0	T
1	K
2	J
3	C
4	N
5	Y
6	P
7	M
8	R
9	S

 

Comments

why did we consider only J,M and not T,J as well?

---

We didn’t consider T,C because they are already inserted into hash table w/o any collision. Only when inserting J,M they cause collision (i.e getting hashed to index 0 and index 3 respectively which are already occupied )

Answer 4

J,M causes collision..
Hash table (0-9) ={T,K,J,M,C,N,Y,P,R,S}

Comments

What is the meaning of ord(x) here ?