Use a Trie instead of a HashMap as cache

[iggedi-ig-ig]

Using a Trie instead of a hash map would significantly reduce memory and probably not be slower.
radix_trie implements such a Trie already, though seriailzation for storing the cache would probably have to be done differently.