CSC301: Week 5: Hash Tables (3.4)

Contents [0/9]

Built in Hash Functions [1/9]
Amusing collisions [2/9]
Implement your own Hash Functions [3/9]
Phone numbers [4/9]
Phone numbers Performance [5/9]
Phone numbers with bad equality [6/9]
Phone numbers lost in a table [7/9]
Floating point gone bad [8/9]
Floating point the right way [9/9]

(Click here for one slide per page)


Built in Hash Functions [1/9]

file:algs34/XBuiltInHashcodes.java [source] [doc-public] [doc-private]
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
package algs34;

import java.util.Arrays;
import java.util.Objects;

public class XBuiltInHashcodes {
  public static void main (String[] args) {
    System.out.format ("int\n");
    System.out.format ("%x ", Integer.hashCode (0));
    System.out.format ("%x ", Integer.hashCode (1));
    System.out.format ("%x ", Integer.hashCode (2));
    System.out.format ("%x ", Integer.hashCode (Integer.MAX_VALUE));
    System.out.format ("%x ", Integer.hashCode (-0));
    System.out.format ("%x ", Integer.hashCode (-1));
    System.out.format ("%x ", Integer.hashCode (-2));
    System.out.format ("%x ", Integer.hashCode (Integer.MIN_VALUE));
    System.out.println ();

    System.out.format ("\nlong\n");
    System.out.format ("%x ", Long.hashCode (0));
    System.out.format ("%x ", Long.hashCode (1));
    System.out.format ("%x ", Long.hashCode (2));
    System.out.format ("%x ", Long.hashCode (Long.MAX_VALUE));
    System.out.format ("%x ", Long.hashCode (-0));
    System.out.format ("%x ", Long.hashCode (-1));
    System.out.format ("%x ", Long.hashCode (-2));
    System.out.format ("%x ", Long.hashCode (Long.MIN_VALUE));
    System.out.println ();

    System.out.format ("\nfloat\n");
    System.out.format ("%x ", Float.hashCode (0));
    System.out.format ("%x ", Float.hashCode (1));
    System.out.format ("%x ", Float.hashCode (2));
    System.out.format ("%x ", Float.hashCode (Float.MAX_VALUE));
    System.out.format ("%x ", Float.hashCode (-0));
    System.out.format ("%x ", Float.hashCode (-1));
    System.out.format ("%x ", Float.hashCode (-2));
    System.out.format ("%x ", Float.hashCode (Float.MIN_VALUE));
    System.out.println ();

    System.out.format ("\ndouble\n");
    System.out.format ("%x ", Double.hashCode (0));
    System.out.format ("%x ", Double.hashCode (1));
    System.out.format ("%x ", Double.hashCode (2));
    System.out.format ("%x ", Double.hashCode (Double.MAX_VALUE));
    System.out.format ("%x ", Double.hashCode (-0));
    System.out.format ("%x ", Double.hashCode (-1));
    System.out.format ("%x ", Double.hashCode (-2));
    System.out.format ("%x ", Double.hashCode (Double.MIN_VALUE));
    System.out.println ();

    System.out.format ("\nchar\n");
    System.out.format ("%x ", Character.hashCode ('0'));
    System.out.format ("%x ", Character.hashCode ('1'));
    System.out.format ("%x ", Character.hashCode ('2'));
    System.out.println ();

    System.out.format ("\nstring\n");
    System.out.format ("%x ", Objects.hashCode ("0"));
    System.out.format ("%x ", Objects.hashCode ("1"));
    System.out.format ("%x ", Objects.hashCode ("2"));
    System.out.println ();

    System.out.format ("\nstring decimal\n");
    System.out.format ("%d ", Objects.hashCode ("0"));
    System.out.format ("%d ", Objects.hashCode ("1"));
    System.out.format ("%d ", Objects.hashCode ("2"));
    System.out.println ();

    System.out.format ("%d (=%d*31 + %d) ", Objects.hashCode ("00"), (int)'0', (int)'0');
    System.out.format ("%d (=%d*31 + %d) ", Objects.hashCode ("01"), (int)'0', (int)'1');
    System.out.format ("%d (=%d*31 + %d) ", Objects.hashCode ("02"), (int)'0', (int)'2');
    System.out.println ();

    System.out.format ("\nstring\n");
    System.out.format ("%d ", Objects.hashCode ("0"));
    System.out.format ("%d ", Objects.hashCode ("00"));
    System.out.format ("%d ", Objects.hashCode ("000"));
    System.out.format ("%d ", Objects.hashCode ("0000"));
    System.out.format ("%d ", Objects.hashCode ("00000"));
    System.out.format ("%d ", Objects.hashCode ("000000"));
    System.out.format ("%d ", Objects.hashCode ("0000000"));
    System.out.format ("%d ", Objects.hashCode ("00000000"));
    System.out.format ("%d ", Objects.hashCode ("000000000"));
    System.out.println ();

    {
      System.out.format ("\nfloat 0's\n");
      float x = Float.intBitsToFloat (0);
      float y = Float.intBitsToFloat (0x80000000);
      System.out.format ("(x==y)=%b Float.compare(x,y)=%d\n", x==y, Float.compare (x, y));
      System.out.format ("x=%s Float.hashCode(x)=%x\n", x, Float.hashCode (x));
      System.out.format ("y=%s Float.hashCode(y)=%x\n", y, Float.hashCode (y));
    }
    {
      System.out.format ("\nfloat NaN's\n");
      float x = Float.NaN;
      float y = Float.NaN;
      System.out.format ("(x==y)=%b Float.compare(x,y)=%d\n", x==y, Float.compare (x, y));
      System.out.format ("x=%s Float.hashCode(x)=%x\n", x, Float.hashCode (x));
      System.out.format ("y=%s Float.hashCode(y)=%x\n", y, Float.hashCode (y));
    }
    {
      System.out.format ("\ndouble 0's\n");
      double x = Double.longBitsToDouble (0L);
      double y = Double.longBitsToDouble (0x8000000000000000L);
      System.out.format ("(x==y)=%b Double.compare(x,y)=%d\n", x==y, Double.compare (x, y));
      System.out.format ("x=%s Double.hashCode(x)=%x\n", x, Double.hashCode (x));
      System.out.format ("y=%s Double.hashCode(y)=%x\n", y, Double.hashCode (y));
    }
    {
      System.out.format ("\ndouble NaN's\n");
      double x = Double.NaN;
      double y = Double.NaN;
      System.out.format ("(x==y)=%b Double.compare(x,y)=%d\n", x==y, Double.compare (x, y));
      System.out.format ("x=%s Double.hashCode(x)=%x\n", x, Double.hashCode (x));
      System.out.format ("y=%s Double.hashCode(y)=%x\n", y, Double.hashCode (y));
    }

    /*
     * Objects and Arrays act like this:
     *
     * Objects.equals(a, b) { return (a == b) || (a != null && a.equals(b)); }
     *   if (a==b) return true;
     *   if (a==null || b==null || (! a.equals(b)) return false;
     *   return true;
     * }
     * Objects.hashCode(a)  {
     *   if (a==null) return 0;
     *   return a.hashCode();
     * }
     *
     * Arrays.equals(a, b) {
     *   if (a==b) return true;
     *   if (a==null || b==null || (a.length != b.length)) return false;
     *   for (int i=0; i<a.length; i++) if (! Objects.equals(a[i],b[i])) return false;
     *   return true;
     * }
     * Arrays.hashCode(a) {
     *   if (a == null) return 0;
     *   int result = 1;
     *   for (Object element : a) result = 31 * result + Objects.hashCode(element);
     *   return result;
     * }
     *
     * Arrays.deepEquals is similar, but recursively calls Arrays.equals(a[i],b[i]) for nested arrays
     * Arrays.deepHashCode is similar, but recursively calls Arrays.hashCode(element) for nested arrays
     */
    {
      System.out.format ("\nObject\n");
      Object x = new Object ();
      Object y = new Object ();
      System.out.format ("(x==y)=%b Objects.equals(x,y)=%b\n", x==y, Objects.equals (x,y));
      System.out.format ("x=%s Objects.hashCode(x)=%x\n", x, Objects.hashCode (x));
      System.out.format ("y=%s Objects.hashCode(y)=%x\n", y, Objects.hashCode (y));
    }
    {
      System.out.format ("\nObject null\n");
      Object x = null;
      Object y = null;
      System.out.format ("(x==y)=%b Objects.equals(x,y)=%b\n", x==y, Objects.equals (x,y));
      System.out.format ("x=%s Objects.hashCode(x)=%x\n", x, Objects.hashCode (x));
      System.out.format ("y=%s Objects.hashCode(y)=%x\n", y, Objects.hashCode (y));
    }
    {
      System.out.format ("\nint[]\n");
      int a[] = new int[4];
      int b[] = new int[4];
      System.out.format ("(a==b)=%b Objects.equals(a,b)=%b Arrays.equals(a,b)=%b\n", a==b, Objects.equals (a,b), Arrays.equals(a,b));
      System.out.format ("a=%s Objects.hashCode(a)=%x Arrays.hashCode(a)=%x\n", a, Objects.hashCode (a), Arrays.hashCode (a));
      System.out.format ("b=%s Objects.hashCode(b)=%x Arrays.hashCode(b)=%x\n", b, Objects.hashCode (b), Arrays.hashCode (b));
    }
    {
      System.out.format ("\nint[] null\n");
      int a[] = null;
      int b[] = null;
      System.out.format ("(a==b)=%b Objects.equals(a,b)=%b Arrays.equals(a,b)=%b\n", a==b, Objects.equals (a,b), Arrays.equals(a,b));
      System.out.format ("a=%s Objects.hashCode(a)=%x Arrays.hashCode(a)=%x\n", a, Objects.hashCode (a), Arrays.hashCode (a));
      System.out.format ("b=%s Objects.hashCode(b)=%x Arrays.hashCode(b)=%x\n", b, Objects.hashCode (b), Arrays.hashCode (b));
    }
    {
      System.out.format ("\nObject[] (for most object arrays, Arrays.equals is enough)\n");
      String a[] = new String[] { new String("hi") };
      String b[] = new String[] { new String("hi") };
      System.out.format ("(a==b)=%b Objects.equals(a,b)=%b Arrays.equals(a,b)=%b Arrays.deepEquals(a,b)=%b\n", a==b, Objects.equals (a,b), Arrays.equals(a,b), Arrays.deepEquals(a,b));
      System.out.format ("a=%s Objects.hashCode(a)=%x Arrays.hashCode(a)=%x Arrays.deepHashCode(a)=%x\n", a, Objects.hashCode (a), Arrays.hashCode (a), Arrays.deepHashCode (a));
      System.out.format ("b=%s Objects.hashCode(b)=%x Arrays.hashCode(b)=%x Arrays.deepHashCode(b)=%x\n", b, Objects.hashCode (b), Arrays.hashCode (b), Arrays.deepHashCode (b));
    }
    {
      System.out.format ("\nint[][] (multidimensional arrays need Arrays.deepEquals)\n");
      int a[][] = new int[4][4];
      int b[][] = new int[4][4];
      System.out.format ("(a==b)=%b Objects.equals(a,b)=%b Arrays.equals(a,b)=%b Arrays.deepEquals(a,b)=%b\n", a==b, Objects.equals (a,b), Arrays.equals(a,b), Arrays.deepEquals(a,b));
      System.out.format ("a=%s Objects.hashCode(a)=%x Arrays.hashCode(a)=%x Arrays.deepHashCode(a)=%x\n", a, Objects.hashCode (a), Arrays.hashCode (a), Arrays.deepHashCode (a));
      System.out.format ("b=%s Objects.hashCode(b)=%x Arrays.hashCode(b)=%x Arrays.deepHashCode(b)=%x\n", b, Objects.hashCode (b), Arrays.hashCode (b), Arrays.deepHashCode (b));
    }
  }
}

