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

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *