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.
Cricket analogy: A scorecard read as a chain of overs works fine for narrating an innings in order, but a stadium's live scoreboard needs instant lookup of 'current score' without walking every prior ball — exactly the gap vectors and hash tables fill over lists.
Creating and Indexing Vectors
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.
Cricket analogy: A pre-printed squad sheet with 11 fixed numbered slots for batting order lets the scorer jump straight to 'slot 7' instantly, unlike scanning a ball-by-ball log — mirroring aref's constant-time indexed access versus nth's linear walk.
(setf v (make-array 5 :initial-element 0))
(setf (aref v 2) 99)
v ; => #(0 0 99 0 0)
;; adjustable vector with a fill pointer, useful as a growable stack
(setf av (make-array 0 :adjustable t :fill-pointer 0))
(vector-push-extend 'a av)
(vector-push-extend 'b av)
av ; => #(A B)Hash Tables: Constant-Time Lookup by Key
(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.
Cricket analogy: A player-to-jersey-number lookup table lets a stadium announcer instantly find '#18 → Virat Kohli' without scanning the full squad list, and using string names as keys requires content comparison, not just checking if it's literally the same string object — mirroring the eql versus equal distinction.
(setf scores (make-hash-table :test #'equal))
(setf (gethash "alice" scores) 95)
(setf (gethash "bob" scores) 88)
(gethash "alice" scores) ; => 95, T (value, present-p)
(gethash "carol" scores) ; => NIL, NIL (absent)
(maphash (lambda (k v) (format t "~a: ~a~%" k v)) scores)
(remhash "bob" scores)Using the default :test #'eql with string keys is a common bug: (setf (gethash "a" table) 1) followed by (gethash "a" table) can return NIL even though a key that looks identical was inserted, because two distinct string objects with the same content are not eql. Always specify :test #'equal (or #'equalp for case-insensitive string/number comparisons) when your keys are strings.
Choosing Between Lists, Vectors, and Hash Tables
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.
Cricket analogy: Building a running ball-by-ball commentary feed where you don't know the final over count in advance fits a list, but a fixed 11-player batting-order card fits a vector, and a player-name-to-career-stats lookup fits a hash table.
- Vectors offer O(1) indexed access via aref, backed by contiguous storage, unlike a list's O(n) walk.
- #(...) creates a vector literal; make-array creates a general array, of which vectors are the 1-D case.
- Adjustable vectors with a fill-pointer, built via vector-push-extend, act as growable arrays/stacks.
- Hash tables give O(1) amortized lookup by arbitrary key via gethash and (setf (gethash ...)).
- The :test keyword (eql, equal, equalp) controls key comparison; string keys require at least equal.
- gethash returns two values: the stored value and a boolean indicating whether the key was present.
- Choose lists for recursive/unbounded processing, vectors for indexed numeric access, hash tables for keyed lookup.
Practice what you learned
1. Why is (aref vector 5000) considered O(1) while (nth 5000 list) is O(n)?
2. What is the default :test used by make-hash-table if none is specified?
3. What does (gethash "missing-key" table) return when the key is not present?
4. Which scenario is the best fit for a hash table rather than a vector?
5. What does vector-push-extend do that plain vector-push cannot?
Was this page helpful?
You May Also Like
Lists and Cons Cells
How Lisp builds every list out of two-slot cons cells, and how car, cdr, and quoting let you construct and inspect them.
List Manipulation Functions
The core built-in functions for navigating, searching, combining, and transforming lists, and the crucial distinction between destructive and non-destructive operations.
Structs and CLOS Basics
How defstruct gives you fast, simple record types, and how CLOS's classes, generic functions, and methods build on that foundation for object-oriented design.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics