Oh wow, that's a super simple solution, and I can immediately see how this gets you the best of both worlds!

And since it's only used for speedy lookup we can even use a fast, cheap and non-secure hashing algorithm, so it's really a low-cost operation!

Thanks! This was really one of those aha-moments where I feel kinda stupid to not have thought of it myself!