Hash.scala

/** Class for testing the distribution of hashCodes for Products/Collections of items in Scala.
* Should be able to just copy - paste this right into the scala interpreter
*/
object Hashable {
  val HashSeed = 0x27d4eb2d
  val HashConstant = 41
  val NullHashCode = 0

  /**
   * Adapted from
   * http://burtleburtle.net/bob/hash/integer.html
   * Thomas Wang has an integer hash using 
   * multiplication that's faster than any 
   * of mine on my Core 2 duo using gcc -O3,
   * and it passes my favorite sanity tests well.
   * I've had reports it doesn't do well with integer sequences with a multiple of 34.
   *
   */
  //This method doesn't seem to work that well
  def hashWang(x: Int): Int = {
    var a = x
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
  }

  // From http://www.concentric.net/~Ttwang/tech/inthash.htm
  // Seems to work very well
  def hash32shift(x: Int): Int = {
    var key = x
    key = ~key + (key << 15); // key = (key << 15) - key - 1;
    key = key ^ (key >>> 12);
    key = key + (key << 2);
    key = key ^ (key >>> 4);
    key = key * 2057; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >>> 16);
    key;
  }
  
  /**
   * From the scala standard library
   *
   */
  final def improve(hcode: Int) = {
    var h: Int = hcode + ~(hcode << 9)
    h = h ^ (h >>> 14)
    h = h + (h << 4)
    h ^ (h >>> 10)
  }

  def hash(x: Int) = improve(x)

  def calcHash(f: Any) = f match {
    case null => NullHashCode
    case f => f.hashCode
  }

  // A more random value distribution for integers.
  def hashList(fields: Iterable[Any]): Int = {
    (fields map calcHash).foldLeft(HashSeed)((x, y) => hash(x + 41 * hash(y)))
  }
}
import Hashable._
val tot = 100
val hashes = (for(x <- -(tot/2) until (tot/2); y <- -(tot/2) until (tot/2); z <- -(tot/2) until (tot/2)) yield hashList(List(x,y,z))).toList
val ideal = hashes.size * 1.0
//val hset = Set() ++ hashes
//val hsSize = hset.size 
val hlSize = hashes.sort(_<_).removeDuplicates.size
println((ideal, hlSize, hlSize/ideal))