A lexical cache comprises a collection of lexical containers, such as tuned hash table, that are organized according to the length of the keys to be looked up in the lexical cache. In one embodiment, the word is compressed to generate a key. Based on the length of the key and optionally a prefix, a hash table is identified from among the collection of hash tables. A hash value is computed for the key, and the hash table is searched for a slot holding a key value matching the key. If a slot having a key value matching the key was found, then the relative position of the key value within the corresponding sequence of slots is moved toward the beginning of the corresponding sequence.