CS 245 Lecture 23 – Binary Search Trees
Agenda
- what ?s
- what does this do?
- what if we don’t override equals?
- what if we don’t override hashcode?
- hashes as a generalization of arrays
- hashes in C++
- hashes in PHP
- hash/object duality in JavaScript
- binary search over linked structures
- the binary search tree
What Does This Do?
public class Point3D {
private int x;
private int y;
private int z;
public Point3D(int x,
int y,
int z) {
this.x = x;
this.y = y;
this.z = z;
}
public static void main(String[] args) {
Hashtable<Point3D, String> pointsToNames = new Hashtable<Point3D, String>();
Point3D p = new Point3D(0, 1, 2);
pointsToNames.put(p, "Hydrogen");
Point3D p2 = new Point3D(0, 1, 2);
System.out.println(pointsToNames.get(p));
System.out.println(pointsToNames.get(p2));
}
}
Hash Links
Code
…
Haiku
Two roads, they diverged
I hope I took the right one
The one to Zaire
I hope I took the right one
The one to Zaire