I should note here that specialised hash-tables in pointer-set.c have a
load-factor of at most 25%. Also another very fast hash table I've
studied, dense_hash_map from google's sparse_hash_table, has a load factor
of 50% max.
As I understand it a good hash function gives a perfectly random value up
to N. So if we have only 25% of slots empty, like we do with today's 75%
load factor, chances we won't have collision are small. And collisions
cost more for an open-addressing hash table.
But for implementing a closed-addressing hash-table with linked lists for
collision resolution, we'd need allocator pools within libiberty. Is it
OK to move alloc-pool.[ch] into libiberty as a first step?
Dimitris