Protobuf did not support maps for a long time. In practice using a list of key/value pairs works fine for most use cases. Sending the message over the wire is obviously always O(n); if you need fast inserts/lookups in code, then it usually makes sense to convert to and from the appropriate in-memory data structure for that purpose.
That said, I think maps are a fine feature for a serialization format to have. But, I haven't gotten around to adding them in Cap'n Proto because I have yet to hit a use case where I wasn't happy with a list of key/value pairs.
For what it's worth, I like them primarily because I don't mind using proto-generated objects as pieces passed around the stack (at least at higher levels of the stack). I lose consistency if I can do that for some objects, but am required to convert objects if they would need a mapping type.
It follows sorta the same reason that Clojure became a fairly widely used lisp – mapping types are extremely common in real world programs. Having them supported first class makes a lot of common tasks quicker to get through.
That said, I think maps are a fine feature for a serialization format to have. But, I haven't gotten around to adding them in Cap'n Proto because I have yet to hit a use case where I wasn't happy with a list of key/value pairs.