Array#

• An array maps an index (usually an integer) to an element, of any type.
• Arrays in Java have indexes starting at 0.
• Access by indexing

1
a[i] /* 0 <= i < size */

• An array is a function from natural numbers to elements all of the same type.

So can we use an array every time we want to connect numbers to values?

Actual example: exam scoring#

• Class of about 300 students
• Student numbers 5 digits
• Students usually marked once, or sometimes twice (borderline).
• Program to check that no student marked more than twice

1
static final int range = 100000; // 5-digit numbers
2
int [ ] timesMarked= new int [range];
3
for (int i= 0; i != range ; i++) timesMarked[i] = 0;
4
…
5
timesMarked[studentNum]= timesMarked[studentNum] + 1;

Very sparsely used array!
0.3% of array is used! Very space-inefficient.

We need to map a key to a value#

• Example:
  link (‘map’) key (student number) to value (student information).
• This is called a mapping.
• At most one value for any key.
• Also called a function, from key to value.

Example: email-address lookup#

“Sharon” → “sharoncurtis@brookes.ac.uk"
"David” → “dlightfoot@brookes.ac.uk"
"Ian” → “ibayley@brookes.ac.uk”
Pronounce ”→” as “maps to”

Associative array#

• ADT(abstract data type)
  • An associative array is an abstract data type
  • it is composed of a collection of unique keys and a collection of values, where each key is associated with one value (or set of values).

• The operation of finding the value associated with a key is called a lookup or indexing, and this is the most important operation supported by an associative array.
• The relationship between a key and its value is sometimes called a mapping or binding. For example, if the value associated with the key “bob” is 7, we say that our array maps “bob” to 7.
• Associative arrays are very closely related to the mathematical concept of a function with a finite domain.

Possible example: sequence of entries#

1
public class DelegateSeq implements IDelegateDB {
2
    private Delegate[] table;
3
    private final static int tableSize = 10; // or whatever
4
    private int numEntries;
5
    public DelegateSeq() {
6
        System.out.println("Simple sequence");
7
        table = new Delegate[tableSize];
8
        clearDB();
9
    }
10
    public void clearDB() {
11
        numEntries = 0;
12
    }
13
}

1
public Delegate put(Delegate delegate) {
2
    assert numEntries != tableSize; // very simple
3
    assert delegate != null;
4
    String name = delegate.getName();
5
    assert name != null && !name.equals("");
6
    Delegate previous;
7
    int pos = findPos(name);
8
    // we have to check not already in table. Time efficiency of findPos? (next slide)
9
    if (pos == numEntries) { // new
10
        numEntries++;
11
        previous = null;
12
    } else {
13
        previous = table[pos];
14
    }
15
    table[pos] = delegate;
16
    return previous;
17
}

1
private int findPos(String name) {
2
    assert name != null && !name.equals("");
3
    int i = 0;
4
    while (i != numEntries && !table[i].getName().equals(name))
5
        i++;
6
    return i;
7
}

Simple sequence gives O(n) behaviour#

• Can be improved by using an ordered sequence.
• Then we can use a binary search.

1
private int findPos(String name) {
2
    // returns position where name is, or would go
3
    assert name != null && !name.equals("");
4
    int left = 0, right = numEntries;
5
    while (left != right) {
6
        int mid = (left + right) / 2;
7
        if (name.compareTo(table[mid].getName()) > 0) left = mid + 1;
8
        else right = mid;
9
    }
10
    return left; // or right, since left == right
11
}

1
public Delegate put(Delegate delegate) {
2
    // assertions as before
3
    Delegate previous;
4
    int pos = findPos(name);
5
    if (pos == numEntries || !name.equals(table[pos].getName())) { // new
6
        int i = numEntries;
7
        while (i != pos) { // ‘budging up’ to keep the table ordered
8
            table[i] = table[i-1]; i--;
9
        }
10
        numEntries++;
11
        previous = null;
12
    } else {
13
        previous = table[pos];
14
    }
15
    table[pos] = delegate;
16
    return previous;
17
}

