Reasons for not using open addressing in uthash

[Vijay Iyengar]

More of a theoretical question, why not use something like quadratic probing or robin-hood for collision resolution? As far as I understand, there's no need to maintain linked lists and these implementations support higher load factors (90+% for robin hood hashing).

[Arthur O'Dwyer]

On Tue, Jul 25, 2017 at 4:18 PM, Vijay Iyengar <vijay.iy...@gmail.com> wrote:

More of a theoretical question, why not use something like quadratic probing or robin-hood for collision resolution? As far as I understand, there's no need to maintain linked lists and these implementations support higher load factors (90+% for robin hood hashing).

Theoretical answer: I've heard good things about open addressing. (I've read a very convincing blog post on Robin Hood hashing, and then heard anecdotally that straightforward linear probing beats it in practice anyway as long as you have a good hash function such as CityHash and don't let your load factor get too high.) So if the hash-table operations are a bottleneck for your application, you should probably look into that kind of stuff. I've actually got a (completely warranty-free) Robin Hood implementation over here myself.

Practical answer: uthash focuses on Not Breaking Things, with a side of Ease Of Use. The former means that there's literally no way to "transition" from the current well-documented chained approach to a different design. (Consider: what would happen to all the macros that take an "hh" parameter? what would happen to all the client code that used those macros?)  The latter means that uthash still has a reasonably good claim to relevance — if you're doing C code and need a hash table that won't cause you problems down the road, uthash is a good option. (If uthash had no reasonable claim to relevance, we could just abandon it and tell people to use "the competition". But I don't think there is very much competition, in C.)

So there you are.

HTH,

Arthur