Section 7 Chapter 40 - Hash Tables and Dictionaries

Question 1

Hash Table

Answer 1

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.

Question 2

Hashing Algorithm

Answer 2

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

Question 3

Folding method

Answer 3

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

Question 4

How to hash a string

Answer 4

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

Question 5

Process for searching for an item in a hash table

Answer 5

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)

Question 6

Collision

Answer 6

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

Question 7

Collision resolution

Answer 7

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

Question 8

Dictionary

Answer 8

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

Question 9

How hash tables and dictionaries are related

Answer 9

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