Amusing collisions [2/9]

file:algs34/XStringHashcodes.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
package algs34;
public class XStringHashcodes {
  public static void main (String[] args) {
    // from http://stackoverflow.com/questions/2310498/why-doesnt-strings-hashcode-cache-0
    String[] strings = new String[] {
        "pollinating sandboxes",
        "amusement & hemophilias",
        "schoolworks = perversive",
        "electrolysissweeteners.net",
        "constitutionalunstableness.net",
        "grinnerslaphappier.org",
        "BLEACHINGFEMININELY.NET",
        "WWW.BUMRACEGOERS.ORG",
        "WWW.RACCOONPRUDENTIALS.NET",
        "Microcomputers: the unredeemed lollipop...",
        "Incentively, my dear, I don't tessellate a derangement.",
        "A person who never yodelled an apology, never preened vocalizing transsexuals.",
        "polygenelubricants",
        "And so my fellow mismanagements: ask not what your newsdealer can sugarcoat for you -- ask what you can sugarcoat for your newsdealer."
    };
    for (String s : strings) {
      System.out.format ("%x %s\n", s.hashCode (), s);
    }
  }
}

Implement your own Hash Functions [3/9]

file:algs34/XStudent.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
package algs34;

import java.util.Arrays;
import java.util.Objects;
import stdlib.*;

