I think you're underestimating the number of memory redirections that are necessary for chaining. It's more than one. That's the killer. It's important to be w

I think you're underestimating the number of memory redirections that are necessary for chaining. It's more than one. That's the killer. It's important to be wary of assuming your data will be in cache. It usually isn't. The problem isn't making lots of high density searches in a hash map, the problem is making a search every now and then. A hash map that makes three DRAM accesses will always be worse that one that makes one, regardless of how much work it needs to do, and this is for two reasons. First is there obvious: RAM is slow as balls, we get it. Second is more insidious. You just evicted two cache lines. It's not just the lookup itself that's slower, you also made the consumer of your data structure slower. Here's a look at what open addressing looks like these days: https://youtu.be/ncHmEUmJZf4 https://youtu.be/ncHmEUmJZf4 (warning, it's an hour. Takes a while to build up, too. Still worth it.)