Ideal Hash Table

• Stores unique data in an array (no duplicates)
• where the key is associated with the index
• by a hashing function
The mapping is unique, that is, a particular key value yields an index (i) and no other key will produce the same index (i)
A one-to-one function
• Really ideal would allow no wasted space in the array
• A one-to-one, onto function (bijective)

• Employee numbers
• Assigned from 1 to numEmployees
• No deletions - just flag the record
• New employee added at end (numEmployees++)
• Employee number is the index
• h(x) = x
• Insert, delete, search are all O(1)
• Practical?
• Wal-Mart has 2.2 million employees world-wide
• If each record contains only an integer reference (index),
• the array size is over 8 Mb

• Consider words to be numbers
Each letter represents a digit...
• Convert to a base 27 number
Blank --> 0
a --> 1
z --> 26
• Convert to decimal to get index
• cats => 3*27³ + 1*27² + 20*27¹ + 19*27⁰
• --> 3 1 20 19₂₇ = 60,337₁₀
• But we have empty cells for neighbors:
...catp, catq, catr, catt, catu...
Four letter words implies
zzzz => 26*27³ + 26*27² + 26*27¹ + 26*27⁰ = 531,440 entries
32 Gb RAM => 235 = 3.5E10
The log base 27 of 3.4E10 is 7.4 => 7 letter words (max)
The longest word we can represent in 32GB is 7 letters long
Pseudopseudohypoparathyroidism (30 chars)
Longest non-coined word in a major dictionary (wikipedia)

• Words/strings are commonly "hashed"
• Compiler symbol tables
• reduce the range of the mapping function
Allow mapping function to be many:1
apply an alternate strategy if a collision occurs
• Goal: ensure ~O(1) for insert, delete & search

• Assume 50,000 words
• Make array twice this size: 100,000
• Hashing function:
1. Calculate the unique location of a word: bigIndex
2. Return smallIndex = bigIndex % size_of_array
3. Multiple words now hash to same location
   Need to handle collisions
• extra space (50,000)
• zyzzyva => 26*27⁶ + 25*27⁵ + 26*27⁴ + 26*27³ + 25*27² + 22*27¹ + 1*27⁰
• bigIndex == 10,446,003,433
• A.length == 100,000
• smallIndex = 3,433

• Separate chaining (https://www.cs.usfca.edu/~galles/visualization/OpenHash.html)
Create a linked list of elements for each location in the array
Java uses this closed addressing, "bucket" approach
• Open addressing (https://www.cs.usfca.edu/~galles/visualization/ClosedHash.html)
When a collision occurs a cell is occupied
Search for an empty cell starting at the hash location
Insert, delete and find operations all must use same strategy for searching

Open Adressing - Linear Probing

• class DataItem, class HashTable: Hash Code
• Visualization

1. index = h(key)
2. If A[index] is occupied already

// find the next availabe spot
1. While (! available(A[++index])) /do nothing/ ;
2. Place item in location index
3. Note that if table is full => infinite loop, so check!
4. index = (index + 1) % A.length(); // circular array

1. index = h(key)
2. If A[index] is occupied & key does not match
3. While (! empty(A[++index])
   1. If key matches return index
   2. Else keep going
   3. Circular increment
4. Didn't find it

1. index = h(key)
2. While (! empty(A[++index])
   1. If key matches
      mark as deleted
      return item
   2. Circular increment
3. return error (null)

• A filled sequence of cells is called a cluster
• Probe length =
• number of steps taken from the hashed index
  i.e., a count of the ++index operations needed
• Ranges from 1 to N (is N if every key hashed to same index )
• Clustering becomes worse as array fills up
• More likely to hit a cluster, probes are longer
• Severe degradation when load factor is more than 2/3
• load factor = ratio of number of items to array size
• When load factor get high enough...
• Grow & rehash everything

Open Addressing - Quadratic Probing

• Linear probing uses a step size of 1
h(key)+1, h(key)+2, h(key)+3, h(key)+4,...
• Quadratic Probing uses square of the step
h(key)+1, h(key)+4, h(key)+9, h(key)+16,...
• Visualization
• Avoids primary clustering by trying to jump over
• Quadratic Probing Issues:
  1. may overflow the int variable (after ~46K steps in Java)
  2. quadratic pattern may cause secondary clustering
  3. Cells that hash to same location will all try the same sequence of steps
  4. May go into infinite loop if size of array is not a prime number

• Clustering occurs because
1. For primary, we use the same stepSize for all keys
2. For secondary, a set of keys that hash to the same index will then follow the same sequence of probes
• Double hashing uses a constant step size > 0
• Determined by a second (different) hash function
• A well-behaved secondary hash function:
1. K == prime number < size of array (also a prime)
2. stepSize = K - (key % K) // use key, not h(key)
• Visualization
• Hash Double Code

• Based on arrays - not dynamic
• Vectors don't solve the problem
1. Can't simply increase size and copy elements
2. Each element has to be re-hashed into the larger array (or vector)
• Can't easily "traverse" the hash table in order
• Severe performance degradation caused by collisions
• high load factor
• Select size of array so that...
It never becomes more than half-full
It doesn't have to be resized
• Re-hashing everything takes a long time
• Want...
1. Every cell is eventually visited by collision algorithm
2. Collision algorithm stops... no infinite loops
3. Smallest prime number >= 2 * size of data space

Hash Table w/ Separate Chaining

• The hash table itself is an array of linked lists
• Initially all lists are empty
• When a key maps to a particular index
• Insert the item into the linked list at that index
• typically InsertInOrder()
• 
• Hash chain Code Visualization
• Another View - add new collision record at either end of list
• 

• Load factor may be > 1 (graceful degradation)
• N or more items in an array of size N
• Still want a prime number for array size
• Let M be the average number of items in a list
Insert, find & delete are O(M) for a sorted list
Still go directly to cell that holds this list
• Duplicates not a problem
• Buckets: use a static array at each cell
• Buckets may waste space or overflow

• Use only "real" data, get rid of excess bits
• Use all of the "real" data
• tableSize is prime -- Otherwise keys that share a divisor with tableSize will tend to cluster
• Lafore's hash function for words meets strategies. But will overflow for long strings
• What is real data?

public static hashFunc3(String key) { 
   int hashVal = 0;
   for (int j=0; j<key.length(); j++) {
       int letter = key.charAt(j) - 96;  // get char code 
       hashVal = (hashVal * 27 + letter) % arraySize; 
       } // end for 
   return hashVal; 
 } // end hashFunc3() 

WorkSheet