Ordered not much improvement#

• Self indexing can be O(1) – constant time. But works only in very special cases.
  • But leads to very sparse use of space in most cases.
  • But leads to very sparse use of space in most cases.
• Using a sequence works OK, but has O(n) time complexity.
• Ordered sequence is better: put is O(n), but get is O(log n) because of the binary search.
• But we want O(1) in all cases.

Answer: Hash tables#

Hans Peter Luhn IBM, 1954
Very clever idea!

We will see how they are made available in the Java Base-Class Library (API) and also how they work.

https://spectrum.ieee.org/tech-history/silicon-revolution/hans-peter-luhn-and-the-birth-of-the-hashing-algorithm

Hans Peter Luhn

Java API HashMap : Method Summary#

• void clear() Removes all mappings from this map.
• boolean containsKey(K key) Returns true if this map contains a mapping for the specified key.
• boolean containsValue(V value) Returns true if this map maps one or more keys to the specified value.
• V get(K key) Returns the value to which the specified key is mapped in this identity hash map, or null if the map contains no mapping for this key.
• boolean isEmpty() Returns true if this map contains no key-value mappings.
• Set<K> keySet() Returns a set view of the keys contained in this map.
• V put(K key, V value) Associates the specified value with the specified key in this map.
  (Returns the old discarded value – same with remove below)
• V remove(K key) Removes the mapping for this key from this map if present.
• int size() Returns the number of key-value mappings in this map.
• Collection<V> values() Returns a collection view of the values contained in this map.

Hash tables (associative arrays)#

• Content topics:
  • Hashing
  • Hash functions
  • Collision resolution
    • Probing (open addressing)
    • Chaining

Typical scenario#

• Fast storage and searching of large tables, lists, databases etc
• Need to minimize processing operations (comparisons and index calculations) per search
• Numerous application areas for fast table-lookup
• For example:
  databases, dictionaries, compiler symbol table, search engines, password lookup …
  

What’s the problem#

• How to store and then be able to locate items from a large data set very quickly
• The problem is whatever search methods we use, the following fact will not change:
  The more data we have, the slower the access

Search-Algorithm Performance#

• Linear search is O(N) – is the worst-possible case, linear time
• Binary search is O(log N) – is better, logarithmic time, but requires data to be sorted
• What we desire is O(1) or O(N⁰)
  • i.e. search time is constant, independent of data size N
  • so we can reach any data in a fixed number of operations, i.e. constant time

’Associative’ array#

• Suitable data structures for associative array:
  • Binary search tree [O(logn)]
  • Hash table [O(1)]

‘Hashing’#

• ‘Messing things up’, for example:
  • Corned-beef hash // 玉米牛肉糜
  • Hash brown potatoes // 薯饼
• Hence the meat-mincing machine in next slide…
• Hashing for CS:
  A method of transforming a search key into an address, for the purpose of fast and efficient storage and retrieval of data items.

Example: finding someone quickly#

How does hashing work#

• Instead of storing each new data item in the next free memory location, we need to find a way to find its storage location based on a key value from the data content.
• That way we will be able to locate each data item, using its key value.

• Hashing:
• The process of build a relationship between constant numbers (such as 1, 2, 3…) and particular content.

• So the location to store/find a data item is obtained using a hash function applied to the data item (key) value
• The hash function maps a key to an arbitrary (but not ‘random’) integer ‘bucket number’

What is a hash function#

• Hash function(method):
  • The way/method to convey the particular contents into constant numbers.

Simple Hashing#

1
int hashFirstChar(String s) { // just value of first character
2
    return s.charAt(0) % tableSize;
3
    // mod tableSize gives a value in range 0 .. tableSize-1
4
}

1
final int tableSize = 12; // for example
2
private static int hashSum(String key) {
3
    int hashValue = 0;
4
    for(int j = 0; j != key.length(); j++)
5
        hashValue = hashValue + (int)key.charAt(j);
6
    return hashValue; // or hashValue % tableSize here or later
7
}

