Hash Tables

Question 1

Hash tables

Answer 1

• store key value pairs

- usually are a fixed size array of some prime number size (that is larger than the num of elements)

Question 2

Hash function

Answer 2

takes in a thing and returns an unsigned integer value which is then mod’ed by the size of the table and places there!

Question 3

Three required properties of fast hash functions

Answer 3

• must be deterministic (same value every time for a key)
• must be fast
• must be evenly distributed

Question 4

Integer overflow is fine , as long as the function is deterministic meaning??

Answer 4

Overflow will almost always occur, just make sure the function returns the same num every time!

Question 5

Two ways to resolve collisions?

Answer 5

Separate chaining

Open Addressing

Question 6

Three types of open addressing?

Answer 6

Linear probing
Quadratic Probing
Double Hashing

Question 7

Separate Chaining

Answer 7

All keys map to a linked list, which can add additional values that are mapped

Question 8

Load factor

Answer 8

ratio of number of elements divided by table size

Question 9

In separate chaining, the load factor is….

Answer 9

the average number of elements in a bucket

Question 10

Average time of a unsuccessful find?

Answer 10

Load factor!

Question 11

Average time on a successful find?

Answer 11

1 + (loadfactor/2)

Question 12

Smaller the load factor, the more memory it uses, but the few collisons!

Answer 12

True

Question 13

Bigger load factor uses…

Answer 13

less memory but is slower

Question 14

Why is it necessary to keep each key in the chain as well as the value?

Answer 14

Because otherwise you can’t be sure which collision value is the value you’re looking for!

Question 15

Linear probing checks spots in what order starting with hash(k)

Answer 15

hash(k)+1
hash(k)+2
hash(k)+3
hash(k)+4
......

Question 16

Probs with linear probing?

Answer 16

large blocks of occupied cells you have to check

-holes when an element is removed…

Question 17

quadratic probing order

Answer 17

hash(k)
hash(k)+4
+9
+16

Question 18

Double hashing

Answer 18

2 hash functions!

hash(k)
hash(k) +1hash2(k)
hash(k)+2hash2(k)

Question 19

Wjhy does the table size have to be prime with double hashing?

Answer 19

So that it will prevent thrashing, and also will lead to a better distribution

Question 20

Rehashing

Answer 20

• when table is too full (load factor is too high), runninng time increases, so you should rehash
• when insert fails DEFINITELY rehash

Question 21

Rehashing means

Answer 21

creating bigger array and rehashing each value already in the array

Question 22

How to remove an element in open addressing?

Answer 22

• rehash upon every delete (not a good idea)
• put in a placeholder value that you know is fake!… however the table would get filled with placeholders on the faster side…

Question 23

Pigeonhole principle

Answer 23

There would be at least one hash value with multiple keys… making an object unable to be backtraced to its key