Hashing

Question 1

What is hashing?

Answer 1

• Using a Hash function on data to create a ‘unique’ hash
• This hash determins the position the data is stored at (in the hash table or on a hard disk)

Question 2

What is a collision

Answer 2

When two peices of data hash to the same index(hash value). This means the second being added wont be able to be stored in this index.

Question 3

Two methods of dealing with collisions?

Answer 3

• Open hashing
• Closed hashing

Question 4

What is open hashing?

Answer 4

• If a collision happens the inserted data is asigned to the next avalable index.
• This increases chance of future collisions
• And increases search time ( to as bad as O(n) as the whole hash table must be checked if a deletion symbol wasnt used.)

Question 5

What is closed Hashing

Answer 5

Each array position in the Hash table is a linked list.

The inserted data gets added onto the end of the correct linked list.

Question 6

What makes a good hash function?

Answer 6

• Makes use of all information in key
• Uniformly distributed output across range.
• Uses fast operations (as its called a lot)
• maps similar keys to very different hashes

Question 7

What is the complexity of accesing ahash table?

Answer 7

Constant time, provided no colisiions have happened.

Question 8

Rougly how much space should be in the hash table?

Answer 8

1.5 times the amount of data eeding to be hashed and stored. to reduce collisons

Question 9

When is hashing used?

Answer 9

Data comms to create a hash of the data being sent, used for checking data is untampered.

Storing data in a way that makes it fast to locate.

In RAM

Look up tables (eg phone book)

Encrypting passwords

Question 10

what is a hash function?

Answer 10

A function H, applied to a key k; which generates a hash value ((of range smaller than the domain of values of k)

(A function which computes a record position within a specified range)