From 70890e6941a4bdbfd0067b60260b7307a874d38b Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Thu, 18 Jun 2015 22:03:25 -0700 Subject: Improvements in equal hashing function. * hash.c (equal_hash): For conses and vectors, ensure that distinct permutations lead to different hash codes. This is done by accumulating the partial hash with a multiplier, rather than just adding subhashes. --- hash.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'hash.c') diff --git a/hash.c b/hash.c index 1368376a..f4d4dff2 100644 --- a/hash.c +++ b/hash.c @@ -126,7 +126,8 @@ static cnum equal_hash(val obj) case LIT: return hash_c_str(litptr(obj)) & NUM_MAX; case CONS: - return (equal_hash(obj->c.car) + equal_hash(obj->c.cdr)) & NUM_MAX; + return (equal_hash(obj->c.car) + + 32 * (equal_hash(obj->c.cdr) & (NUM_MAX / 16))) & NUM_MAX; case STR: return hash_c_str(obj->st.str) & NUM_MAX; case CHR: @@ -151,13 +152,17 @@ static cnum equal_hash(val obj) cnum i, h = equal_hash(obj->v.vec[vec_length]); cnum len = c_num(length); - for (i = 0; i < len; i++) - h = (h + equal_hash(obj->v.vec[i])) & NUM_MAX; + for (i = 0; i < len; i++) { + h = 32 * (h & (NUM_MAX / 16)); + h += equal_hash(obj->v.vec[i]); + h &= NUM_MAX; + } return h; } case LCONS: - return (equal_hash(car(obj)) + equal_hash(cdr(obj))) & NUM_MAX; + return (equal_hash(car(obj)) + + 32 * (equal_hash(cdr(obj)) & (NUM_MAX / 16))) & NUM_MAX; case LSTR: lazy_str_force(obj); return equal_hash(obj->ls.prefix); -- cgit v1.2.3