Some areas that I explored more deeply in my Earlier Days w.r.t hash tables (Java hash tables, at that) that aren't covered by the analysis are:
* Memory footprint and GC load
* Write performance (especially characterizing fast-path vs. rebalance times)
* Loading vs. performance tradeoffs (can the table perform well with 80% occupancy? 99%?)
* Small-table utilization.
If some of the implementations consume substantially less memory and/or GC churn while having largely indistinguishable lookup performance, then they're a win for value. This is one place that open addressing can win.
For the libraries we were writing, we didn't know if consumers would be stuffing in one element (the most common case) or millions of elements (uncommon but important), so we ended up implementing a clever abstraction that would start with a pointer to the single object, then replace it with a hash table when the second element was added. Since we used hash tables like country doctors prescribe aspirin, it reduced the heap footprint of the server by ~30%. Of course, Hansen's Law states "Clever is the opposite of maintainable," and that definitely applied here.
* Memory footprint and GC load
* Write performance (especially characterizing fast-path vs. rebalance times)
* Loading vs. performance tradeoffs (can the table perform well with 80% occupancy? 99%?)
* Small-table utilization.
If some of the implementations consume substantially less memory and/or GC churn while having largely indistinguishable lookup performance, then they're a win for value. This is one place that open addressing can win.
For the libraries we were writing, we didn't know if consumers would be stuffing in one element (the most common case) or millions of elements (uncommon but important), so we ended up implementing a clever abstraction that would start with a pointer to the single object, then replace it with a hash table when the second element was added. Since we used hash tables like country doctors prescribe aspirin, it reduced the heap footprint of the server by ~30%. Of course, Hansen's Law states "Clever is the opposite of maintainable," and that definitely applied here.