Tables and Hashing

Question 1

What is a ADT Table: Data?

Answer 1

• A table is a collection of entries, where each entry contains:
  
  • a key(unique identifier for the entry)
  • rest of the entry (other data associated with this entry

Sometimes called a dictionary

Question 2

What are a table’s standard operations?

Answer 2

Question 3

What are the posibiities for implementing a table and what are the advantages/disadvantages?

Answer 3

Question 4

What is the most important table operation?

Answer 4

search/retrieve

Question 5

How fast is a hash table, insert, delete and search?

Answer 5

O(1)

Means that execution time is independent of problem size, it takes a constant number of operations

Question 6

What is the general idea of how to implement an ADT table using a hash table?(psudo code)

Answer 6

Question 7

What is a Hash function?

Answer 7

A mathematical function that, given a key k gives an index h(k) into the hash table(an array) where the item with key k can be found.

Example:

• Keys are in 0,1,2,3,…
• So use h(k) = k
• Search, insert, delete would all take O(1) time in an array

Question 8

What are the potential problems with the simple hash function?

Answer 8

The keys could be:

• Large (compared to a smaller array size)
• Alpha-numeric(non-numeric, at least)
• Collisions (two keys hashing to the same location)

Question 9

What must a good hash function do?

Answer 9

• Minimize collisions
• fast to compute
• Hash values should be evenly distributed, even if the keys are not

Question 10

What are the two steps of a hash function?

Answer 10

1. Make the key an integer(called a hash code) - If it isn’t an integer, map the key to some integer
2. Make the integer into an array index(compression map) - Map the hash code into the desired array index range.

Question 11

When turning a key into a hash code that has the same size of int, such as short, char and float?

Answer 11

treat the key as an int, cast it to an int

Question 12

Hash code: how do you turn a key that is longer than an int into a hash code?(example double or long)

Answer 12

• Split the key into int-size pieces and add them together
• Can’t just use one piece as the hash code, that piece may be identitical or similar to a lot of different keys, leading to clustering and collisions

Question 13

How do you turn a non-integer key into an integer hash code?

Answer 13

1. Divide the key into a sequence of int-sized chunks
2. Treat each chunk as an int
   
   • example String:
     
     • Get the character at position i: word.charAt(i)
     • cast the character at position i into an int: (int)word.charAt(i)
3. Turn the sequence of integers into one integer using the polynomial hash code

Question 14

Why use a polynomial hash for Strings? Why can’t we just add the characters together?

Answer 14

The polynomial hash code gives uniform distribution on english words.

Just adding the characters together ignores the position (commutative property) which differentiates words. “stop”, “pots”,”opts” would all hash to the same index

Question 15

How can you computer the polynomial hash code efficiently? What’s the difference in speed?

Answer 15

The inefficient is (s(s+1))/2 multiplications

Factor out the common factor (a) using Horner’s method.

With Horner’s method there is S additions and S multiplications

Question 16

How does Horner’s method work? Provide an example using the String “cat”

Answer 16

Processes the characters left to right, starting with hash code = 0

for each character:

• Multiply the current hash code by a and then
• add on to the next character
• do the computation mod the table size at each step so that the value computed doesn’t cause an integer overflow

Question 17

What are the problems with a simple compression map

(using h(k) = |k| mod N(has table size)

Answer 17

• If hash code k is even, then h(k) is even, meaning it will only hash to an even key in the table
• If the table is divisible by 5 (N = 10) then only positions 0 or 5 will be used in the hash table
  
  • In general, if k and N are divisible by b, then h() is divisible by b (leading to many collisions)

Question 18

What is the problem with Polynomial Hash Code, Horner’s Method and Overflow? What is the solution?

Answer 18

Problem: When finding the polynomial hash code for a longer string, you can get an integer overflow quite quicky - all those large powers of a add up quickly

Solution: After every step in Horner’s method, take the current computer value mod N and use that in the next step

(current value*a+next letter) mod N