What is the relationship between a Lisp "association list" and a key-value mapping like Java's Map?

Question

I'm reading Land of Lisp (which is by the way, one of the best technical books I have ever read) and I have come across the "association list":

(defparameter *edges* 
  '((living-room (garden west door) 
                 (attic upstairs ladder))
    (garden (living-room east door)) 
    (attic (living-room downstairs ladder))))

Is an association list in Lisp the same concept of Java's Map (key-value binding)?

For living-room key, how it is possible to have more than one value? Why enclose the value with a list?

'(living-room
   ((garden west door)
    (attic upstairs ladder)))

Answer 1

1. Yes, the association list is one way to express key-value associations. Other structures Common Lisp provides to that end are property lists and hash tables.

2. The value is actually already contained in a list. An alist is fundamentally a list of pairs, where the car of each pair is the key, and the cdr is the value associated with that key. If you look up the key LIVING-ROOM with ASSOC and apply CDR to the result:

CL-USER> (cdr (assoc 'living-room *edges*))
((GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER))

The magic behind this lies in the fact that a pair whose car is living-room and whose cdr is a list of the two elements (garden west door) and (attic upstairs ladder) can also be viewed as the three-element list (living-room (garden west door) (attic upstairs ladder)), due to the way lists are constructed out of pairs.

Usually when representing alists as quoted objects, you see the elements depicted explicitly with dotted pairs, rather than punning with list notation, like so:

(defparameter *edges* 
  '((living-room . ((garden west door)
                    (attic upstairs ladder)))
    (garden . ((living-room east door))) 
    (attic . ((living-room downstairs ladder))) ))