On Sat, Apr 10, 2010 at 2:57 PM, "Martin v. Löwis" <mar...@v.loewis.de> wrote: >> Any other advice would also be helpful. > > I may be missing the point, but ISTM that the assumption of this > approach is that there are often collisions in the hash table. I think > that assumption is false; at least, I recommend to validate that > assumption before proceeding.
It's just an experiment for a class, not something I am (yet) seriously thinking about contributing back to CPython. I think my chances of improving over the current implementation are slim. I do not have that much hubris. :) I would just rather do experimental rather than theoretical work with data structures. I think you're right about the number of collisions, though. CPython dicts use a pretty low load factor (2/3) to keep collision counts down. One of the major benefits cited in the paper is the ability to maintain performance in the face of higher load factors, so I may be able to bump up the load factor to save memory. This would increase collisions, but then that wouldn't matter, because resolving them would only require looking within two consecutive cache lines. > There are, of course, cases where dicts do show collisions (namely when > all keys hash equal), however, I'm uncertain whether the approach would > help in that case. Yes, in fact, hopscotch hashing fails completely as I mentioned at the end of my last message. Reid _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com