Possibility? of infinite loop in MultinameHashtable::get

Haghighat, Mohammad R mohammad.r.haghighat at intel.com
Mon Jan 14 22:02:19 PST 2008


Cool! This property doesn't hold for all instances of quadratic probing,
as stated here: 
http://cs.nyu.edu/courses/fall07/V22.0102-002/lectures/hashing-102-fa07.
ppt#307,33,Slide%2033
More specifically, the plain h(k,i) = (h(k)+i^2) mod n results in the
repetition of digits 0, 1, 4, 9 in some order. 

However, when n is a power of 2 and the right coefficients are used, as
is the case in Tamarin: h(k,i) = (h(k)+ i(i+1)/2) mod n, the generated
numbers are distinct in the sequence. The proof is at the very bottom of
http://en.wikipedia.org/wiki/Quadratic_probing

Thanks,
- moh 

-----Original Message-----
From: Thomas Reilly [mailto:treilly at adobe.com] 
Sent: Monday, January 14, 2008 5:10 PM
To: Haghighat, Mohammad R; tamarin-devel at mozilla.org
Subject: RE: Possibility? of infinite loop in MultinameHashtable::get


There's a proof out there somewhere that a power of 2 hashtable w/
quadratic probe with the right constants hits every slot in the table
before repeating.  Thus no infinite loop if the table isn't full.

> -----Original Message-----
> From: tamarin-devel-bounces at mozilla.org 
> [mailto:tamarin-devel-bounces at mozilla.org] On Behalf Of 
> Haghighat, Mohammad R
> Sent: Monday, January 14, 2008 5:00 PM
> To: tamarin-devel at mozilla.org
> Subject: Possibility? of infinite loop in MultinameHashtable::get
> 
> 
> I've been looking at optimizing the "get" method of 
> MultinameHashtable, which is often the hottest VM function. 
> It seems that its implementation is at risk of infinite loop 
> not only at insertion time but also during lookups. For 
> lookups, when a match is found the method doesn't return the 
> match before it inspects all the possible collisions until it 
> finds an empty slot. This is done to check if there's an 
> ambiguous binding.
> Even if the occupancy of the table is below the load factor, 
> it is conceivable that all cells in the collision chain might 
> be occupied. In such a case, the get method will not 
> terminate. This is more probable with small tables. A remedy 
> could be to rehash the table upon the first revisit of the 
> first cell. 
> 
> - moh
> _______________________________________________
> Tamarin-devel mailing list
> Tamarin-devel at mozilla.org
> https://mail.mozilla.org/listinfo/tamarin-devel
> 


More information about the Tamarin-devel mailing list