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

[Jens Alfke]

> On Jan 21, 2016, at 1:02 PM, David Turnbull <dturnbull at gmail.com> wrote:
> 
> Only the lookup by index is O(1). Lookup by key is not specified. You can't O(1) by key without a perfect hash function.

Hash tables are generally considered O(1) even without perfect hashing. If the table grows sufficiently as items are added, so that there are few collisions, it will almost always take 1 probe to find a value. If it sometimes takes 2 or 3 or more, that just raises the average a little, and an average of (say) 1.053 probes is still O(1) because it doesn’t increase as the data set grows.

My point earlier was that the built-in Dictionary class is not the only possible class with associative-array semantics, and other implementations of associative arrays can have very different performance characteristics.

—Jens
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20160121/5990450c/attachment.html>