Many sources say open-addressing, the hash collision handling approach used in llvm::StringMap, is not stable. Open-addressing is said to be inferior to chaining when the load factor is high (which is imaginable).
But if the load factor is low, there will be a huge memory waste for open-addressing, because I have to allocate Bucket_number * sizeof(Record) bytes in memory, even if the majority of buckets do not hold a record.
So my question is, what is the reason for LLVM to choose open-addressing over separate-chaining? Is it merely because of the advantage in speed gained by cache locality (records are stored in buckets themselves)?
Thanks:)
Edit: C++11 standard's requirements on std::unordered_setand std::unordered_map imply the chaining approach, not open-addressing. Why does LLVM choose an hash collision handling method that can't even satisfy the C++ standard? Are there any special use cases for llvm::StringMap that warrants this deviation? (Edit: this slide deck compares the performance of several LLVM data structures with that of STL counterparts)
Another question, by the way:
How does llvm::StringMap guarantee that keys' hash values are not recomputed when growing?
The manual says:
hash table growth does not recompute the hash values for strings already in the table.