Hash Tables/Dictionaries Flashcards Preview

Paper 1 - Computer Science > Hash Tables/Dictionaries > Flashcards

Flashcards in Hash Tables/Dictionaries Deck (27)
Loading 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']


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