Maps have actually two representations depending on the size. Small maps (less than 32 keys) are represented as two sorted arrays - one for keys and one for values. Accessing a key in such a map involves a linear search (and a linear search is much faster than a binary search since the size is so small). Depending on how you look at it, you might say that’s O(n) since it depends on the map size, or O(1) since the worst case is O(32), which is O(1) - the big O notation is not very helpful when talking about small data structures, especially with cache locality and branch prediction effects, you can get significantly different results from what you’d expect by a simple complexity analysis.
Large maps are represented as HAMT and the access is O(log n) - the “forking” factor of the maps is 32, so even very big maps are rather shallow and rarely involve more than 3 levels (32k items).
Anyway, maps are superior to me because of one simple thing - I can read them. Records are terrible in that regard - you get a tagged tuple and you have no idea what the fields mean. Debugging with records is a significantly worse experience and takes much longer. I would reach for records in the tightest loops of the program, where I need some “lolspeed”, but for everything else, maps and structs are plenty fast.
