Hash tables

Question 1

What are the requirements for a Hashing function

Answer 1

Generate numeric value from a key
Uniform spread of indices
Minimise collisions

Question 2

What is the mid-square method

Answer 2

First square the item.
Take the middle of the result
Then do the MOD for the address

Question 3

What is the folding method

Answer 3

Divide item into equal pieces
Add the pieces together
Then do MOD

Question 4

How many amount of slots should there be

Answer 4

The number of assigned slots must exceed the number of records by a third

Question 5

What happens if the hash table becomes >70% full

Answer 5

The hash table will be re-sized

Question 6

What happens if there is a collision

Answer 6

1. Rehashing: If there is a collision it will find the next available hash.
2. Create a linked list (Chaining): If there is a collision it will create a list that is linked to the hash

Question 7

Use of hash tables

Answer 7

Can be used in check sums with barcode readers.
It can also be used in digital signatures for asymmetric encryption.

Question 8

How are hash slots deleted

Answer 8

They will be marked with a dummy item. If a new item is added to the hash slot it will replace the dummy item.

Question 9

How are hash tables used in asymmetric encryption

Answer 9

When a file is sent a hash algorithm is calculated giving a unique hash.
The file is sent with a public key and digital signature
The receiver decrypts the digital signature using the given public key
Then calculates the hash and compares to original hash