Я написал это, пытаясь решить ту же проблему:
https://github.com/robtandy/randomdict
Он имеет O (1 ) произвольный доступ к ключам, значениям и элементам.