On 2012-04-08, at 23:21 , Niko Matsakis wrote: > On 4/8/12 12:15 PM, Stefan Plantikow wrote: >> Hi, >> >> I was thinking about this, too. One of the state-of-the art algorithms seems >> to be hopscotch hashing, wikipedia has a quite good introduction to it. >> Even though it has been developed for concurrent access, it should also be >> quite good in a single core scenario and has a really low memory footprint >> (90% full hash table still works reasonably). I was thinking about >> implementing that for fun once the currently ongoing changes to regions and >> vectors are complete. > > I am totally excited about offering a variety of map abstractions. One > additional thing I would particularly like (which is kind of orthogonal) is a > default map implementation that begins as a straight-up list of some fixed > size and then shifts to another algorithm as the table is populated. Of > course we'd want to test and tune to see where it makes sense to shift, but I > believe that a lot of hash tables are generally small (but not always) and > thus can benefit from changing strategies as they fill up. In fact I would > like to have a similar approach to each of the basic container types (a > default implementation that adjusts and does the right thing, plus a variety > of more specific implementations).
Cocoa has a lot of that kind of things, if somebody wants to do it. _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
