[swift-users] array.first vs. array[0]

[Dave Abrahams]

on Wed Jan 20 2016, Jens Alfke <jens-AT-mooseyard.com> wrote:

>> On Jan 20, 2016, at 12:28 PM, Dave Abrahams via swift-users <swift-users at swift.org> wrote:
>> 
>>> "But what about dictionaries?" Ah, but a dictionary key is not an
>>> Index (note the capital). The relation between a Collection and an
>>> Index is that there must be a constant-time operation to get to a
>>> value from an Index. 
>> 
>> Well, but that also applies to dictionary keys. 
>
> Not necessarily. It does if the dictionary is based on a
> [well-implemented] hash table. But if it’s implemented as a search
> tree (as C++’s std::map is), it’s not — lookup time is O(log n).

Swift Dictionaries are documented as having O(1) lookup.