Generics

xxxxxxxxxx
 
import java.util.List;
import java.util.ArrayList;
​
public class LastTen<T> {
  private List<T> values = new ArrayList<>(10);
  private int currentIndex = 0;
  LastTen() {
    for (int i = 0; i < 10; i++) {
      values.add(i, null);
    }
  }
  public void add(T newValue) {
    values.set(currentIndex, newValue);
    currentIndex = (currentIndex + 1) % 10;
  }
  public List<T> get() {
    return values;
  }
}
public class Example {
  public static void main(String[] unused) {
    LastTen<String> lastTen = new LastTen<>();
    for (int i = 0; i < 30; i++) {
      lastTen.add("foo" + i);
    }
    System.out.println(lastTen.get());
  }
}

Generics
> Click or hit Control-Enter to run Example.main above

						 						int[] numbers = new int[] {5, 6, 7}; 					
						 						System.out.println(numbers[0]); 					
						 						numbers[1] = 8;

Arrays map an index (0, 1, 2, array.length to a value).
The value can be anything, but the indices had to be be integers.
No longer!

A Java Map allows us to use any object like an array index.

						 						import java.util.Map; 					
						 						import java.util.HashMap; 					
						 						 					
						 						Map<String, Integer> stringValues = new HashMap<>(); 					
						 						stringLengths.put("test", 5); 					
						 						System.out.println(stringLengths.get("test")); // Prints 5 					
						 						stringLengths.put("test", 7); 					
						 						System.out.println(stringLengths.get("test")); // Prints 7

So how do we implement a Map?

Use a hashCode to retrieve a hash code for each object.
Use that value—or a smaller part of it—as an index into an array.
But what about collisions?

$hash table$

public class HashMap {
  private static final int TABLE_SIZE = 16;
  class Item {
    public Object key;
    public Object value;
    public Item next;
    Item(Object setKey, Object setValue, Item setNext) {
      key = setKey;
      value = setValue;
      next = setNext;
    }
  }
  private Item[] items = new Item[TABLE_SIZE];
  public int itemCount = 0;
  private int hash(Object key) {
    int hashValue = key.hashCode() % TABLE_SIZE;
    if (hashValue < 0) {
      hashValue += TABLE_SIZE;
    }
    return hashValue;
  }
  public void put(Object key, Object value) {
    int bucket = hash(key);
    Item current = items[bucket];
    for (; current != null; current = current.next) {
      if (current.key.equals(key)) {
        current.value = value;
        return;
      }
    }
    Item newItem = new Item(key, value, items[bucket]);
    items[bucket] = newItem;
    itemCount++;
    return;
  }
}
public class Example {
  public static void main(String[] unused) {
    HashMap ourHashMap = new HashMap();
    ourHashMap.put("test", "me");
    System.out.println(ourHashMap.itemCount);
    ourHashMap.put("test", "another");
    System.out.println(ourHashMap.itemCount);
  }
}

xxxxxxxxxx
 
public class HashMap {
  private static final int TABLE_SIZE = 16;
  class Item {
    public Object key;
    public Object value;
    public Item next;
    Item(Object setKey, Object setValue, Item setNext) {
      key = setKey;
      value = setValue;
      next = setNext;
    }
  }
  private Item[] items = new Item[TABLE_SIZE];
  public int itemCount = 0;
  private int hash(Object key) {
    int hashValue = key.hashCode() % TABLE_SIZE;
    if (hashValue < 0) {
      hashValue += TABLE_SIZE;
    }
    return hashValue;
  }
  public void put(Object key, Object value) {
    int bucket = hash(key);
    Item current = items[bucket];
    for (; current != null; current = current.next) {
      if (current.key.equals(key)) {
        current.value = value;
        return;
      }
    }
    Item newItem = new Item(key, value, items[bucket]);
    items[bucket] = newItem;
    itemCount++;
    return;
  }
}
public class Example {
  public static void main(String[] unused) {
    HashMap ourHashMap = new HashMap();
    ourHashMap.put("test", "me");
    System.out.println(ourHashMap.itemCount);
    ourHashMap.put("test", "another");
    System.out.println(ourHashMap.itemCount);
  }
}

