[erik_seaberg]

Lisp's development was skewed by the high cost of memory. Early on, scope was dynamic, lists were mutable and often spliced in-place, linear searches were typical (hash tables were almost unheard of), and there were very few first-class types because a pointer only had so many tag bits available.

[lispm]

Things evolved in the 70s. Hash tables were added over time, with some alternatives were using some tree like search. Usually the first thing was to make the symbol table not a list -> making the symbol table a hash table was reportedly done in 1971 by Jon L White. Tag bits then also were not a part of the pointers (with only very few exceptions), but a part of the data object (numbers, strings, arrays, symbols, ..).