Lecture notes for Week 6: Hashing

Textbook portions covered

Introduction to Algorithms (Cormen et al.)

Chapter 11

Engineering Algorithms...(Clowes “online book”)

Chapter 9

Announcements

Announcements

Hash functions

1. Division method: h(k) = k mod m
2. Multiplication method: h(k) = mfractioanl(kA)

Example (java Hashtable)

    public synchronized boolean contains(Object value) {
        if (value == null) {
            throw new NullPointerException();
        }

        Entry tab[] = table;
        for (int i = tab.length ; i-- > 0 ;) {
            for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
                if (e.value.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }

          

Example Java String hashCode()

     */
    public int hashCode() {
        int h = hash;
        if (h == 0) {
            int off = offset;
            char val[] = value;
            int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

          

Introduction to Algorithms (Cormen et al.)

• Exercise 11.1-1
• Exercise 11.1-2
• Exercise 11.1-3
• Exercise 11.2-2
• Exercise 11.2-3
• Exercise 11.4-1
• Exercise 11.4-2

Engineering Algorithms...(Clowes “online book”)

• 9.1