> Click or hit Control-Enter to run Example.main above

Let’s consider the performance of our simple HashMap in two cases. First, if the array is very small relative to the number of items:

put: O(n) with n being the number of items
get: O(n) with n being the number of items
At this point the HashMap is acting like a linked list.

Let’s consider the performance of our simple HashMap in two cases. Second, if the array is very large relative to the number of items:

put: O(1)
get: O(1)
At this point the HashMap is acting like an array.
What’s the problem? It requires a lot of space.

In reality we want our HashMap to blend the good features of an array and a linked list.

Usually implementations will enlarge the array part of a HashMap once it gets filled past a certain point (called the load factor).

This is cool stuff!

Hash functions already provide:

Determinism: it can convert an arbitrary amount of data into a single limited-size value. If we repeat the computation on the same data, we get the same value.
Uniformity: over many inputs, each output value is equally likely.
Efficiency: it is efficient to compute.

But what if there were hash functions with the following new properties:

Given the hash, it is infeasible to determine the original input
A small change to the input produces a large change in the output
The function is difficult to compute, not easy

A hash function that satisfies these properties is known as a cryptographic hash function, largely because they are ubiquitous in modern cryptography.

I need to be able to check your password, but I don’t want to save it. Is that possible?

Yes!
Save the cryptographic hash of your password, not the password itself.
When you submit your password, I hash it and compare it with the saved hash.
If someone steals my database, they can’t recover the original passwords.
- Given the hashes, you can’t recover the original passwords
- Hash values reveal nothing about how close you are to the actual password
- Hashing inputs to test them is expensive

Heard of blockchain?

Blocks are linked through cryptographic hashes. And the blockchain is secured through an old idea called Hashcash.

Given a hash value of a given size, I can estimate how much work you’ll have to do to guess the input that produced that value
So I can force you to do that work and verify that you did it easily by hashing the value that you gave me

Alice: "Here’s a challenge for you Bob, find an input that produces hash 39c3aa4015e7964914c311915316a2f78157c946.
Bob: "Geez, that’s hard. Give me a few minutes… OK, got it."
Alice: "Wow, you’re right. I computed the hash and it’s 39c3aa4015e7964914c311915316a2f78157c946 that must have been hard."

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the function’s output for a random input.

The existence of such one-way functions is still an open conjecture. In fact, their existence would prove that the complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science.

Lists and maps are the two data structures you meet in heaven. Together you can use them to solve almost any problem.

