3 ms·

> The reason open addressing is considered open is that it frees us from the hash table. The table entries themselves are not stored directly in the bins anymor

by jlas 10y ago

> The reason open addressing is considered open is that it frees us from the hash table. The table entries themselves are not stored directly in the bins anymore, as with a closed addressing hash table, but rather in a separate entries array, ordered by insertion. > Open addressing uses the bins array to map keys to their index in the entries array. Am I wrong or is this generally not true? Open addressing is about storing the entries directly in the bins [1]. The new implementation is still open addressing, sure, but the bins contain an index to a separate entries array, presumably to keep the size of the bins array compact. [1] https://en.wikipedia.org/wiki/Hash_table#Open_addressing https://en.wikipedia.org/wiki/Hash_table#Open_addressing

masklinn 10y ago
> Am I wrong or is this generally not true? Open addressing is about storing the entries directly in the bins. Correct. > The new implementation is still open addressing, sure, but the bins contain an index to a separate entries array, presumably to keep the size of the bins array compact. Yes, the original proposal for CPython[0] also noted improvements in iteration speed since the iterator doesn't keep branching on the empty/full cells of the sparse array (it can just go through the dense one which is mostly or entirely full depending on implementation), and improvements to resizing performances. Plus it also allows further gains e.g. pypy switches the size of the values in the sparse array depending on dict size (so under 256 (actual items) the sparse array will be 1 byte/item, then 2 bytes until 2^16, etc…)[1]. And it has the advantage of being naturally ordered (that is entries will be iterated in original insertion order) at no additional cost (modulo how removals are implemented) whereas in older systems you'd need an additional doubly-linked list for that, IIRC that was the case for both PHP and Ruby (the base Python dict didn't conserve or guarantee ordering). [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... [1] https://morepypy.blogspot.fr/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.fr/2015/01/faster-more-memory-effi...

by jlas 10y ago

masklinn 10y ago

> Am I wrong or is this generally not true? Open addressing is about storing the entries directly in the bins. Correct. > The new implementation is still open addressing, sure, but the bins contain an index to a separate entries array, presumably to keep the size of the bins array compact. Yes, the original proposal for CPython[0] also noted improvements in iteration speed since the iterator doesn't keep branching on the empty/full cells of the sparse array (it can just go through the dense one which is mostly or entirely full depending on implementation), and improvements to resizing performances. Plus it also allows further gains e.g. pypy switches the size of the values in the sparse array depending on dict size (so under 256 (actual items) the sparse array will be 1 byte/item, then 2 bytes until 2^16, etc…)[1]. And it has the advantage of being naturally ordered (that is entries will be iterated in original insertion order) at no additional cost (modulo how removals are implemented) whereas in older systems you'd need an additional doubly-linked list for that, IIRC that was the case for both PHP and Ruby (the base Python dict didn't conserve or guarantee ordering). [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... [1] https://morepypy.blogspot.fr/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.fr/2015/01/faster-more-memory-effi...