On Sat, 25 Dec 2010 11:46:43 -0600 Andrei Alexandrescu <seewebsiteforem...@erdani.org> wrote:
> On 12/25/10 10:08 AM, bearophile wrote: > > Andrei: > > > >> What is a pure hash map? > > > > I meant that to implement the dict protocol in Python you just need to > > implement an equality and an __hash__ methods, because the collisions are > > not managed with a tree as in D. With pure hash map I meant that it doesn't > > contain trees and it doesn't need less-than comparisons. > > This behavior has been changed since a few releases ago to use > singly-linked lists for solving collisions. Did not know that. This change certainly simplifies implementation. Then, with a slight change, it would probably be possible to implement an ordered AA, like in Ruby: http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/. The change is to add a // series of 'next' pointers to keep inserton order (for iteration only). The cost in time is neglectable (and happens only at insertion time); the cost in space is one pointer per node. (I guess it was not possible in Python because their dict 'buckets' are not linked lists). denis -- -- -- -- -- -- -- vit esse estrany ☣ spir.wikidot.com
