<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 21, 2016, at 1:02 PM, David Turnbull <<a href="mailto:dturnbull@gmail.com" class="">dturnbull@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Alegreya-Regular; font-size: 15px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">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.<br class=""></div></div></blockquote></div><br class=""><div class="">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.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">—Jens</div></body></html>