Generics

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

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

Note that this does not mean that simply storing hashed password is safe, particularly if your users don’t choose good passwords.

For a great description of a sophisticated security breach using several different techniques, read this article
Note that I am in no way condoning the actions of Anonymous in this case
But reading about what HBGary did wrong can help you avoid similar mistakes, and understand a bit more about computer security and hashing

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."

Hashcash was intended to help fight spam. Now it’s the reason that Bitcoin mining is ruining the planet.

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();

> 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

> 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));
  }
}

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

The third and final midterm starts on Saturday.

The focus is data structures and algorithms, but completing the programming questions will require both imperative and object-oriented programming
There are four programming problems together worth 60 points. Most have partial credit.
Our final midterm represents your more sophisticated set of programming tasks yet.
(My goal is to irritate you before you complete the course evaluations…)

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

Midterm 2 consists of four 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
A final question that I’m not going to say more about

Friday: concurrency and a bit about hardware
Monday: streams and functional Java
Wednesday: wrap up and ICES forms

Your first final project checkpoint is in lab this week.
No office hours today. (I’m not feeling well.)
Remember to provide feedback on the course using the anonymous feedback form.
I’ve started to respond to existing feedback on the forum.

Cryptographic Hash Function

Cryptographic Hash Functions

A Simple Example

HBGary Hack

Another Example

Hashcash Example

Blockchain Proof of Work

Unintended Consequences

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

Announcements