Author loewis
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Jim.Jewett, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.snow, fx5, georg.brandl, grahamd, gregory.p.smith, gvanrossum, gz, haypo, jcea, lemburg, loewis, mark.dickinson, merwok, neologix, pitrou, skorgu, skrah, terry.reedy, tim.peters, v+python, zbysz
Date 2012-01-27.21:02:34
SpamBayes Score 6.81853e-06
Marked as misclassified No
Message-id <20120127220233.Horde.-kL5FML8999PIxDp7fqjHtA@webmail.df.eu>
In-reply-to <1327695914.19.0.0339252748661.issue13703@psf.upfronthosting.co.za>
Content
> But then isn't it vulnerable to Frank's first attack as exposed in
> http://mail.python.org/pipermail/python-dev/2012-January/115726.html ?

It would be, yes. That's sad.

That could be fixed by indeed creating trees in all cases (i.e. moving
away from open addressing altogether). The memory consumption does not worry
me here; however, dictionary order will change in more cases.

Compatibility could be restored by introducing a threshold for
tree creation: if insertion visits more than N slots, go back to the
original slot and put a tree there. I'd expect that N could be small,
e.g. N==4. Lookup would then have to consider all AVL trees along the
chain of visited slots, but ISTM it could also stop after visiting N
slots.
History
Date User Action Args
2012-01-27 21:02:35loewissetrecipients: + loewis, lemburg, gvanrossum, tim.peters, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, haypo, christian.heimes, benjamin.peterson, merwok, grahamd, Arfrever, v+python, alex, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, Jim.Jewett, PaulMcMillan, fx5, skorgu
2012-01-27 21:02:34loewislinkissue13703 messages
2012-01-27 21:02:34loewiscreate