Messages in this thread | | | From | Nick Piggin <> | Subject | Re: [patch][rfc] ddds: "dynamic dynamic data structure" algorithm, for adaptive dcache hash table sizing (resend) | Date | Wed, 8 Oct 2008 03:39:39 +1100 |
| |
On Wednesday 08 October 2008 02:37, Mikael Pettersson wrote:
> I missed the first post, but loooking at the patch it seems > somewhat complex.
It is complex, but relatively self-contained, ie. it doesn't affect the actual code that performs hash lookups very much (although there can be some impact on atomicity if we have to consider something like a full table traversal like the rt hash).
> How does this relate to traditional incremental hash tables > like extensible hashing or linear hashing (not to be confused > with linear probing)? In linear hashing a resize only affects > a single collision chain at a time, and reads from other chains > than the one being resized are unaffected.
I haven't actually seen any real implementations of those things. AFAICS they don't exactly deal with concurrency. They are also likely to be more costly to operate on, versus a well sized simple hash table.
| |