|
|
Log in / Subscribe / Register

A generic hash table

A generic hash table

Posted Aug 10, 2012 2:17 UTC (Fri) by nybble41 (subscriber, #55106)
In reply to: A generic hash table by nix
Parent article: A generic hash table

> Downside: you still do need to resize now and then, which is hateful because it breaks active iterators unless you have crazy complexity to deal with that case alone.

Even without resizing, keys can change location when other items are inserted, so you can't make very many guarantees. Even with a normal hash table it's difficult to say whether you will see the inserted key later on; with a cuckoo hash table you may miss _other_ keys, or even double-iterate them.

If you must modify a hash table with active iterators, perhaps you should collect the list of keys up front, atomically, and iterate over that instead. It may not be quite as efficient as iterating over the hash table directly, in memory or CPU time, but the result will be much more predictable. Or you could make a shallow copy of the hash table to iterate over.


The LWN site is currently under high scraper load, so comment display has been suppressed for anonymous users. If you are a human, you may read the comments by clicking the button below:

Note: you can avoid this step in the future by logging into your LWN account.


Copyright © 2026, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds