<map> was introduced in HTML 3.2 in 1997. The other technique I often saw was to cut the image into a grid of separate image files. They would look to the user as if they were a single image, but you could hyperlink some of the images so the effect was that parts of the overall image were hyperlinked and some weren't. Developers came up with all kinds of interesting tricks in those days!
My first websites were built like this. I'd design PSDs and then slice them into images that I'd place in tables. I completely forgot about that approach!
