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

[Dave Abrahams]

on Thu Jan 21 2016, David Turnbull <dturnbull-AT-gmail.com> wrote:

> The documentation is correct. Thinking about key lookups as O(1) is what
> led to this problem...
> http://www.ocert.org/advisories/ocert-2011-003.html

Sorry, no, the documentation isn't correct, in that it doesn't reflect
our intention.  It should say that Dictionary lookups are amortized O(1)
when the dictionary isn't backed by an NSDictionary, subject to the
quality of the hash function (which as we all know, is a big caveat).

>
> -david
>
> On Thu, Jan 21, 2016 at 1:36 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>
>>
>> on Thu Jan 21 2016, David Turnbull <dturnbull-AT-gmail.com> wrote:
>>
>> > On Thu, Jan 21, 2016 at 12:23 PM, Dave Abrahams via swift-users <
>> > swift-users at swift.org> wrote:
>> >
>> >> Swift Dictionaries are documented as having O(1) lookup.
>> >>
>> >
>> > Only the lookup by index is O(1). Lookup by key is not specified.
>>
>> Then that's a bug in our documentation; please file a ticket!  It should
>> guarantee O(1) as long as the Dictionary isn't backed by NSDictionary
>> and the hash function is good.
>>
>>