Draw the contents of the hash table

158 views 13/10/2021 admin 0 Comments binary encoding, hash function, hash table

Problem 1

Draw the contents of the hash table in the boxes below given the following conditions:
So The size of the hash table is 12.
And Open addressing is used to resolve collisions.
So The hash function used is H(k) = k mod 12
So What values will be in the hash table after the following sequence of insertions? Draw the values in the boxes below, and show your work.
33, 10, 9, 13, 12, 45, 26, 17
0 1 2 3 4 5 6 7 8 9 10 11

Answer:

So Here we have to insert values which are 33, 10, 9, 13, 12, 45, 26, 17
In open addressing hashing, values in the table are stored by itself. So There are three ways of insertion they are linear probing, quadratic probing and double hashing. Here we use linear probing in this question.

Insert 33,

So Position= 33%12= 9 (insert 33 at 9 position)
0 1 2 3 4 5 6 7 8 9 10 11
33

Insert 10,
So Position= 10%12= 10 (insert 10 at 10 position)
0 1 2 3 4 5 6 7 8 9 10 11
33 10

Insert 9,
So Position= 9%12= 9
Collision occurs so we move to the next place, 10, where also the data is stored so we move to the next position 11.
0 1 2 3 4 5 6 7 8 9 10 11
33 10 9
Insert 13,

So Position= 13%12= 1 (insert 13 at 1 position)
0 1 2 3 4 5 6 7 8 9 10 11
13 33 10 9
Insert 12,

So Position= 12%12= 0 (insert 12 at 0 position)
0 1 2 3 4 5 6 7 8 9 10 11
12 13 33 10 9
Insert 45,

So Position= 45%12= 9
A collision occurs so we move to the next place, 10, where also the data is stored so we move to the empty next position 2.
0 1 2 3 4 5 6 7 8 9 10 11
12 13 45 33 10 9

Insert 26,
So Position= 26%12= 2
Collision occurs so we move to the next place,3,
0 1 2 3 4 5 6 7 8 9 10 11
12 13 45 24 33 10 9
Insert 17,

So Position= 17%12= 5
0 1 2 3 4 5 6 7 8 9 10 11
12 13 45 24 17 33 10 9

Problem 2

So In this problem, you are required to design a hash function named Bailando on textual words composed of 5 characters (characters from a – z and A – Z).

a. So Provide an algorithm (set of operations) to generate the output of your hash function. Try to come up with a hash design that has seemingly no collisions.

b. So What is Bailando(“hello”), Bailando(“three”), and Bailando(“olleh”) based on your design.

c. So Can you find any two 5-character words that generate a collision in your hash design?

d. How can you improve your function to reduce the number of collisions?

Answer

Bailando= (alphabet value of char) mod 26.
So Here we use linear probing to solve the collision. So there are 26 letters in alpjabets and 5 letters in the input.

So For example,
Bailando(“noise”)= 14,15,9,19,5
Insert n, position= 14 mod 26= 14 (insert at 14)
Insert o, position= 15 mod 26= 15 (insert at 15)
Insert i, position= 9 mod 26= 9 (insert at 9)
Insert s, position= 19 mod 26= 19 (insert at 19)
Insert e, position= 5 mod 26= 5 (insert at 5)

So next is:

⦁ Bailando(“hello”)= 8,5,11,12,14
Bailando(“three”)= 20,8,18,5,6
Bailando(“olleh”)= 14,11,12,5,8
⦁ Example of collision is in input “hello” and “Hatch”.
⦁So To avoid this collision, we can use mod 5 function and chaining in case of collision.
Bailando(“hello”)=

- Insert h, position= 8 mod 5=3
- Insert e, position= 5 mod 5= 0
- Insert l, position= 11 mod 5= 1
- Insert l, position= 11 mod 5= 1
- Insert o, position= 14 mod 5=4

It will be stored as:
0 →e
1 →l→l
2
3→h
4→o

Problem 3

Do some research to solve the following problem:
So Consider a hash function having available addresses and records to be stored.

What is the packing density of this hash function?
So How many addresses are expected to go unused?
So How many addresses contain no synonyms?
So How many addresses contain two or more synonyms?

Answer

So Here we enter 33, 10, 9, 13, 12, 45, 26, 17 in the table which is a hash table with the hash function H(k) = k mod 12

- Packing density= number of used address/number of unused address= 8/12= 0.66
- The number of unused addresses is: 12-8= 4
- 10,13,12 and 17 are the values with no synonyms
- 33,9,45 are synonyms
  45 and 26 as also synonym

Problem 4

So Consider a textual file that is to be compressed using Huffman coding. Each character in the file is assumed to occupy 3 bits in storage. This allows us to have an alphabet of 8 characters. The frequency of occurrence of each character in the file is provided in the following table.
a 11.9% e 6.7%
b 9.6% f 7.7%
c 24.7% g 9.2%
d 28.3% h 1.9%

(a) So Construct the Huffman tree based on the above frequency table.
Note: In order to ensure that the tree construction is unique, use 0 to label the edge that goes to the subtree having the leaf with the alphabetically biggest label (among all labels in the two subtrees).

So For example, if a node’s two subtrees contain leaves labeled by (c, d, and f) and by (a and e), respectively, then the edge into the (c, d, and f) subtree should be labeled 0, because f is the biggest alphabetically among all the labels in the two subtrees.

(b) Show the binary encoding of each character based on the tree constructed in part a.

(c) Computer the compression rate (the ratio between the lengths of the compressed file and the original file). Show your work.