1
private static int hashWeighted(String key) {
2
    int hashValue = 0;
3
    for(int j = 0; j != key.length(); j++)
4
        hashValue = j * hashValue + (int)key.charAt(j);
5
        // "j *" here is weighting
6
    return hashValue;
7
}

1
private static int hashWeighted(String key) {
2
    int hashValue = 0;
3
    for(int j = 0; j != key.length(); j++)
4
        hashValue = (j * hashValue + (int)key.charAt(j)) % tableSize;
5
    return hashValue;
6
}

Some examples of hashing functions#

• Division:
  h(k) is the remainder (modulus) of key k after division by the size of the table, s.
  h(k) = k % s; if k = 7155, s = 97 then h(k) = 74
• Truncation:
  Take a few of the first or last characters of the key as the hash code. Can work well, provided the characters are evenly distributed.

• Mid-square:
  the key is squared and the middle digits of the result are used as the hashed value.
  k = 7155; k² = 51194025; h(k) = 94 (from 511 94 025)
• Folding:
  the key is partitioned into several parts and the sum of the parts is used to produce the hash code
  k = 7155; 71 + 55 → 126 or 17 + 55 → 72
• ……

Practice: calculate your name hash value#

• Store some names of a group students, so table size should be 26, the key value for each one is simply the name string, e.g. “Tony”
• The hash function is Division:
  • k is the sum of the ASCII codes of the letters in the name string;
  • h(k) is the remainder (modulus) of key k after division by the size of the table, s.
    h(k) = k % s; s = 26

Practice#

• Design your own hash method
  • to calculate the hash value for your name string
  • should be different from the example method mentioned above
  • try to use easy way

The most handsome boy/most beautiful girl demonstrate

Simple Hashing – with Hash Clash#

Search(Retrieval)#

• Use the same hashing function and collision-resolution method as for inserting.
• At best can get O(1) – constant time.

Can’t do better than that!

Perfect hash function#

A perfect hash function gives no collisions:
For all x and y:

• Possible if you know the data.
• Collision is when two or more keys have the same hash value.
• Rarely possible, but for example in a compiler,
• determine whether identifier is a reserved word.
• We know all the reserved words, so can construct a perfect hash function.

Desirable characteristics of a hashing function#

• Quick to calculate
• Gives good spread – different keys map to different bucket/slot numbers (positions in the table)
• A perfect hashing function maps every key to a different bucket/slot number
• but in practice, sometimes get a ‘clash’ 💣 – more than one key is mapped to the same bucket number.

More about hash functions#

• The hash function can potentially generate any hash table index, 0..TableSize-1 so we often use the modulo (%) operator to restrict the hash function range
• A hash function directs us to a single storage location for a particular data key value
• If we could guarantee that each possible key value maps on to a unique entry (1:1 mapping) then our hashing would be perfect.
• Because the hash table in practice is limited in size, and the difficulty of ensuring one-to-one mapping, we need to allow for collisions.

Try to reduce collisions!
Impossible to eliminate!

One Java built-in hashCode() method#

$\text{hashCode}(s) = s[0] \times 31^{(n-1)} + s[1] \times 31^{(n-2)} + \dots + s[n-1] \times 31^0$
$e.g.$
$\text{hashcode}(^{\prime\prime}\text{A}^{\prime\prime}) = 65$
$\text{hashcode}(^{\prime\prime}\text{AB}^{\prime\prime}) = 65 \times 31^1 + 66 = 2081$
$\text{hashcode}(^{\prime\prime}\text{ABC}^{\prime\prime}) = 65 \times 31^2 + 66 \times 31^1 + 67 = 64578$
Beware numeric overflow! Use % early.

1
public class Hash10 {
2
    public static void main(String[] args) {
3
        System.out.println("hashCode(\"A\")="+"A".hashCode());
4
        System.out.println("hashCode(\"AB\")="+"AB".hashCode());
5
        System.out.println("hashCode(\"ABC\")="+"ABC".hashCode());
6
        System.out.println("hashCode(\"ABCD\")="+"ABCD".hashCode());
7
    }
8
}

