Hash table rehashing and iterator invalidation

user_3169754 0
Viewed 578

What techniques are known to prevent iterator invalidation after/during rehashing? In particular, I'm interested in collision-chaining hash tables with incremental rehashing.

Suppose we're iterating a hash table via an iterator, insert an element during the iteration, and that insertion causes full or partial table rehash. I'm looking for hash table variants which allow to continue iteration and be sure that all elements are visited (except the newly inserted one maybe, it doesn't matter) and no element is visited twice.

AFAIK C++ unordered_map invalidates iterators during rehash. Also, AFAIK Go's map has incremental rehashing and doesn't invalidate iterators (range loop state), so it's likely what I'm looking for, but I can't fully understand the source code so far.

One possible solution is to have a doubly-linked list of all elements, parallel to the hash table, which is not affected by rehashing. This solution requires two extra pointers per element. I feel that better solutions should exist.

go hashmap data-structures hashtable algorithm
1 Answers

AFAIK C++ unordered_map invalidates iterators during rehash.

Correct. cppreference.com summarises unordered_map iterator invalidation thus:

Operations                                     Invalidated
==========                                     ===========
All read only operations, swap, std::swap      Never
clear, rehash, reserve, operator=              Always
insert, emplace, emplace_hint, operator[]      Only if causes rehash
erase                                          Only to the element erased

If you want to use unordered_map, your options are:

  • call reserve() before you start your iteration/insertions, to avoid rehashing
  • change max_load_factor() before you start your iterations/insertions, to avoid rehashing
  • store the elements to be inserted in say a vector during the iteration, then move them into the unordered_map afterwards
  • create e.g. vector<T*> or vector<reference_wrapper<T>> to the elements, iterate over it instead of the unordered_map, but still do your insertions into the unordered_map

If you really want incremental rehashing, you could write a class that wraps two unordered_maps, and when you see an insertion that would cause a rehash of the first map, you start inserting into the second (for which you'd reserve twice the size of the first map). You could manually control when all the elements from the first map were shifted to the second, or have it happen as a side effect of some other operation (e.g. migrate one element each time a new element is inserted). This wrapping approach will be much easier than writing an incremental rehashing table from scratch.

user_4107670
Related