FAQ: Lisp Frequently Asked Questions 2/7 [Monthly posting] (2024)

Both association lists (alists) and hash tables may be used torepresent tabular data. Hash tables have an O(1) running time andalists an O(n) running time, so hash tables are ultimately moreefficient than alists. However, if the alists are small, they can bemore efficient than hash tables, which have a large initial overhead.Alists can sometimes be more efficient if the keys are sortedaccording to frequency, with the most heavily accessed keys appearingat the front of the list. But one doesn't always know this kind ofinformation, and even then the frequency distribution may be flat.In Allegro CL 4.1 [SPARC; R1], the rule of thumb is that for less than24 elements, linear search using alists beats hashing. In Lucid CL4.0.1 HP 9000/700, the break-even point is at 10 elements. Thebreak-even points vary in other lisps from as low as 4 elements to ashigh as 100 elements. So if you're using alists in your code, using hash tables instead may speed up your program. A potential problem may occur, however, when the keys of an EQ or EQLhash table are Lisp objects such as conses or arrays (or other objectsthat are identified by their addresses). In most implementations, suchtables must be re-hashed after garbage collection. If your applicationcauses frequent GCs, this can adversely affect the performance of hashtable lookup. Since EQL-hashing and =-hashing of fixnums generallydon't require rehashing after GC, one way of avoiding this problem isto include a unique identifier in each key object and hash on thatinstead. Another solution is to use an EQUAL hash table if the keysare conses or an EQUALP hash table if the keys are arrays or other(non-circular!) structures.