public class XStudent {
  int i;
  double d;
  int[] a;
  Object o;

  public boolean equals(Object y) {
    //Trace.draw ();
    if (y == this) return true;
    if (y == null) return false;
    if (y.getClass() != this.getClass()) return false;
    XStudent that = (XStudent) y;
    if (Integer.compare (this.i, that.i) != 0) return false;
    if (Double.compare (this.d, that.d) != 0) return false;
    if (! Arrays.equals (this.a, that.a)) return false;
    if (! Objects.equals (this.o, that.o)) return false;
    // don't use ((this.o).equals(that.o)) unless you know that (this.o!=null)
    return true;
  }
  public int hashCode() {
    int h = 17;
    h = 31 * h + Integer.hashCode (i);
    h = 31 * h + Double.hashCode (d);
    h = 31 * h + Arrays.hashCode (a);
    h = 31 * h + Objects.hashCode (o);
    // don't use (o.hashCode()) unless you know that (o!=null)
    return h;
  }


  public XStudent (double d, int[] a, Object o) {
    this.d = d;
    this.a = a;
    this.o = o;
  }
  public static void main (String[] args) {
    //Trace.run ();
    Object p = new Object ();
    XStudent x = new XStudent (0.1, new int[] { 1,2,3 }, p);
    XStudent y = new XStudent (0.1, new int[] { 1,2,3 }, p);
    StdOut.format ("(x==y)=%b x.equals(y)=%b\n", x==y, Objects.equals(x,y));
    StdOut.format ("x=%s Objects.hashCode(x)=%x\n", x, Objects.hashCode (x));
    StdOut.format ("y=%s Objects.hashCode(y)=%x\n", y, Objects.hashCode (y));
  }
}

