You should check out Dan Schmidt's article Building a Better Hash. He is trying to solve exactly the same problem. He comes up with a Perl module that implements a data structure with fast indexed access for search, insert, and delete (like a hash) but also fast random key selection.