Impact of Load Factor on Cost

Dashed lines are linear probing, solid lines are “random” probing.

Load factor is on the x-axis, expected number of buckets accessed on the y-axis.

(From OpenDSA book)

Socrative

Which of the following best describes the corresponding figure when chaining is used for collision resolution? (load factor on the x-axis, expected number of key comparisons on the y-axis).

1. The plot would have more or less the same shape, with somewhat fewer operations than linear probing.
2. The plot would approach infinity at .5 instead of 1.
3. The plot would be a straight line, with a positive slope.
4. The plot would be a horizontal line at 1.0.

Problems/Challenges with Hashing

• No ordered iteration.
• Iteration can be relatively inefficient when it involves iterating past empty buckets.
• Good hashing can lead to poor cache performance.
• Worst case performance is very bad, worst case performance is easy

What Gets used In The Wild?

C#/.net Dictionary

• Prime-number-sized tables
• Collision Resolution: Separate Chaining (in an array)
• Max load factor: 1.0

source

blog post

Python 2

• Closed hashing
• Power-of-two table sizes
• Hash function: grab lower order bits (no effort to avoid collisions)
• Collision resolution: fancy double hashing
  • Original hash $j$ is modified according to:

  perturb >>= PERTURB_SHIFT;
  j = (5*j) + 1 + perturb;

  • perturb is initialized to the original hash, then bit-shifted after every collision.
  • Default load factor .66

Implementation in: Python-2.7.2/Objects/dictobject.c. Source can be downloaded from www.python.org.

Python 3.6+

Update in Python 3:

the dictionary:

    d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

is currently stored as:

    entries = [['--', '--', '--'],
               [-8522787127447073495, 'barry', 'green'],
               ['--', '--', '--'],
               ['--', '--', '--'],
               ['--', '--', '--'],
               [-9092791511155847987, 'timmy', 'red'],
               ['--', '--', '--'],
               [-6480567542315338377, 'guido', 'blue']]

Instead, the data should be organized as follows:

    indices =  [None, 1, None, None, None, 0, None, 2]
    entries =  [[-9092791511155847987, 'timmy', 'red'],
                [-8522787127447073495, 'barry', 'green'],
                [-6480567542315338377, 'guido', 'blue']]

Only the data layout needs to change.  The hash table
algorithms would stay the same.

descripion: https://mail.python.org/pipermail/python-dev/2012-December/123028.html

source: https://github.com/python/cpython/blob/main/Objects/dictobject.c

Ruby

• Originally:
  • Prime-number-sized tables
  • Collision resolution: chaining
  • Max load factor: 5
• Currently:
  • Very similar to the Python3 approach

Original source: https://github.com/ruby/ruby/blob/ruby_2_3/st.c Current source: https://github.com/ruby/ruby/blob/ruby_3_0/st.c

Java 7 (We’ve seen…)

• Power-of-two table sizes
• Hash Function: bit scrambling, then use lower-order bits.
• Collision resolution: Chaining
• Default load factor: .75

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }


    /**
     * Returns index for hash code h.
     */

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

source (GPL V2.0)

Java 8+

• Power-of-two table sizes
• Hash Function: a little bit shifting, then use lower-order bits.
• Collision resolution: Chaining, CONVERT TO TREES IF THE CHAIN GETS LONGER THAN 8!
• Default load factor: .75

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Java 16 Source: https://github.com/openjdk/jdk/blob/jdk-16+36/src/java.base/share/classes/java/util/HashMap.java