Phone numbers [4/9]

file:algs34/XPhoneNumber.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
package algs34;
import stdlib.*;
import java.util.HashSet;
/* ***********************************************************************
 *  Compilation:  javac PhoneNumber.java
 *  Execution:    java PhoneNumber
 *  Dependencies:
 *
 *  Immutable data type for US phone numbers.
 *
 *************************************************************************/

public final class XPhoneNumber {
  private final int area;   // area code (3 digits)
  private final int exch;   // exchange  (3 digits)
  private final int ext;    // extension (4 digits)

  public XPhoneNumber(int area, int exch, int ext) {
    this.area = area;
    this.exch = exch;
    this.ext  = ext;
  }

  // how you're supposed to implement equals
  public boolean equals(Object y) {
    if (y == this) return true;
    if (y == null) return false;
    if (y.getClass() != this.getClass()) return false;
    XPhoneNumber that = (XPhoneNumber) y;
    if (!((this.area == that.area) && (this.exch == that.exch) && (this.ext == that.ext))) return false;
    return true;
  }

  // satisfies the hashCode contract
  public int hashCode() {
    int h = 17;
    h = ext + 31 * h;
    h = exch + 31 * h;
    h = area + 31 * h;
    return h;
  }

  // 0 for padding with leading 0s
  public String toString() {
    return String.format("(%03d) %03d-%04d", area, exch, ext);
  }

