Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
/** 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment