KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > mmbase > util > HashCodeUtil


1 /*
2
3 This software is OSI Certified Open Source Software.
4 OSI Certified is a certification mark of the Open Source Initiative.
5
6 The license (Mozilla version 1.0) can be read at the MMBase site.
7 See http://www.MMBase.org/license
8
9 */
10 package org.mmbase.util;
11
12
13
14 /**
15  * http://www.macchiato.com/columns/Durable6.html
16  *
17  * Hash Collections (HashSet, HashMap, Hashtable, etc) are typically implemented with an array of buckets.
18  * Each bucket is itself an array or linked list of <key, value> pairs. To decide which keys go into
19  * which buckets, the array index for the bucket is produced by taking the hash value, modulo the size
20  * of the collection. That is,
21  * <code>bucketIndex = abs(hashValue % tableSize);</code>
22  * Within each bucket, the search for the object is sequential, and uses equals. In the ideal case, the
23  * table size is a prime number, the hash values would be evenly distributed, and each bucket would
24  * contain just one value. Lookup in that case is incredibly fast: just one call to hashCode and one call
25  * to equals. If the hash values (modulo the table size) are constant, you have the worst case; all the
26  * objects will be in one bucket, and accessing the objects will require a sequential search through every
27  * single item in the hash table, calling equals for every single item. Lookup in that case will be incredibly
28  * slooow!
29  *
30  * Requirements: synchronization with Equality
31  * <code>If x.equals(y), then x.hashCode() == y.hashCode()</code>
32  * That is, if two objects are equal, then their hash values are equal. Not that the reverse is not true;
33  * two objects may have the same hash value but not be equal!
34  *
35  * Basic design goals:
36  * Even Distribution
37  * An ideal implementation would return integer values that are
38  * evenly distributed over the range from zero to Integer.MAX_VALUE.
39  * That is, if I picked a million random objects, their hash values
40  * would be pretty randomly distributed over this range. In the best
41  * case, any unequal objects would have different hash values.
42  * Fast
43  * An ideal implementation would compute the hash value very quickly.
44  * After all, this method is going to be called every time an object
45  * is put into a hash-based collection, and every time you query whether
46  * an object is in a hash-based collection.
47  * Simple
48  * Since you should implement this for every object that could go into
49  * hash-based collections, you want your code to be simple to write and easy
50  * to maintain.
51  *
52  * @since MMBase-1.8
53  */
54 final public class HashCodeUtil {
55
56    private static final int PRIME = 1000003;
57
58    public static final int hashCode(int source, boolean x) {
59       return PRIME * source + (x ? 1 : 0);
60    }
61
62    public static final int hashCode(int source, int x) {
63       return PRIME * source + x;
64    }
65
66    public static final int hashCode(int source, long x) {
67       return PRIME * source + (int) (PRIME * (x >>> 32) + (x & 0xFFFFFFFF));
68    }
69
70    public static final int hashCode(int source, float x) {
71       return hashCode(source, x == 0.0F ? 0 : Float.floatToIntBits(x));
72    }
73
74    public static final int hashCode(int source, double x) {
75       return hashCode(source, x == 0.0 ? 0L : Double.doubleToLongBits(x));
76    }
77
78    public static final int hashCode(int source, Object JavaDoc x) {
79       return hashCode(source, x == null ? 0 : x.hashCode());
80    }
81    
82    public static final int hashCode(int source, boolean[] x) {
83       for (int i = 0; i < x.length; ++i) {
84          source = hashCode(source, x[i]);
85       }
86       return source;
87    }
88
89    public static final int hashCode(int source, int[] x) {
90       for (int i = 0; i < x.length; ++i) {
91          source = hashCode(source, x[i]);
92       }
93       return source;
94    }
95
96    public static final int hashCode(int source, long[] x) {
97       for (int i = 0; i < x.length; ++i) {
98          source = hashCode(source, x[i]);
99       }
100       return source;
101    }
102    
103    public static final int hashCode(int source, float[] x) {
104       for (int i = 0; i < x.length; ++i) {
105          source = hashCode(source, x[i]);
106       }
107       return source;
108    }
109    
110    public static final int hashCode(int source, double[] x) {
111       for (int i = 0; i < x.length; ++i) {
112          source = hashCode(source, x[i]);
113       }
114       return source;
115    }
116
117    public static final int hashCode(int source, Object JavaDoc[] x) {
118       for (int i = 0; i < x.length; ++i) {
119          source = hashCode(source, x[i]);
120       }
121       return source;
122    }
123
124    
125    public static final int hashCodeGentle(int source, Object JavaDoc[] x) {
126       source = PRIME * source + x.length;
127       for (int i = 0; i < x.length; i++) {
128         source = PRIME * source + x[i].hashCode();
129       }
130       return source;
131    }
132
133    public static final int hashCodeGentle2(int source, Object JavaDoc[] x) {
134       int last = x.length - 1;
135       int i = 0, j = last;
136       source = PRIME * source + last;
137       for (; i < j; i = 17 * (i + 1) >> 4, j = last - i) {
138          source = PRIME * source + x[i].hashCode();
139          source = PRIME * source + x[j].hashCode();
140       }
141       if (i == j) {
142          source = PRIME * source + x[i].hashCode();
143       }
144       return source;
145    }
146 }
Popular Tags