  public static void main(String[] args) {
    XPhoneNumber a = new XPhoneNumber(609, 258, 4455);
    XPhoneNumber b = new XPhoneNumber(609, 876, 5309);
    XPhoneNumber c = new XPhoneNumber(609, 003, 5309);
    XPhoneNumber d = new XPhoneNumber(215, 876, 5309);
    XPhoneNumber e = new XPhoneNumber(609, 876, 5309);
    StdOut.format("a = %s [hashcode=%d]\n", a, a.hashCode ());
    StdOut.format("b = %s [hashcode=%d]\n", b, b.hashCode ());
    StdOut.format("c = %s [hashcode=%d]\n", c, c.hashCode ());
    StdOut.format("d = %s [hashcode=%d]\n", d, d.hashCode ());
    StdOut.format("e = %s [hashcode=%d]\n", e, e.hashCode ());

    HashSet<XPhoneNumber> set = new HashSet<>();
    set.add(a);
    set.add(b);
    set.add(c);
    StdOut.println("Added a, b, and c");
    StdOut.println("contains a:  " + set.contains(a));
    StdOut.println("contains b:  " + set.contains(b));
    StdOut.println("contains c:  " + set.contains(c));
    StdOut.println("contains d:  " + set.contains(d));
    StdOut.println("contains e:  " + set.contains(e));
    StdOut.println("b == e:      " + (b == e));
    StdOut.println("b.equals(e): " + (b.equals(e)));
  }



}

Phone numbers Performance [5/9]

file:algs34/XPhoneNumberPerformanceTest.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
package algs34;

import stdlib.*;

public class XPhoneNumberPerformanceTest {
  private static int NUM_SIZES = 8;
  private static int START_SIZE = 25000;
  public static void main(String[] args) {
    Object val = new Object ();
    int size = START_SIZE;
    for (int count=1; count<NUM_SIZES; count++) {
      size += size;
      //java.util.IdentityHashMap<XPhoneNumber,Object> set = new java.util.IdentityHashMap <>();
      java.util.HashMap<XPhoneNumber,Object> set = new java.util.HashMap <>();
      //SeparateChainingHashST<XPhoneNumber,Object> set = new SeparateChainingHashST <>();
      //LinearProbingHashST<XPhoneNumber,Object> set = new LinearProbingHashST <>();
      Stopwatch sw1 = new Stopwatch ();
      for (int i=size-1; i>=0; i--) {
        XPhoneNumber x = new XPhoneNumber
          (StdRandom.uniform (1000), StdRandom.uniform (1000), StdRandom.uniform (10000));
        set.put(x,val);
      }
      double time1 = sw1.elapsedTime ();
      Stopwatch sw2 = new Stopwatch ();
//      for (int i=size-1; i>=0; i--) {
//        XPhoneNumber x = new XPhoneNumber
//          (StdRandom.uniform (1000), StdRandom.uniform (1000), StdRandom.uniform (10000));
//        //set.containsKey (x);
//        set.contains (x);
//      }
      double time2 = sw1.elapsedTime ();
      System.out.format ("%9d: add=%f contains=%f\n", size, time1, time2);
    }
  }
}

