changeset 81:a905e13db753

Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
author Mike Pavone <pavone@retrodev.com>
date Wed, 18 Jul 2012 08:59:08 -0700
parents cbc92ee13f35
children 48daa1d3e052
files modules/sets.tp
diffstat 1 files changed, 17 insertions(+), 7 deletions(-) [+]
line wrap: on
line diff
--- a/modules/sets.tp	Mon Jul 16 01:22:48 2012 -0700
+++ b/modules/sets.tp	Wed Jul 18 08:59:08 2012 -0700
@@ -3,17 +3,20 @@
 		empty <- #{
 			empty? <- { true }
 		}
+		size <- 0
+		hashdiffs <- #[0]
 		#{
 			buckets <- #[empty empty empty empty]
 			contains? <- :object {
 				hv <- object hash
 				
 				notdone <- true
-				hashes <- #[hv (hv + 1) (hv - 1)]
+				
+				basehash <- hv
 				i <- 0
 				ret <- false
-				while: { if: notdone { i < 3 } } do: {
-					hv <- hashes get: i
+				while: { if: notdone { i < (hashdiffs length) } } do: {
+					hv <- basehash + (hashdiffs get: i)
 					trunc <- hv % (buckets length)
 					if: trunc < 0 { trunc <- 0 - trunc }
 					bucketval <- (buckets get: trunc)	
@@ -41,14 +44,15 @@
 					}
 				}
 				notdone <- true
-				hashes <- #[hv (hv + 1) (hv - 1)]
+				basehash <- hv
 				i <- 0
-				while: { if: notdone { i < 3 } } do: {
-					hv <- hashes get: i
+				while: { if: notdone { i < (hashdiffs length) } } do: {
+					hv <- basehash + (hashdiffs get: i)
 					trunc <- hv % (buckets length)
 					if: trunc < 0 { trunc <- 0 - trunc }
 					bucketval <- (buckets get: trunc)	
 					if: (bucketval empty?) {
+						size <- size + 1
 						buckets set: trunc (makeBucket: hv)
 						notdone <- false
 					} else: {
@@ -59,7 +63,13 @@
 					i <- i + 1
 				}
 				if: notdone {
-					newsize <- (buckets length) * 3
+					newsize <- (buckets length) * 3 + 1
+					lastdiff <- hashdiffs get: ((hashdiffs length) - 1)
+					if: lastdiff <= 0 {
+						hashdiffs append: ((0 - lastdiff) + 1)
+					} else: {
+						hashdiffs append: (0 - lastdiff)
+					}
 					newbucks <- #[]
 					while: { (newbucks length) < newsize } do: {
 						newbucks append: empty