4,964 views

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.

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

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

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

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

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

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.

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

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 )
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
10,809 views