Performing a hashtable lookup for the queries with the wildcard special token in the current position could be made more efficient. If there is a pointer that points to the next setitem or exactitem for queries with a wildcard in the current position, and is NULL otherwise, following wildcards would perform more like a linked list than a hashtable lookup.
The cleanest solution I can think of is wrapping each hashtable pointer in a struct that contains a wild pointer in addition to the hashlib pointer.
This will probably be only a small net change in memory requirements, as every hashtable will now contain an extra pointer, but many will contain one fewer entries.