in reply to Re: Better Hash Tables?
in thread Better Hash Tables?

Thanks for the links.

There's a lot going unsaid in that article (not surprised, we're not the intended audience).

From my further research, Perl resizes based on load factor, typically >75% (depends on the implementation). However, collisions are handled with a linked list, so in the worst case, a single bucket would hold all of the entries.

The article and paper talk about "open-addressing". An open-addressing hash table is a data structure that uses probing to resolve collisions when storing keys in a fixed-length array. It's also known as closed hashing. (Nothing like confusing terminology.)

Apparently, Python uses open-addressing with probing. The loading factor threshold for resizing is 2/3.

Since Perl uses linked lists to "resolve" collisions, this paper doesn't appear to apply.

There was this weird fact that popped up: Instead of just doubling, Python picks the next power of two to optimize performance. I mean, it doesn't start with a power-of-two size?

There was nothing in the article that helped me understand why the paper makes anything better, except hand-wavy declarations that it's true.

I also started to read the linked paper. Didn't get very far, didn't have the time to wade in and learn the terminology, and read the other papers.

-QM
--
Quantum Mechanics: The dreams stuff is made of