Phone numbers with bad equality [6/9]

file:algs34/XPhoneNumberOverload.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
package algs34;
import stdlib.*;
import java.util.HashSet;
/* ***********************************************************************
 *  Compilation:  javac PhoneNumber.java
 *  Execution:    java PhoneNumber
 *  Dependencies:
 *
 *  Immutable data type for US phone numbers, but with a broken
 *  overloaded implementation of equals(). By implementing equals()
 *  with the signature
 *
 *       public boolean equals(PhoneNumber that)
 *
 *  we do not override the equals() method inherited from Object.
 *  This causes unexpected behavior when used with java.util.HashSet.
 *
 *  DO NOT USE THIS CLASS
 *
 *************************************************************************/

public final class XPhoneNumberOverload {
  private final int area;   // area code (3 digits)
  private final int exch;   // exchange  (3 digits)
  private final int ext;    // extension (4 digits)

  public XPhoneNumberOverload(int area, int exch, int ext) {
    this.area = area;
    this.exch = exch;
    this.ext  = ext;
  }

  // overloaded equals - don't do this
  public boolean equals(XPhoneNumberOverload that) {
    return (this.area == that.area) && (this.exch == that.exch) && (this.ext == that.ext);
  }

  // satisfies the hashCode contract
  public int hashCode() {
    int h = 17;
    h = ext + 31 * h;
    h = exch + 31 * h;
    h = area + 31 * h;
    return h;
  }

  // 0 for padding with leading 0s
  public String toString() {
    return String.format("(%03d) %03d-%04d", area, exch, ext);
  }

  public static void main(String[] args) {
    XPhoneNumberOverload a = new XPhoneNumberOverload(609, 258, 4455);
    XPhoneNumberOverload b = new XPhoneNumberOverload(609, 876, 5309);
    XPhoneNumberOverload c = new XPhoneNumberOverload(609, 003, 5309);
    XPhoneNumberOverload d = new XPhoneNumberOverload(215, 876, 5309);
    XPhoneNumberOverload e = new XPhoneNumberOverload(609, 876, 5309);
    Object o = e;
    StdOut.format("a = %s [hashcode=%d]\n", a, a.hashCode ());
    StdOut.format("b = %s [hashcode=%d]\n", b, b.hashCode ());
    StdOut.format("c = %s [hashcode=%d]\n", c, c.hashCode ());
    StdOut.format("d = %s [hashcode=%d]\n", d, d.hashCode ());
    StdOut.format("e = %s [hashcode=%d]\n", e, e.hashCode ());

    // show broken behavior when you use covariant equals with a Set
    HashSet<XPhoneNumberOverload> set = new HashSet<>();
    set.add(a);
    set.add(b);
    set.add(c);
    StdOut.println("Added a, b, and c");
    StdOut.println("contains a:  " + set.contains(a));
    StdOut.println("contains b:  " + set.contains(b));
    StdOut.println("contains c:  " + set.contains(c));
    StdOut.println("contains d:  " + set.contains(d));
    StdOut.println("***contains e:  " + set.contains(e));  // not in set, but it should be!
    StdOut.println("b == e:      " + (b == e));
    StdOut.println("b.equals(e): " + (b.equals(e)));
    StdOut.println("o == e:      " + (o == e));
    StdOut.println("b.equals(o): " + (b.equals(o)));
  }

}

Phone numbers lost in a table [7/9]

file:algs34/XPhoneNumberMutable.java [source] [doc-public] [doc-private]
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
 
