Status update: HashSet

Wednesday, January 6, 2010
I've implemented the HashSet class. This is written entirely in Tart, and should be about the same speed as a native C version, although I haven't actually benchmarked the performance. The algorithm is a quadratically probed hash table. The hash function itself is specific to the type of item in the set, but generic hash functions (via murmurhash) are available for ints, strings, and any type that can be converted into a byte array. (The hash functions are also written purely in Tart.)

Here's one of the unit tests to give you a sense of how it can be used:

def testAddMany {
  let h = HashSet[String]();
  h.addAll("1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14",
           "15", "16", "17");
  assertEq(17, h.length);
  assertFalse(h.isEmpty);
  assertTrue("1" in h);
  assertTrue("2" in h);
  assertTrue("3" in h);
  assertTrue("4" in h);
  assertTrue("16" in h);
  assertTrue("17" in h);
}

Getting HashSet to work required fixing a lot of bugs related to passing small structs around and implementing the 'struct return param' for larger structs.

0 comments:

Post a Comment