Vectors and Hash Tables in LISP

Lists are elegant for recursive, sequential processing, but their O(n) positional access becomes a real cost once you need to repeatedly look up arbitrary elements by index or key. Common Lisp provides two data structures purpose-built for that: vectors, which offer constant-time indexed access backed by contiguous memory, and hash tables, which offer constant-time (amortized) lookup by arbitrary key rather than by position at all.

A vector literal is written #(1 2 3), and (make-array 5 :initial-element 0) creates a general-purpose array of length 5 (make-array is the more general constructor; vectors are simply one-dimensional arrays). Elements are accessed with (aref vector index), zero-indexed just like nth, but in true constant time since the underlying storage is contiguous rather than a chain of separately allocated cons cells. Unlike lists, a vector's length is typically fixed at creation unless you explicitly request an adjustable one, and (setf (aref v 2) 99) mutates the vector directly in place — vectors are inherently a mutable, indexed structure in a way plain lists are not.

(make-hash-table :test #'equal) creates an empty hash table, with the :test keyword specifying how keys are compared — eql is the default (fine for numbers and symbols), but equal is required for string keys, since eql compares strings by identity, not content. (gethash key table) retrieves the associated value, returning nil (plus a second boolean value indicating presence, useful for distinguishing 'key maps to nil' from 'key absent') and (setf (gethash key table) value) both inserts and updates. remhash deletes an entry, and maphash iterates over every key-value pair in an unspecified order.

Use a list when you're building or consuming data recursively, don't know the size up front, or need cheap insertion/removal at the front — the whole recursive, functional style of Lisp assumes lists. Use a vector when you know the size (or can bound it) and need fast random-access reads or writes by numeric position, especially in numerically heavy or performance-sensitive code. Use a hash table when lookups are naturally keyed by something other than position — names, symbols, or composite keys — and you need that lookup to stay fast regardless of how large the collection grows.