package algs34;
import stdlib.*;
import java.util.HashSet;
/* ***********************************************************************
 *  Compilation:  javac PhoneNumber.java
 *  Execution:    java PhoneNumber
 *  Dependencies:
 *
 *  Mutable data type for US phone numbers, with overridden versions
 *  equals and hashcode.  This can cause data to get lost in java.util.HashSet.
 *
 *  DO NOT USE THIS CLASS
 *************************************************************************/

public final class XPhoneNumberMutable {
  private int area;   // area code (3 digits)
  private int exch;   // exchange  (3 digits)
  private int ext;    // extension (4 digits)

  public XPhoneNumberMutable(int area, int exch, int ext) {
    this.area = area;
    this.exch = exch;
    this.ext  = ext;
  }

  public void set(int area, int exch, int ext) {
    this.area = area;
    this.exch = exch;
    this.ext  = ext;
  }

  // how you're supposed to implement equals
  public boolean equals(Object y) {
    if (y == this) return true;
    if (y == null) return false;
    if (y.getClass() != this.getClass()) return false;
    XPhoneNumberMutable that = (XPhoneNumberMutable) y;
    return (this.area == that.area) && (this.exch == that.exch) && (this.ext == that.ext);
  }

  // 0 for padding with leading 0s
  public String toString() {
    return String.format("(%03d) %03d-%04d", area, exch, ext);
  }

  // satisfies the hashCode contract
  public int hashCode() {
    int h = 17;
    h = ext + 31 * h;
    h = exch + 31 * h;
    h = area + 31 * h;
    return h;
  }


  public static void main(String[] args) {
    XPhoneNumberMutable a = new XPhoneNumberMutable(609, 258, 4455);
    XPhoneNumberMutable b = new XPhoneNumberMutable(609, 876, 5309);
    XPhoneNumberMutable c = new XPhoneNumberMutable(609, 003, 5309);
    XPhoneNumberMutable d = new XPhoneNumberMutable(215, 876, 5309);
    XPhoneNumberMutable e = new XPhoneNumberMutable(609, 876, 5309);
    StdOut.format("a = %s [hashcode=%d]\n", a, a.hashCode ());
    StdOut.format("b = %s [hashcode=%d]\n", b, b.hashCode ());
    StdOut.format("c = %s [hashcode=%d]\n", c, c.hashCode ());
    StdOut.format("d = %s [hashcode=%d]\n", d, d.hashCode ());
    StdOut.format("e = %s [hashcode=%d]\n", e, e.hashCode ());

    HashSet<XPhoneNumberMutable> set = new HashSet<>();
    set.add(a);
    set.add(b);
    set.add(c);
    StdOut.println("\nAdded a, b, and c: " + set);
    StdOut.println("contains a:  " + set.contains(a));
    StdOut.println("contains b:  " + set.contains(b));
    StdOut.println("contains c:  " + set.contains(c));
    StdOut.println("contains d:  " + set.contains(d));
    StdOut.println("contains e:  " + set.contains(e));
    StdOut.println("b == e:      " + (b == e));
    StdOut.println("b.equals(e): " + (b.equals(e)));

    c.set(609, 876, 5309);
    b.set(609, 003, 5309);
    StdOut.format("\na = %s [hashcode=%d]\n", a, a.hashCode ());
    StdOut.format("b = %s [hashcode=%d]\n", b, b.hashCode ());
    StdOut.format("c = %s [hashcode=%d]\n", c, c.hashCode ());
    StdOut.format("d = %s [hashcode=%d]\n", d, d.hashCode ());
    StdOut.format("e = %s [hashcode=%d]\n", e, e.hashCode ());
    StdOut.println("\nSwapped values of b and c: " + set);
    StdOut.println("contains a:  " + set.contains(a));
    StdOut.println("***contains b:  " + set.contains(b));
    StdOut.println("***contains c:  " + set.contains(c));
    StdOut.println("contains d:  " + set.contains(d));
    StdOut.println("***contains e:  " + set.contains(e));
    StdOut.println("c == e:      " + (c == e));
    StdOut.println("c.equals(e): " + (c.equals(e)));

  }



}

