Hash Tables/Dictionaries Flashcards
When are Hash tables most commonly used?
When speed of look-up/deletion/insertion of items is a priority
What is a hash table?
An array which has been coupled with a hash function
What can hash tables help implement?
Hash tables can be used to implement dictionary data structures
What is a hash function?
A piece of code that takes in data (key) and returns a value (the hash value)
What is the hash value used for?
It maps the initial key to a fixed index in the hash table
What happens when you first use the hash function?
It tells us where to store a piece of data in the hash table for a given key
Why can we use the hash value to determine where in a hash table an item is stored?
Because the hashing function will always return the same value for a given key
What happens if the hash function generates the same value for different keys?
As there is already a value stored in that location, a collision will occur
What is a collision in hash tables?
When a hash function generates the same value for multiple keys
What is a solution for dealing with collisions in hash tables?
One solution is to store the second generated values key in the next available location/index
What should a good hash function be designed to do?
It should be designed to try to avoid creating duplicate hash values (however this may not be possible)
What is continuing to store keys in the next available location known as?
It is known as clustering
What is the problem with clustering?
It increases the probability of future collisions
What is the best solution for dealing with collisions in hash tables?
The best solution is to use linked lists with the hash table.
What happens when a collision occurs when using hash tables with linked lists?
If a collision takes place, the item is stored in overflow linked lists
Why is using linked lists more efficient than using the clustering method?
- Linked lists allow for random fast access due to the array type data structure)
- It also avoids increasing the probability of future collisions
What is a dictionary?
An abstract data type consisting of associated pairs of values. It’s used for storing groups of objects
What does a dictionary data structure consist of?
It consists of a set of keys, each key has a single value associated with it
How is data retrieved in a dictionary data structure?
When the key is supplied the associated value is returned
What should an implemented dictionary be able to do?
- 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
What order are pairs held in a dictionary?
They are not held in any specific order
Why is look up and retrieval quick and easy in dictionaries?
Because the key is hashed and placed in the resultant location
Give an example of a common use of dictionary data structures.
They can be used in dictionary encoding (a type of compression)
What is the code for creating a dictionary?
age = {‘Craig’ : 39, ‘Dave’ : 21, ‘Ella’ : 45}
What is the code for returning a value in a dictionary?
> > > age [‘Craig’]
39
What is rehashing?
The process of finding an empty slot when a collision occurs
Give a real life example of what a hash table can be used for?
For storing user codes and encrypted passwords that need to be verified quickly
