Ch 8: Hash Tables

Question 1

what is a hash table?

Answer 1

a data structure that stores unordered items by mapping (hashing) each item to a location in an array (or vector)

Question 2

what is the main advantage of hash tables?

Answer 2

an item may require only O(1) insert, remove and search

Question 3

what is a key?

Answer 3

a value used to map to an index

Question 4

what is a bucket?

Answer 4

each hash table array element

Question 5

what is a hash function?

Answer 5

computes a bucket index from the item’s key

Question 6

what is collision?

Answer 6

occurs when an item is inserted into a hash table maps to the same bucket as an existing item in the hash table

Question 7

what is chaining?

Answer 7

a collision resolution technique where each bucket has a list of items

Question 8

what is open addressing?

Answer 8

a collision resolution technique where collisions are resolved by looking for an empty bucket elsewhere in the table

Question 9

what is linear probing?

Answer 9

handles a collision by starting at the key’s mapped bucket, then linearly searches subsequent buckets until an empty bucket is found

Question 10

what are two types of buckets? define them

Answer 10

empty-since-start: has been empty since the hash table was created
empty-after-removal: had an item removed that caused the bucket to now be empty

Question 11

why does search stop at an empty-since-start but not an empty-after-removal?

Answer 11

stops because if previously inserting the item had reached that bucket, then it would have put it there. but since it has been empty since the start, it must not have been inserted

Question 12

explain removal with linear probing

Answer 12

• determine the initial bucket
• probe each bucket until a matching item is found, an empty-since-start bucket is found, or all buckets have been probed

Question 13

what is quadratic probing?

Answer 13

starting at the key’s mapped bucket, and then quadratically searches subsequent buckets until an empty bucket is found

Question 14

what is the hash table function for quadratic probing

Answer 14

(H + c1 *i + c2&(i^2)) mod (tablesize)
H: item’s initial mapped bucket
c1 & c2: programmer definined constants for quadratic probing
i: increment

Question 15

explain insert for quadratic probing

Answer 15

• use formula, starting with i = 0 to find bucket
• insert if bucket is empty
• otherwise, increment i and use the formula to find a new bucket, repeat

Question 16

what is a probing sequence?

Answer 16

iterating through sequential i values to obtain the desired table values

Question 17

when is a hash table fast?

Answer 17

if it minimizes collision

Question 18

what are perfect hash functions?

Answer 18

maps items to buckets with no collisions

Question 19

when can a perfect hash function be created?

Answer 19

if the number of items and all possible key item keys are known before hand

Question 20

what do good hash functions do?

Answer 20

uniformly distribute items into buckets

Question 21

chaining and a good hash result in what?

Answer 21

short bucket lists so faster inserts, searches and removes

Question 22

what is the average & worst case operation run times on good hash functions?

Answer 22

average: O(1)
worst: O(n)

Question 23

what is a modulo hash?

Answer 23

uses remainder from division of key by hash table size

Question 24

what is a midsquare hash?

Answer 24

squares the key, extracts R digits from the results middle and returns the remainder of the middle digits divide by hash table size

Question 25

what is a multiplicative string hash?

Answer 25

repeatedly multiplies the hash value and adds the ASCII value of each character in the string

Question 26

what is a direct hash function?

Answer 26

uses the item's keys as the bucket index

Question 27

what is a direct access table?

Answer 27

a hash table with a direct hash function

Question 28

what is the advantage of a direct access table?

Answer 28

no collision

Question 29

what are the two main limitations of a direct access table?

Answer 29

1. all keys must be non-negative integers, but for some applications, keys may be negative 2. the hash table's size equals the largest key values plus 1, which may be very large

Question 30

what is double hashing?

Answer 30

an open-addressing collision resolution technique that uses 2 different hash functions to compute bucket indices

Question 31

what is the key index for double hashing?

Answer 31

(h1(key) + i*h2(key))mod(tablesize)

Question 32

what size is a table resized to?

Answer 32

the next prime number >= N*2

Question 33

what is the run time complexity of resizing and why?

Answer 33

O(n) because the old array is reindexed to new array

Question 34

what is a load factor?

Answer 34

if of items in the hash table divided by the # of buckets

Question 35

when does resizing often occur?

Answer 35

when 1+ values exceed a certain threshold: 1. load factor 2. when using open-addressing, the # of collisions during an insertion 3. when using chaining, the size of bucket's linked list