But you’ll usually use Java`s built-in implementations.

						 						import java.util.List; 					
						 						import java.util.ArrayList; 					
						 						import java.util.LinkedList; 					
						 						 					
						 						import java.util.Map; 					
						 						import java.util.HashMap; 					
						 						import java.util.TreeMap; 					
						 						 					
						 						List list = new ArrayList(); 					
						 						List anotherList = new LinkedList(); 					
						 						Map map = new HashMap(); 					
						 						Map anotherMap = new TreeMap();

xxxxxxxxxx
 
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
​
public class Example {
  public static void main(String[] unused) {
    List list = new ArrayList();
    // What goes in is a string...
    list.add("string");
    // But what comes out is an Object
    String s = list.get(0);
    // We can downcast this, but that's not safe
​
    Map map = new HashMap();
    // Keys and values can be any Java object...
    map.put("key", 8);
    // But what comes out is an Object
    Integer i = map.get("key");
    // We can downcast this, but that's (still) not safe
  }
}

> Click or hit Control-Enter to run Example.main above

Java and many languages that followed it have tried to transform runtime errors into compiler errors. Why?

You compile your code before it runs: and so before you have to demo it to a client, or before you deploy it to hundreds of users.
Catching errors at this stage is critical.

Java generics allow us to create reusable classes while allowing the compiler to check our code for correctness.

Type parameters tell the compiler what we are going to do with each data structure.

						 						import java.util.List; 					
						 						import java.util.ArrayList; 					
						 						import java.util.Map; 					
						 						import java.util.HashMap; 					
						 						 					
						 						List<Integer> integerlist = new ArrayList<>(); // This is list of Integers 					
						 						Map<Integer, String> = new HashMap<>(); // This maps Integers to Strings

Java generics allow to combine two desirable features of the language:

Polymorphism: because every object inherits from Object it is easy to build general purpose data structures that can operate on every Java object
Type Checking: however, upcasting everything to Object makes it impossible for the compiler to perform compile-time type checking
Generics are intended to allow us to have the best of both worlds

xxxxxxxxxx
 
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
​
public class Example {
  public static void main(String[] unused) {
    List<String> list = new ArrayList<>();
    // What goes in is a string...
    list.add("string");
    // What comes out is a string
    String s = list.get(0);
    // I can't add Objects that aren't Strings or don't descend from String
    list.add(new Integer(10));
​
    Map<String, Integer> map = new HashMap<>();
    // The compiler can check my mappings...
    map.put("key", 8);
    // And cast what comes out safely for me
    Integer i = map.get("key");
    // I can't add invalid mappings
    map.put(8, 10);
  }
}

> Click or hit Control-Enter to run Example.main above

So we know how to use existing generic class. But how do we provide our own?

First, we have to declare our class to accept type parameters:

						 						// T is a type parameter that can be used throughout our class 					
						 						public class SimpleLinkedList<E> { 					
						 						  // get returns a reference of type E 					
						 						  public E get(int index) { 					
						 						  } 					
						 						  // set takes a reference of type T as its second argument 					
						 						  public void set(int index, E value) { 					
						 						  } 					
						 						}

Class parameters are not variables.

I can use them where I would normally provide a type, but I can’t get or set their values.

						 						public class SimpleLinkedList<E> { 					
						 						  // I can use the parameter here as a return type... 					
						 						  public E get(int index) { 					
						 						    E = String; // But I can't do something like this 					
						 						  } 					
						 						}

To help understand how generics work you can imagine the compiler rewriting them when it compiles your code.

						 						public class List<E> { 					
						 						  public E get(int i) { 					
						 						  } 					
						 						  public void set(int i, E value) { 					
						 						  } 					
						 						} 					
						 						List<String> list = new List<>();

						 						public class List { 					
						 						  public String get(int i) { 					
						 						  } 					
						 						  public void set(int i, String value) { 					
						 						  } 					
						 						} 					
						 						List list = new List<>();

						 						public class List<E> { 					
						 						  public E get(int i) { 					
						 						  } 					
						 						  public void set(int i, E value) { 					
						 						  } 					
						 						} 					
						 						List<Integer> list = new List<>();

						 						public class List { 					
						 						  public Integer get(int i) { 					
						 						  } 					
						 						  public void set(int i, Integer value) { 					
						 						  } 					
						 						} 					
						 						List list = new List<>();

Note that this is not actually what happens.

The compiler only creates one instance of each generic class
Type information is used during compilation to check access but then erased
But this isn’t a bad mental model of how generics work in practice

Classes can use one or several type parameters:

						 						// This is a generic list storing elements of type T 					
						 						public class SimpleLinkedList<T> { } 					
						 						 					
						 						// This is a generic map mapping elements of type K to type V 					
						 						public class SimpleMap<K,V> { }

To avoid confusing type parameters with variable names or other keywords, Java has established conventions for naming them.

By convention type names are single uppercase letters: T, K, V, E, etc.
Note that this is just a convention: it’s not enforced by the compiler
Certain type parameters have conventional meanings:
- E for element (which we’ll use for our lists)
- K for key and V for value, (which we’ll use for our maps)
- N for a number

						 						public class Map<K, V> { 					
						 						  public V get(K key) { 					
						 						  } 					
						 						  public void put(K key, V val) { 					
						 						  } 					
						 						} 					
						 						Map<String, Double> map = new Map<>();

						 						public class Map { 					
						 						  public Double get(String key) { 					
						 						  } 					
						 						  public void put(String key, Double val) { 					
						 						  } 					
						 						} 					
						 						Map map = new Map();

						 						public class Map<K, V> { 					
						 						  public V get(K key) { 					
						 						  } 					
						 						  public void put(K key, V val) { 					
						 						  } 					
						 						} 					
						 						Map<Integer, String> map = new Map<>();

						 						public class Map { 					
						 						  public String get(Integer key) { 					
						 						  } 					
						 						  public void put(Integer key, String val) { 					
						 						  } 					
						 						} 					
						 						Map map = new Map();

public class SimpleLinkedList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private int currentSize;

public SimpleLinkedList() { }

public SimpleLinkedList(Object[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      this.add(0, array[i]);
    }
  }

public void add(int index, Object toAdd) {
    if (index == 0) {
      start = new Item(toAdd, start);
      currentSize++;
      return;
    }
    Item previousItem = getItem(index - 1);
    if (previousItem == null) {
      return;
    }
    Item newItem = new Item(toAdd, previousItem.next);
    previousItem.next = newItem;
    currentSize++;
  }

public Object remove(int index) {
    Object toReturn;
    if (index == 0) {
      toReturn = start;
      start = start.next;
      return toReturn;
    }
    Item previousItem = getItem(index - 1);
    toReturn = previousItem.next;
    previousItem.next = previousItem.next.next;
    return toReturn;
  }

public Object get(int index) {
    Item item = getItem(index);
    if (item == null) {
      return null;
    } else {
      return item.value;
    }
  }

public void set(int index, Object toSet) {
    Item item = getItem(index);
    if (item != null) {
      item.value = toSet;
    }
  }

public int size() {
    return currentSize;
  }

protected Item getItem(int index) {
    if (index < 0 || index >= currentSize) {
      return null;
    }
    int currentIndex = 0;
    for (Item current = start; current != null; current = current.next) {
      if (currentIndex == index) {
        return current;
      }
      currentIndex++;
    }
    return null;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleLinkedList simpleList = new SimpleLinkedList();
    for (int i = 0; i < 10; i++) {
      simpleList.add(0, i);
    }
    System.out.println(simpleList.size());
    for (int i = 0; i < 5; i++) {
      simpleList.remove(i);
    }
    System.out.println(simpleList.get(0));
  }
}

xxxxxxxxxx
 
public class SimpleLinkedList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private int currentSize;
​
  public SimpleLinkedList() { }
​
  public SimpleLinkedList(Object[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      this.add(0, array[i]);
    }
  }
​
  public void add(int index, Object toAdd) {
    if (index == 0) {
      start = new Item(toAdd, start);
      currentSize++;
      return;
    }
    Item previousItem = getItem(index - 1);
    if (previousItem == null) {
      return;
    }
    Item newItem = new Item(toAdd, previousItem.next);
    previousItem.next = newItem;
    currentSize++;
  }
​
  public Object remove(int index) {
    Object toReturn;
    if (index == 0) {
      toReturn = start;
      start = start.next;
      return toReturn;
    }
    Item previousItem = getItem(index - 1);
    toReturn = previousItem.next;
    previousItem.next = previousItem.next.next;
    return toReturn;
  }
​
  public Object get(int index) {
    Item item = getItem(index);
    if (item == null) {
      return null;
    } else {
      return item.value;
    }
  }
​
  public void set(int index, Object toSet) {
    Item item = getItem(index);
    if (item != null) {
      item.value = toSet;
    }
  }
​
  public int size() {
    return currentSize;
  }
​
  protected Item getItem(int index) {
    if (index < 0 || index >= currentSize) {
      return null;
    }
    int currentIndex = 0;
    for (Item current = start; current != null; current = current.next) {
      if (currentIndex == index) {
        return current;
      }
      currentIndex++;
    }
    return null;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleLinkedList simpleList = new SimpleLinkedList();
    for (int i = 0; i < 10; i++) {
      simpleList.add(0, i);
    }
    System.out.println(simpleList.size());
    for (int i = 0; i < 5; i++) {
      simpleList.remove(i);
    }
    System.out.println(simpleList.get(0));
  }
}

> Click or hit Control-Enter to run Example.main above

The third and final midterm will be held next Monday.

The focus is data structures and algorithms, but completing the programming questions will require both imperative and object-oriented programming
There are three programming problems together worth 50 points. Most have partial credit.
Our final midterm represents your more sophisticated set of programming tasks yet.

As always, the best way to review for the midterm is to review the practice homework problems.

Midterm 2 includes three programming tasks:

One question on lists that is very similar to a homework problem
One question on trees that is very similar to a homework problem
One question on sorting that is directly drawn from the homework

Friday: more about generics.
Monday: midterm exam (no class).
Wednesday: wrap up.

Review: Remember Arrays?

Review: Java Maps

Brief `Map` Implementation

`Map` As Array + Linked List

`HashMap` Performance

`HashMap` Performance

Realistic `HashMap` Performance

Looking forward to CS 225 yet?

Cryptographic Hash Function

Cryptographic Hash Functions

A Simple Example

Another Example

Hashcash Example

Blockchain Proof of Work

And, Beautiful Theory

Questions About Hashing?

Java Generics

Compiler Errors v. Runtime Errors

Generics

Generic Rationale

Generifying Your Classes

Class Type Parameters

Parameters Are Not Variables

Compiling Generic Classes

Original and Rewritten List

Original and Rewritten List

Type Erasure

Multiple Type Parameters

Parameter Naming Conventions

Original and Rewritten Map

Original and Rewritten Map

Questions About Generics?

Midterm 2

Midterm 2 Problems

Next Few Classes

	int[] numbers = new int[] {5, 6, 7};
	System.out.println(numbers[0]);
	numbers[1] = 8;

	import java.util.Map;
	import java.util.HashMap;

	Map<String, Integer> stringValues = new HashMap<>();
	stringLengths.put("test", 5);
	System.out.println(stringLengths.get("test")); // Prints 5
	stringLengths.put("test", 7);
	System.out.println(stringLengths.get("test")); // Prints 7

	import java.util.List;
	import java.util.ArrayList;
	import java.util.LinkedList;

	import java.util.Map;
	import java.util.HashMap;
	import java.util.TreeMap;

	List list = new ArrayList();
	List anotherList = new LinkedList();
	Map map = new HashMap();
	Map anotherMap = new TreeMap();

	// T is a type parameter that can be used throughout our class
	public class SimpleLinkedList<E> {
	// get returns a reference of type E
	public E get(int index) {
	}
	// set takes a reference of type T as its second argument
	public void set(int index, E value) {
	}
	}

	public class SimpleLinkedList<E> {
	// I can use the parameter here as a return type...
	public E get(int index) {
	E = String; // But I can't do something like this
	}
	}

	public class List<E> {
	public E get(int i) {
	}
	public void set(int i, E value) {
	}
	}
	List<String> list = new List<>();

	public class List {
	public String get(int i) {
	}
	public void set(int i, String value) {
	}
	}
	List list = new List<>();

	public class List {
	public Integer get(int i) {
	}
	public void set(int i, Integer value) {
	}
	}
	List list = new List<>();

	// This is a generic list storing elements of type T
	public class SimpleLinkedList<T> { }

	// This is a generic map mapping elements of type K to type V
	public class SimpleMap<K,V> { }

	public class Map<K, V> {
	public V get(K key) {
	}
	public void put(K key, V val) {
	}
	}
	Map<String, Double> map = new Map<>();

	public class Map {
	public Double get(String key) {
	}
	public void put(String key, Double val) {
	}
	}
	Map map = new Map();

	public class Map {
	public String get(Integer key) {
	}
	public void put(Integer key, String val) {
	}
	}
	Map map = new Map();

Review: Remember Arrays?

Review: Java Maps

Brief Map Implementation

Map As Array + Linked List

HashMap Performance

HashMap Performance

Realistic HashMap Performance

Looking forward to CS 225 yet?

Cryptographic Hash Function

Cryptographic Hash Functions

A Simple Example

Another Example

Hashcash Example

Blockchain Proof of Work

And, Beautiful Theory

Questions About Hashing?

Java Generics

Compiler Errors v. Runtime Errors

Generics

Generic Rationale

Generifying Your Classes

Class Type Parameters

Parameters Are Not Variables

Compiling Generic Classes

Original and Rewritten List

Original and Rewritten List

Type Erasure

Multiple Type Parameters

Parameter Naming Conventions

Original and Rewritten Map

Original and Rewritten Map

Questions About Generics?

Midterm 2

Midterm 2 Problems

Next Few Classes

Brief `Map` Implementation

`Map` As Array + Linked List

`HashMap` Performance

`HashMap` Performance

Realistic `HashMap` Performance