CSE 3302Lecture 23: Equality and identity13 April 2010Nate NystromUTATuesday, April 27, 2010Today• A smörgåsbord:• Equality and identity• Real numbers• Dynamic typingTuesday, April 27, 2010Equality and identity• What does it mean for two variables to be equal?• equality vs. identity•identical = names refer to the same object•equal = names refer to objects with the same valueTuesday, April 27, 2010Java• == on primitives: equality• == on objects: identity• .equals on objects: equalityTuesday, April 27, 2010Java primitives• == implements equality• numbers:• 1.0 == 1 == 1L• (byte) 256 == 0 // same bit pattern• floats:• +0. == -0.• Float.NaN != Float.NaNTuesday, April 27, 2010Java objects• Use == for identity, .equals for equality• new Integer(1) != new Integer(1)• (new Integer(1)).equals(new Integer(1))Tuesday, April 27, 2010Java strings• Use == for identity, .equals for equality• “hello”.equals(“hello”) ?• “hello” == “hello” ?• “hello” == new String(“hello”) ?Tuesday, April 27, 2010Java strings• Use == for identity, .equals for equality• “hello”.equals(“hello”) true• “hello” == “hello” true• “hello” == new String(“hello”) falseTuesday, April 27, 2010Java objects•Classes can override .equals• Default implementation does ==•Thus new Object() != new Object()Tuesday, April 27, 2010Java .equals• Things to be careful of when overriding .equals:• reflexivity, transitivity, symmetry• mutable state• null• consistency• hashCode• toStringTuesday, April 27, 2010Reflexivity• == should imply .equals• ! .equals should imply !=• Broken:class C { public boolean equals(Object o) { return false; }}Tuesday, April 27, 2010Symmetry• Broken?class C { int x; public boolean equals(Object o) { return o instanceof C && x == ((C) o).x; }}Tuesday, April 27, 2010Symmetryclass C { int x; public boolean equals(Object o) { return o instanceof C && x == ((C) o).x; }}class D extends C { int y; public boolean equals(Object o) { return super.equals(o) && o instanceof D && y == ((D) o).y; }}(new D()).equals(new C()) -- false(new C()).equals(new D()) -- trueTuesday, April 27, 2010Symmetry• Solution 1:class C { int x; public boolean equals(Object o) { return o instanceof C && x == ((C) o).x && o.equals(this); }}Tuesday, April 27, 2010Symmetry• Solution 2:class C { int x; public boolean equals(Object o) { return o.getClass() == this.getClass() && x == ((C) o).x; }}Tuesday, April 27, 2010Symmetry• Guideline:•If a class C overrides equals, every subclass of C should override equals alsoTuesday, April 27, 2010null•x.equals(null) should return false for anyx != nullTuesday, April 27, 2010Consistency•Multiple invocations of x.equals(y) should consistently return either true or false provided no fields of x or y change• Broken (obviously):class C { boolean equals(Object o) { return java.lang.Math.random() < .5; }}Tuesday, April 27, 2010Mutable stateclass C { int x; boolean equals(Object o) { return o.getClass() == getClass() && ((C) o).x == x; }}C c1 = new C();C c2 = new C();c1.equals(c2); // truec1.x = 1;c1.equals(c2); // falseTuesday, April 27, 2010Mutable state• Be careful!• Object might be changed by another thread, or might change in a non-obvious wayif (x.equals(y)) { ... // other thread modifies x.f assert x.equals(y); // fails!}•Guideline: equals should not depend on mutable stateTuesday, April 27, 2010hashCode•If x.equals(y), thenx.hashCode() == y.hashCode()• Otherwise, collections break!•Guideline: hashCode should be overridden whenever equals is overriddenTuesday, April 27, 2010hashCode bug• Guideline: hashCode should not depend on mutable state• Bug:hashMap.put(k, v);k.mutate();assert hashMap.get(k) == v; // fails!Tuesday, April 27, 2010Deep vs. shallow equality• Shallow:• .equals compares fields with ==• Deep:• .equals compares fields with .equalsTuesday, April 27, 2010Language and tool support• Eclipse:• warns if hashCode not overridden with equals• Scala case classes• == does structural comparison of fields rather than pointer identity• Ruby:• == same value• .eql? same value and same type• .equal? same objectTuesday, April 27, 2010Real numbersTuesday, April 27, 2010Real numbers• Read:• What Every Computer Scientist Should Know About Floating-Point Arithmetic• http://docs.sun.com/source/806-3568/ncg_goldberg.html• Several different possible representations• Not possible to represent exactly, of course• => rounding errorsTuesday, April 27, 2010Floats• Most common representation of real numbers• Base B and precision p• B=10, p=3• 0.1 = 1.00 x 10-1 (exact)• B=2, p=24• 0.1 = 1.10011001100110011001101 x 2-4 (inexact)• In general• +/- d0.d1d...dp-1 x Be•d.dd...d = significand (or mantissa), has p digits•e = exponentTuesday, April 27, 2010IEEE FloatsNameCommon nameBaseDigitsEminEmaxbinary16half211-1415binary32single, float224-126127binary64double253-10221023binary128quadruple2113-1638216383decimal32107-9596decimal641016-383384decimal1281034-61436144Tuesday, April 27, 2010Extended precision• 80-bit floating point• Often “long double” in C• Supported on x86• instruction to switch processor precision mode• expensive to switch• can’t be done on a per-instruction basis• Although:• sometimes “long double” = double (Visual C++)• sometimes “long double” = quadTuesday, April 27, 2010Rounding errors• Suppose B=10, p=3•Without rounding:• x = 2.15 x 1012• y = 1.25 x 10-5• ->• x = 2.15 x 1012• y = 0.0000000000000000125 x 1012• x - y = 2.1499999999999999875 x 1012Tuesday, April 27, 2010Rounding errors• Suppose B=10, p=3•With rounding:• x = 2.15 x 1012• y = 1.25 x 10-5• ->• x = 2.15 x 1012• y = 0.00 x 1012• x - y = 2.15 x 1012Tuesday, April 27, 2010Rounding errors• Suppose B=10, p=3• 10.1 - 9.93• Without rounding: 0.17• With rounding:• x = 1.01 x 101• y = 0.99 x 101• x - y = 0.02 x 101• error = |0.2 - 0.17| / 0.17 = 17.65%• rounding error, even though result (0.17) could be represented exactlyTuesday, April 27, 2010Rounding errors• Theorem:• if x and y are floats with representation (B,p) with
View Full Document
Unlocking...