7 Hash Tables

A hash table is a very fast kind of lookup table, somewhat like an alist (see Association Lists) in that it maps keys to corresponding values. It differs from an alist in these ways:

• Lookup in a hash table is extremely fast for large tables—in fact, the time required is essentially independent of how many elements are stored in the table. For smaller tables (a few tens of elements) alists may still be faster because hash tables have a more-or-less constant overhead.
• The correspondences in a hash table are in no particular order.
• There is no way to share structure between two hash tables, the way two alists can share a common tail.

Emacs Lisp provides a general-purpose hash table data type, along with a series of functions for operating on them. Hash tables have no read syntax, and print in hash notation, like this:

     (make-hash-table)
          => #<hash-table 'eql nil 0/65 0x83af980>

(The term “hash notation” refers to the initial `#' character—see Printed Representation—and has nothing to do with the term “hash table.”)

Obarrays are also a kind of hash table, but they are a different type of object and are used only for recording interned symbols (see Creating Symbols).

• Creating Hash: Functions to create hash tables.
• Hash Access: Reading and writing the hash table contents.
• Defining Hash: Defining new comparison methods
• Other Hash: Miscellaneous.