in DS edited by
6,122 views
24 votes
24 votes

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.

  1. Which insertions cause collisions?

  2. Display the final hash table.

in DS edited by
6.1k views

2 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.
6
6
edited by
I think They hadn't given definitions clearly
0
0

4 Answers

25 votes
25 votes
Best answer

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

edited by

4 Comments

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

0
0

@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!

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

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

4 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.
0
0
@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?
1
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.
0
0
5 votes
5 votes

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

 

2 Comments

why did we consider only J,M and not T,J as well?
0
0
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 )
0
0
2 votes
2 votes
J,M causes collision..
Hash table (0-9) ={T,K,J,M,C,N,Y,P,R,S}

1 comment

What is the meaning of ord(x) here ?
1
1