result:

1
hashCode("A")=65
2
hashCode("AB")=2081
3
hashCode("ABC")=64578
4
hashCode("ABCD")=2001986

Probability of hash clashes#

• What is the probability that 2 (or more) people in a group of n share a birthday month?
  Assume that birthdays are equally and randomly distributed over 12 months. Q(n) = probability that n people have distinct birthday months
  Q(2) = 11/12 = 0.9166
  Q(3) = 11/12 x 10/12 = 0.7639
  Q(4) = 11/12 x 10/12 x 9/12 = 0.5729
  etc

P(n) = 1-Q(n) = probability that 2 or more people of the n share a birthday month, so
P(2) = 0.0834
P(3) = 0.236
P(4) = 0.427
P(5) = 0.618
P(6) = 0.777
etc.

5 people > 50%

Probabilities of clashes in Hash Table#

• A surprising example:
  • Create a hash table with Table_Size=1,000,000 entries (index 0..Table_Size-1)
  • Hash function creates an arbitrary index number (based on the key value) that is uniformly distributed in the range 0..Table_Size-1
  • Keep adding hash entries to the table
  • The probability that a collision will occur before 2,500 entries are made is 95%, i.e. when the table is only 0.25% full
• Conclusion: clashes can occur more frequently than we might intuitively expect.

Collision Resolution – Linear probing#

• Hash collisions can be resolved by probing to find an alternative location.
  • If a collision occurs [hash(key1)=hash(key2)] look for next table entry that is free
  • First calculate:
    • Index1 = hash(Key) (which cell is not available)
    • hash(key) maps to range 0 ..Table_Size-1
  • Next calculate
    • Index2 =(Index1 + probe) % Table_Size
  • repeating with probe = 1,2,3,.. until a vacant entry is found (probe function)

primary clustering has occurred for keys that hash to index 93 and 94

• Hash collisions can be resolved by probing to find an alternative location.
  • Advantages:
    • resolves hash clash
    • simple algorithm
  • Disadvantages:
    • local clustering around the primary key (termed primary clustering, such as key1~key6)
    • deletion is tricky (it leaves holes)

Collision resolution: Open addressing#

• Open addressing
• The average number of probes for a search depends critically on the hash-table load factor, L
  L = number_of_items_in_table / Table_Size often expressed as a percentage
  Therefore the maximum capacity is simply the hash table size, and maximum load factor is 1.0.

Linear probing - Number of probes#

• The average number of probes for a search depends critically on the hash-table load factor
• Average number of probes calculation is complex to derive

To solve clustering#

• Primary clustering
  • When keys hash to the same location and are then stored close by – this leads to primary clustering
  • Avoid by allowing the probe function to provide a greater spread of keys
• Secondary clustering
  • When keys hash to the same index and then follow the same probe sequence (same offset), this leads to secondary clustering
  • Avoid with probe offset being non-linear (quadratic) or a function of the key (double hashing)

Open-Addressing Hashing Efficiency#

• Average steps of probes

collision resolution: chaining#

• Separate chaining
  • start a linked list to store the data for each key for that maps to the hash-table location
  • each hash table entry can then accommodate a list of key values that share the same hash value
• Since each hash table entry can be a list there is no limit to the hash-table capacity, so the load factor may exceed 1.0.

• Linked lists within the hash table handle collisions
• Alternative to ‘open addressing’, Linked list of all elements whose keys have same hash index.

