001: /*
002:
003: This software is OSI Certified Open Source Software.
004: OSI Certified is a certification mark of the Open Source Initiative.
005:
006: The license (Mozilla version 1.0) can be read at the MMBase site.
007: See http://www.MMBase.org/license
008:
009: */
010: package org.mmbase.util;
011:
012: /**
013: * http://www.macchiato.com/columns/Durable6.html
014: *
015: * Hash Collections (HashSet, HashMap, Hashtable, etc) are typically implemented with an array of buckets.
016: * Each bucket is itself an array or linked list of <key, value> pairs. To decide which keys go into
017: * which buckets, the array index for the bucket is produced by taking the hash value, modulo the size
018: * of the collection. That is,
019: * <code>bucketIndex = abs(hashValue % tableSize);</code>
020: * Within each bucket, the search for the object is sequential, and uses equals. In the ideal case, the
021: * table size is a prime number, the hash values would be evenly distributed, and each bucket would
022: * contain just one value. Lookup in that case is incredibly fast: just one call to hashCode and one call
023: * to equals. If the hash values (modulo the table size) are constant, you have the worst case; all the
024: * objects will be in one bucket, and accessing the objects will require a sequential search through every
025: * single item in the hash table, calling equals for every single item. Lookup in that case will be incredibly
026: * slooow!
027: *
028: * Requirements: synchronization with Equality
029: * <code>If x.equals(y), then x.hashCode() == y.hashCode()</code>
030: * That is, if two objects are equal, then their hash values are equal. Not that the reverse is not true;
031: * two objects may have the same hash value but not be equal!
032: *
033: * Basic design goals:
034: * Even Distribution
035: * An ideal implementation would return integer values that are
036: * evenly distributed over the range from zero to Integer.MAX_VALUE.
037: * That is, if I picked a million random objects, their hash values
038: * would be pretty randomly distributed over this range. In the best
039: * case, any unequal objects would have different hash values.
040: * Fast
041: * An ideal implementation would compute the hash value very quickly.
042: * After all, this method is going to be called every time an object
043: * is put into a hash-based collection, and every time you query whether
044: * an object is in a hash-based collection.
045: * Simple
046: * Since you should implement this for every object that could go into
047: * hash-based collections, you want your code to be simple to write and easy
048: * to maintain.
049: *
050: * @since MMBase-1.8
051: */
052: final public class HashCodeUtil {
053:
054: private static final int PRIME = 1000003;
055:
056: public static final int hashCode(int source, boolean x) {
057: return PRIME * source + (x ? 1 : 0);
058: }
059:
060: public static final int hashCode(int source, int x) {
061: return PRIME * source + x;
062: }
063:
064: public static final int hashCode(int source, long x) {
065: return PRIME * source
066: + (int) (PRIME * (x >>> 32) + (x & 0xFFFFFFFF));
067: }
068:
069: public static final int hashCode(int source, float x) {
070: return hashCode(source, x == 0.0F ? 0 : Float.floatToIntBits(x));
071: }
072:
073: public static final int hashCode(int source, double x) {
074: return hashCode(source, x == 0.0 ? 0L : Double
075: .doubleToLongBits(x));
076: }
077:
078: public static final int hashCode(int source, Object x) {
079: return hashCode(source, x == null ? 0 : x.hashCode());
080: }
081:
082: public static final int hashCode(int source, boolean[] x) {
083: for (boolean element : x) {
084: source = hashCode(source, element);
085: }
086: return source;
087: }
088:
089: public static final int hashCode(int source, int[] x) {
090: for (int element : x) {
091: source = hashCode(source, element);
092: }
093: return source;
094: }
095:
096: public static final int hashCode(int source, long[] x) {
097: for (long element : x) {
098: source = hashCode(source, element);
099: }
100: return source;
101: }
102:
103: public static final int hashCode(int source, float[] x) {
104: for (float element : x) {
105: source = hashCode(source, element);
106: }
107: return source;
108: }
109:
110: public static final int hashCode(int source, double[] x) {
111: for (double element : x) {
112: source = hashCode(source, element);
113: }
114: return source;
115: }
116:
117: public static final int hashCode(int source, Object[] x) {
118: for (Object element : x) {
119: source = hashCode(source, element);
120: }
121: return source;
122: }
123:
124: public static final int hashCodeGentle(int source, Object[] x) {
125: source = PRIME * source + x.length;
126: for (Object element : x) {
127: source = PRIME * source + element.hashCode();
128: }
129: return source;
130: }
131:
132: public static final int hashCodeGentle2(int source, Object[] x) {
133: int last = x.length - 1;
134: int i = 0, j = last;
135: source = PRIME * source + last;
136: for (; i < j; i = 17 * (i + 1) >> 4, j = last - i) {
137: source = PRIME * source + x[i].hashCode();
138: source = PRIME * source + x[j].hashCode();
139: }
140: if (i == j) {
141: source = PRIME * source + x[i].hashCode();
142: }
143: return source;
144: }
145: }
|