Instantly share code, notes, and snippets.

# benjaminjackman/Hash.scala Created Jan 6, 2010

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))