Hash Tables/Dictionaries Flashcards Preview

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

Flashcards in Hash Tables/Dictionaries Deck (27)
Loading flashcards...
1

When are Hash tables most commonly used?

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

2

What is a hash table?

An array which has been coupled with a hash function

3

What can hash tables help implement?

Hash tables can be used to implement dictionary data structures

4

What is a hash function?

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

5

What is the hash value used for?

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

6

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

7

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

8

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

9

What is a collision in hash tables?

When a hash function generates the same value for multiple keys

10

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

11

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)

12

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

It is known as clustering

13

What is the problem with clustering?

It increases the probability of future collisions

14

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

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

15

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

16

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

17

What is a dictionary?

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

18

What does a dictionary data structure consist of?

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

19

How is data retrieved in a dictionary data structure?

When the key is supplied the associated value is returned

20

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

21

What order are pairs held in a dictionary?

They are not held in any specific order

22

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

Because the key is hashed and placed in the resultant location

23

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

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

24

What is the code for creating a dictionary?

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

25

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

>>> age ['Craig']
39

26

What is rehashing?

The process of finding an empty slot when a collision occurs

27

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