On Mon, Aug 22, 2011 at 1:37 PM, Dimitrios Apostolou <ji...@gmx.net> wrote: > 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?
Well, what would be the constant overhead for a closed-addressing hash if it is empty and per element (per collision)? Decreasing the load factor might be a better choice ... Richard. > > Dimitris > > >
