Hash Tables/Dictionaries

Question 1

When are Hash tables most commonly used?

Answer 1

When speed of look-up/deletion/insertion of items is a priority

Question 2

What is a hash table?

Answer 2

An array which has been coupled with a hash function

Question 3

What can hash tables help implement?

Answer 3

Hash tables can be used to implement dictionary data structures

Question 4

What is a hash function?

Answer 4

A piece of code that takes in data (key) and returns a value (the hash value)

Question 5

What is the hash value used for?

Answer 5

It maps the initial key to a fixed index in the hash table

Question 6

What happens when you first use the hash function?

Answer 6

It tells us where to store a piece of data in the hash table for a given key

Question 7

Why can we use the hash value to determine where in a hash table an item is stored?

Answer 7

Because the hashing function will always return the same value for a given key

Question 8

What happens if the hash function generates the same value for different keys?

Answer 8

As there is already a value stored in that location, a collision will occur

Question 9

What is a collision in hash tables?

Answer 9

When a hash function generates the same value for multiple keys

Question 10

What is a solution for dealing with collisions in hash tables?

Answer 10

One solution is to store the second generated values key in the next available location/index

Question 11

What should a good hash function be designed to do?

Answer 11

It should be designed to try to avoid creating duplicate hash values (however this may not be possible)

Question 12

What is continuing to store keys in the next available location known as?

Answer 12

It is known as clustering

Question 13

What is the problem with clustering?

Answer 13

It increases the probability of future collisions

Question 14

What is the best solution for dealing with collisions in hash tables?

Answer 14

The best solution is to use linked lists with the hash table.

Question 15

What happens when a collision occurs when using hash tables with linked lists?

Answer 15

If a collision takes place, the item is stored in overflow linked lists

Question 16

Why is using linked lists more efficient than using the clustering method?

Answer 16

• Linked lists allow for random fast access due to the array type data structure)
• It also avoids increasing the probability of future collisions

Question 17

What is a dictionary?

Answer 17

An abstract data type consisting of associated pairs of values. It’s used for storing groups of objects

Question 18

What does a dictionary data structure consist of?

Answer 18

It consists of a set of keys, each key has a single value associated with it

Question 19

How is data retrieved in a dictionary data structure?

Answer 19

When the key is supplied the associated value is returned

Question 20

What should an implemented dictionary be able to do?

Answer 20

• create a new empty dictionary
• add a key:value pair
• Delete a key:value pair
• amend the value in a key:value pair
• Return the value associated with a key
• Return True/False to a statement depending if a key exists in the dictionary
• Return the length of the dictionary

Question 21

What order are pairs held in a dictionary?

Answer 21

They are not held in any specific order

Question 22

Why is look up and retrieval quick and easy in dictionaries?

Answer 22

Because the key is hashed and placed in the resultant location

Question 23

Give an example of a common use of dictionary data structures.

Answer 23

They can be used in dictionary encoding (a type of compression)

Question 24

What is the code for creating a dictionary?

Answer 24

age = {‘Craig’ : 39, ‘Dave’ : 21, ‘Ella’ : 45}

Question 25

What is the code for returning a value in a dictionary?

Answer 25

> > > age [‘Craig’]

39

Question 26

What is rehashing?

Answer 26

The process of finding an empty slot when a collision occurs

Question 27

Give a real life example of what a hash table can be used for?

Answer 27

For storing user codes and encrypted passwords that need to be verified quickly