Floating point gone bad [8/9]

file:algs34/XBadPoint.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
package algs34;
import stdlib.*;
import java.util.HashSet;
/* ***********************************************************************
 * Floating point is a pain!
 *************************************************************************/

public final class XBadPoint {
  static class BadPoint {
    private final double x;
    private final double y;
    public BadPoint(double x, double y) { this.x = x; this.y = y; }
    public String toString() { return "(" + x + ", " + y + ")";  }

    public boolean equals(Object other) {
      if (other == this) return true;
      if (other == null || other.getClass() != this.getClass()) return false;
      BadPoint that = (BadPoint) other;
      if (this.x != that.x) return false;
      if (this.y != that.y) return false;
      return true;
    }
    public int hashCode() {
      int h = 17;
      h = 31*h + Double.hashCode(x);
      h = 31*h + Double.hashCode(y);
      return h;
    }
  }

  public static void main(String[] args) {
    BadPoint a = new BadPoint(0.0, 0.0);
    BadPoint b = new BadPoint(0.0, 0.0);
    BadPoint e = new BadPoint(0.0,-0.0);
    StdOut.format("a = %s [hashcode=%d]\n", a, a.hashCode ());
    StdOut.format("b = %s [hashcode=%d]\n", b, b.hashCode ());
    StdOut.format("e = %s [hashcode=%d]\n", e, e.hashCode ());

    HashSet<BadPoint> set = new HashSet<>();
    set.add(a);
    StdOut.println("Added a");
    StdOut.println("a == b:      " + (a == b));
    StdOut.println("a.equals(b): " + (a.equals(b)));
    StdOut.println("contains b:  " + set.contains(b));
    StdOut.println("a == e:      " + (a == e));
    StdOut.println("a.equals(e): " + (a.equals(e)));
    StdOut.println("contains e:  " + set.contains(e));
  }
}

Floating point the right way [9/9]

file:algs34/XGoodPoint.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
package algs34;
import stdlib.*;
import java.util.HashSet;

public final class XGoodPoint {
  static class GoodPoint {
    private final double x;
    private final double y;
    public GoodPoint(double x, double y) { this.x = x; this.y = y; }
    public String toString() { return "(" + x + ", " + y + ")";  }

    public boolean equals(Object other) {
      if (other == this) return true;
      if (other == null || other.getClass() != this.getClass()) return false;
      GoodPoint that = (GoodPoint) other;
      if (Double.compare(this.x,that.x) != 0) return false;
      if (Double.compare(this.y,that.y) != 0) return false;
      return true;
    }
    public int hashCode() {
      int h = 17;
      h = 31*h + Double.hashCode(x);
      h = 31*h + Double.hashCode(y);
      return h;
    }
  }


  public static void main(String[] args) {
    GoodPoint a = new GoodPoint(0.0, 0.0);
    GoodPoint b = new GoodPoint(0.0, 0.0);
    GoodPoint e = new GoodPoint(0.0,-0.0);
    StdOut.format("a = %s [hashcode=%d]\n", a, a.hashCode ());
    StdOut.format("b = %s [hashcode=%d]\n", b, b.hashCode ());
    StdOut.format("e = %s [hashcode=%d]\n", e, e.hashCode ());

    HashSet<GoodPoint> set = new HashSet<>();
    set.add(a);
    StdOut.println("Added a");
    StdOut.println("a == b:      " + (a == b));
    StdOut.println("a.equals(b): " + (a.equals(b)));
    StdOut.println("contains b:  " + set.contains(b));
    StdOut.println("a == e:      " + (a == e));
    StdOut.println("a.equals(e): " + (a.equals(e)));
    StdOut.println("contains e:  " + set.contains(e));
  }
}

Revised: 2008/03/17 13:01