Section 7 Chapter 40 - Hash Tables and Dictionaries

A data structure that creates a mapping between keys and values. The location of where an item is stored is determined by the hashing algorithm.

A process that determines the location of a value based on its key. For instance taking modulo of the key if it were an integer

A hashing algorithm. Every pair of numbers is added together and then moduloed. For insance: 123456 12 + 34 + 56 102 % 10 2

The ASCII values of each character are summed together and then a numerical hashing algorithm, for instance modulo, is used to obtain the hash.

1) Apply the hashing algorithm to the key 2) If the item is there then return it 3) If the cell is empty it is not in the table 4) If the item is a different one then move forward to the next cell and repeat from (2)

A collision occurs when two key values compute to the same hash

Rehashing is used. This is the process of finding an empty slot when a collision has occurred. The most simple rehash is to move forward one cell at a time until an empty one is found

An abstract data type that is a collection of key-value pairs in which the value is accessed via the associated key

Dictionaries often use hash tables in their implementation in order to provide faster response times for returning values