It all depends on how many thousand entries are in your hash to begin with. If the number is reasonable and you don't do it too often, it just might be simplest and quickest (if slightly aromatic...) to just iterate through the hash sequentially. In other words, you might get away with it.

Otherwise, you're going to have to create a reverse-hash, and each slot in that reverse-hash can contain either a single value, or an array-reference containing a list of values.

The tradeoff, as usual, is the usual one: speed versus space. By building a reverse-hash you just at-least-doubled your storage requirement... but it's fast.

The “brute force search” may or may not be so-bad. If the hash is very large and virtual-storage is not, then the potential exists that walking through that hash is going to trigger a slew of page-faults every time, and that's really bad. But if storage is plentiful then it's all probably sitting in real-RAM anyway and you can just blip-through all that storage at CPU-speed. So basically it comes down to the practical likelihood of page-faults.