Python hash table for fuzzy matching

Question

I am trying to implement a data structure which allows rapid look-ups based on keys.

The python dict is great when my look-ups involve an equality
(e.g. key == somevalue translates to datadict[somevalue].

The problem is that I also need to be able to efficiently look up keys based on a more complex comparison, e.g. key > 50, or key.startswith('abc').

Obviously I can't use the same solution in both cases, but at the moment I can't figure out how to solve either case. Can anyone suggest a way of doing this?

Answer 1

It doesn't sound like you want a hash algorithm - instead some form of binary tree. Or even a list which you use the bisect module with. It'd be worth looking at: Python's standard library - is there a module for balanced binary tree?

Another option (depending on your data), would be to use use an in-memory sqlite3 database and create appropriate indices for possible lookups -- but you'll trade performance/memory and SQL syntax for flexibility...