Yr2 Hash Tables

Question 1

What is a hash table?

Answer 1

Where data is stored is determined by hashing said data to produce the number corresponding to a memory location based

Question 2

What is the theoretical speed of a hash table search?

Answer 2

O(1)

Question 3

What is a big issue with hash tables?

Answer 3

Collisions - collisions are where two pieces of data produce the same memory location when hashed

Question 4

What are the two solutions to hash table collisions?

Answer 4

1. Overflow (best solution)
2. Storing in the next memory location

Question 5

How can overflow be used to solve a hash table collision?

Answer 5

Using a linked list store both pieces of data in the same memory location and refer to them using pointers when needed.

Question 6

What issues are there with using overflow to solve a hash table collision?

Answer 6

The memory location may be unable to store both pieces of data if they are too large

Question 7

What problems are there with storing data int he next memory location in order to solve hash table collisions?

Answer 7

It increases the chance of collisions in the future

Question 8

What is a dictionary?

Answer 8

A data structure that maps items to other specified values