edited by
6,149 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.

edited by

4 Answers

Best answer
25 votes
25 votes

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

 

Related questions

39 votes
39 votes
6 answers
1
Kathleen asked Oct 9, 2014
13,627 views
An advantage of chained hash table (external hashing) over the open addressing scheme isWorst case complexity of search operations is lessSpace used is lessDeletion is ea...
54 votes
54 votes
7 answers
2
Kathleen asked Oct 9, 2014
22,708 views
A binary search tree is used to locate the number $43$. Which of the following probe sequences are possible and which are not? Explain.$\begin{array}{llllll} \text{(a)} ...
29 votes
29 votes
3 answers
3
Kathleen asked Oct 9, 2014
12,124 views
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?$1$$3$$7$$8$
21 votes
21 votes
3 answers
4
Kathleen asked Oct 9, 2014
4,305 views
Which of the following sequences denotes the post order traversal sequence of the below tree?$f\; e\; g\; c\; d\; b\; a$$g\; c\; b\; d\; a\; f\; e$$g\; c\; d\; b\; f\; e\...