1
import java.util.LinkedList;
2
import java.util.ListIterator;
3
public class Hash11 {
4
    public static void main(String[] args) {
5
        final int HTS = 12; // hash table size
6
        LinkedList[] staff=new LinkedList[HTS];
7
        for(int i=0; i<HTS; i++)
8
            staff[i]=new LinkedList();
9
        addStaff(staff,"Sharon");
10
        addStaff(staff,"Chris");
11
        addStaff(staff,"Ian");
12
        addStaff(staff,"David");
13
        addStaff(staff,"Peter");
14
        addStaff(staff,"Muhammad");
15
        addStaff(staff,"Arantza");
16
        addStaff(staff,"Ken");
17
        addStaff(staff,"Richard");
18
        addStaff(staff,"Hong");
19
        addStaff(staff,"William");
20
        addStaff(staff,"Mark");
21
        addStaff(staff,"Bob");
22
        addStaff(staff,"Clare");
23
        addStaff(staff,"Faye");
24
        ListIterator iterator=staff[0].listIterator();
25
        for(int i=0; i<HTS; i++) {
26
            iterator=staff[i].listIterator();
27
            System.out.print("staff["+i+"]: ");
28
            while (iterator.hasNext())
29
                System.out.print(iterator.next()+" ");
30
            System.out.println();
31
        }
32
    }
33
    private static void addStaff(LinkedList[] staff, String key) {
34
        final int HTS = 12; // hash table size
35
        staff[hash(key)].addLast(key);
36
    }
37
    private static int hash(String key) {
38
        final int HTS = 12; // hash table size
39
        return Math.abs(key.hashCode() % HTS);
40
    }
41
}

1
staff[0]: Hong
2
staff[1]: Richard
3
staff[2]:
4
staff[3]: Sharon
5
staff[4]: Muhammad Ken
6
staff[5]: Arantza William Mark Bob
7
staff[6]:
8
staff[7]: Chris Clare
9
staff[8]: David Peter
10
staff[9]:
11
staff[10]: Ian
12
staff[11]: Faye
13
BUILD SUCCESSFUL (total time: 0 seconds)

Linear Probing vs Chaining#

Hashing Performance#

• Best Case (ideal) O(1)
• Worst case (all keys hash to same slot) O(n)
• Performance very dependent on hash table Load Factor
  Load Factor = number of items in table / table size
• Likelihood of collision strongly related to load factor
• Load Factor (L) = 0 represents empty table
  • Open Addressing: 0 ≤ L ≤ 1, (hash table can only fill to capacity)
  • Chaining: 0 ≤ L, (so L can exceed 1)
• Typically performance becomes poor when table > 80% full
• Rebuild with a bigger table to improve performance if table becomes full

Disadvantages of hash tables#

• The size of the table is fixed and must be estimated in advance. It cannot be changed at runtime.
• Table size should be about 10% larger than the maximum expected number of entries.
• Hashing algorithms are designed for efficient insertion and retrieval. Deletions are cumbersome and should be avoided. (Don’t just replace entry by null – “example: Where’s Wally”)
  Use ‘lazy deletion’; don’t really remove – just mark entry as inactive.
• Contents not stored in order, so sorting needed.
• The space needed for pointers for chaining could be used for a larger table.

Summary#

• Access time is not dependent on the size of the table, at best O(1)
• Good for storing data not directly representable as array indexes,
  or for storing sets of data from very large data sets.
• Key values mapped to index by hashing function.
• Different keys mapping to same index means collision.
• Collision resolution:
  • ‘open addressing’ using various ‘probing’ algorithms;
  • chaining (most efficient, but uses more memory).
• Hashing efficiency depends critically on hash-table load factor and degree of clustering

References#

• Robert Sedgewick, Algorithms in Java, Addison-Wesley, Ch 14.
• Mark Allen Weiss, Data Structures and Algorithm Analysis, Addison-Wesley, Ch 5
• Cormen, Leiserson and Rivest, Introduction to Algorithms, Ch 12
• Niklaus Wirth, Algorithms+Data Structures=Programs, Prentice-Hall
• Wikipedia: https://en.wikipedia.org/wiki/Hash_table

Extra: history#

• The idea of hashing arose independently in different places.
• In January 1953, H. P. Luhn wrote an internal IBM memorandum that used hashing with chaining.
• Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, and Arthur Samuel implemented a program using hashing at about the same time. Open addressing with linear probing (relatively prime stepping) is credited to Amdahl, but Ershov (in Russia) had the same idea.