Copyright © 2014, 2015
Robert W. Hasker

CS 2852 Note 11

Making a hash of everything

• Suppose we want to look up states by two-letter code.
  • Solution 1: sorted array - max 6 comparisons
  • But can you do better?
    • 2-dimensional arrays
    • Note trade of speed for space
  • How to generalize this?
    • Given a string, compute a hash code for that string
    • Example: add up the integer values of the letters, take the remainder after dividing by some large number
    • Eg: 'sue' = 115 + 117 + 101 = 333, 333 % 100 = 33
      'mark' = 107 + 97 + 114 + 107 = 425, 425 % 100 = 25
      'zoe' = 122 + 111 + 101 = 334, 334 % 100 = 34
      'timmy' = 560, 560 % 100 = 60
    • Create an array of strings, store sue at 33, etc.
    • Comparisons to see if 'sue' is in the array: one
    • Problem: won't get different numbers every time: drew = 334, tudd = 433
    • Fixes: use a bigger array, use a fancier hashing scheme
  • better hashing - order matters:

            int sum = 0;
            char[] letters = string.reverse();
            for(int i = 0; i < letters.length; i++)
               sum += letters[i] + (i * 100);
    

  • ideal hashing: essentially a random number
    • constraint: if x equals y, need hash(x) == hash(y)
  • Java: every object has a hash code: Object.hashCode()
    • returns an integer with a large range
    • typical use: take the remainder after dividing by the size of the array: Math.abs(x.hashCode()) % table.length
      • Note book gives the wrong formula!
  • Resulting attempt:

            public class NaiveHashTable {
               private String[] table = new String[1000]; // all = null
               private int indexOf(String x) { return Math.abs(x.hashCode() % 1000); }
               public boolean contains(String x) {
                  int hash = indexOf(x);
                  return table[hash] != null && table[hash].equals(x);
               }
               public void add(String x) {
                  int hash = indexOf(x);
                  if ( table[hash] == null )
                     table[hash] = x;
                  else if ( table[hash].equals(x) )
                     ; // do nothing
                  else
                       ?
               }
            }
    

• How to handle collisions?
  • Two items have same hash code but are different
• Open addressing: find another place in the table for the item
  • linear probing: if index is filled, try index + 1, index + 2, etc.
  • stop when find a null
  • note must wrap around: probe after table.length - 1 is 0
  • Obviously if table completely full, will never find a space: allocate a new array and rebuild the table
  • issue: can get clusters of keys in the table - poor performance!
  • quadratic probing: increment by a number such as 13
    • making number relatively prime to table size decreases odds of clustering
    • challenge: not all table elements can be accessed from a given index, so may not be able to find a location for a key even though the table is not full
• Chaining
  • each table element references a linked list
  • this linked list is known as a bucket
  • tradeoff: easy collision handling, no secondary collisions, but poor performance if many keys hash to a particular location
  • opportunity: move referenced items to the head of the list
• How would we iterate over a hash table?
  • how would you implement hasNext?
  • could we iterate in alphabetical order?

Deleting Elements, Expansion

• Chaining: simple?
• Open Addressing:
  • [Why can't just change hashtable entry to null?]
  • Alternative: put a dummy entry in the table:

            final Object dummyNull = new Object();
    

  • [How could this create problems?] Consider table after many deletions.
  • Could we just replace dummy items by new ones?
    • Need to first ensure the item is not at the end of a list of dummies
  • Better solution: rehash
• Rehashing
  • Allocate new table, probably doubling its size
  • For each undeleted entry in the old table, insert into new
  • update references to new table
• Why can't we just copy data from the old to new table?

Hash table performance

• [what is the goal - what performance should we expect?]
• load factor: number of stored items divided by table size
  • ideal: load factor low enough that the only collisions are for items with the same hashCode
  • or is that ideal?
• Open addressing vs. chaining
  • expected number of comparisons, c, for finding an item using open addressing w/ linear probing and a load factor L:

    c = 0.5 * (1 + 1/(1-L))

    • See table 7.4 for various values of c and L
    • L = 0.5: c = 1.5
    • L = 0.75: c = 2.5
    • L = 0.9: c = 5.5 - not very good
  • for chaining (without reorganization); note L is the average size of a bucket:

    c = 1 + (L / 2)

    • L = 0.5: c = 1.25
    • L = 0.75: c = 1.38
    • L = 0.9: c = 1.45 - much better
  • open addressing with quadratic probing is between these two
• rehashing: drops load factor, improves efficiency
• Overall: O(1) is possible, but not guaranteed
  • In particular, must allocate time for rehashing, especially in a system with lots of deletions as well as additions
  • Question: is the guarantee worth the cost?
• This ignores storage requirements
  • If hashes waste 10 times the space, this is not a solution
  • There are always time vs. space tradeoffs - can always increase computation speed by storing more results
  • hash table of size 100 with open addressing at load factor 0.75: 25 null references
  • binary search tree for 75 item: need space for 75 left and right nodes, or 150 additional references - increased space
  • hash table with chaining: each item must have a next link, so can have 75 empty buckets before use more space than binary search tree

Implementation Issues

• Review hashCode
  • Why does this mean must redefine hashCode if redefine equals?
  • See Object.equals
• Creating hash table of strings using buckets:
  • Declaration: LinkedList<String>[] table; -- no problems
  • Naive initialization: table = new LinkedList<String>[100];
  • This doesn't compile because of type erasure: Java Generics are purely compile-time, so this code is disallowed because it would imply checks that cannot be made by the compiler
  • Causes warnings: table = LinkedList[100];
  • Fix: suppress the warnings - you cannot do better than this!

          @SuppressWarnings("unchecked")
          LinkedList<String>[] table = new LinkedList[100];
          for(int i = 0; i < table.length; ++i)
             table[i] = new LinkedList<>();
    

    • This adds the initialization of each bucket
    • @SuppressWarnings can only apply to whole declarations (locals, class members, classes) - couldn't apply to just the initialization
• Implement hash table with chaining: add(E), clear(), contains(Object), isEmpty(), remove(Object), size()
• How would HashMap differ?
• What is the asymptotic time complexity for the following HashSet methods:
  • add(E), clear(), contains(Object), isEmpty(), remove(Object), size()
• Questions:
  • [Does Map have .get(int)?]
  • [Do Set classes have indices?]
  • [When to use TreeSet and HashSet?]
  • [Which collections store data in sorted order?]

Review

• sets, maps
• java collections framework:
  • interfaces: collection, list, set, map, queue
  • implementations: ArrayList, LinkedList, Stack, TreeSet, HashSet, TreeMap, HashMap
• key design decision: which implementations to use!
• hash tables: promise of O(1) access
  • open addressing vs. chaining
  • insertion, lookup, deletion
  • widely used in high-performance, production systems!
• next: balanced trees