Re: Looking things up by string prefix
On Sun, 4 Jul 2010, Andreas Leitgeb wrote:
Tom Anderson <twic@urchin.earth.li> wrote:
I want to store some things, each filed under a string key. I then want to
look those things up with other strings, finding the thing whose key is
the longest available prefix of the lookup string.
So, if i store:
/products -> foo
/products/fruit -> bar
Then lookups go like:
/products/furniture/chairs -> foo
/products/fruit/bananas -> bar
My approach would be, to partition the keys by length, first,
and for each length maintain a separate HashMap.
The structure to hold the key-thing pairs:
ArrayList<HashMap<String,Thing>>
To add a pair: put it into the hashmap indexed by key.length()
in the ArrayList (extending the ArrayList and creating a new
HashMap as necessary)
To lookup a string:
reverse-iterate the ArrayList from .size()-1 downto 1: for each
index i that has a non-empty HashMap stored in the ArrayList,
obtain lookupString.substring(0,i) and look it up in that
non-empty HashMap stored at i.
Interesting, thanks. That would certainly work. At first glance, it seems
a bit clunky, but you only need to to do lookups for the lengths that have
keys, and each one is a hashtable lookup, so it should be quite quick.
For large sets of keys, or rather for sets of keys with many different
lengths, i suspect it wouldn't be very fast, but my key set is likely to
be quite small.
tom
--
Get a fucking hobby that isn't breathing, browsing 4chan, or fapping. --
The Well Cultured Anonymous, on Manners