Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

FAQ: Lisp Frequently Asked Questions 2/7 [Monthly posting]
Section - [2-2] When should I use a hash table instead of an association list?

( Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Part7 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Business Photos and Profiles ]


Top Document: FAQ: Lisp Frequently Asked Questions 2/7 [Monthly posting]
Previous Document: [2-1] Is there a GNU-Emacs interface to Lisp?
Next Document: [2-3] What is the equivalent of EXPLODE and IMPLODE in Common Lisp?
See reader questions & answers on this topic! - Help others by sharing your knowledge

Both association lists (alists) and hash tables may be used to
represent tabular data. Hash tables have an O(1) running time and
alists an O(n) running time, so hash tables are ultimately more
efficient than alists. However, if the alists are small, they can be
more efficient than hash tables, which have a large initial overhead.

Alists can sometimes be more efficient if the keys are sorted
according to frequency, with the most heavily accessed keys appearing
at the front of the list. But one doesn't always know this kind of
information, and even then the frequency distribution may be flat.

In Allegro CL 4.1 [SPARC; R1], the rule of thumb is that for less than
24 elements, linear search using alists beats hashing.  In Lucid CL
4.0.1 HP 9000/700, the break-even point is at 10 elements. The
break-even points vary in other lisps from as low as 4 elements to as
high 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 EQL
hash table are Lisp objects such as conses or arrays (or other objects
that are identified by their addresses). In most implementations, such
tables must be re-hashed after garbage collection. If your application
causes frequent GCs, this can adversely affect the performance of hash
table lookup. Since EQL-hashing and =-hashing of fixnums generally
don't require rehashing after GC, one way of avoiding this problem is
to include a unique identifier in each key object and hash on that
instead. Another solution is to use an EQUAL hash table if the keys
are conses or an EQUALP hash table if the keys are arrays or other
(non-circular!) structures.

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA




Top Document: FAQ: Lisp Frequently Asked Questions 2/7 [Monthly posting]
Previous Document: [2-1] Is there a GNU-Emacs interface to Lisp?
Next Document: [2-3] What is the equivalent of EXPLODE and IMPLODE in Common Lisp?

Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Part7 - Single Page

[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
ai+lisp-faq@cs.cmu.edu





Last Update March 27 2014 @ 02:11 PM