# 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