{"action":"created","issue":{"url":"https://api.github.com/repos/dart-lang/sdk/issues/7559","labels_url":"https://api.github.com/repos/dart-lang/sdk/issues/7559/labels{/name}","comments_url":"https://api.github.com/repos/dart-lang/sdk/issues/7559/comments","events_url":"https://api.github.com/repos/dart-lang/sdk/issues/7559/events","html_url":"https://github.com/dart-lang/sdk/issues/7559","id":84524450,"number":7559,"title":"ImmutableMap should not take O(N) to do a lookup","user":{"login":"jmesserly","id":1081711,"avatar_url":"https://avatars.githubusercontent.com/u/1081711?v=3","gravatar_id":"","url":"https://api.github.com/users/jmesserly","html_url":"https://github.com/jmesserly","followers_url":"https://api.github.com/users/jmesserly/followers","following_url":"https://api.github.com/users/jmesserly/following{/other_user}","gists_url":"https://api.github.com/users/jmesserly/gists{/gist_id}","starred_url":"https://api.github.com/users/jmesserly/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmesserly/subscriptions","organizations_url":"https://api.github.com/users/jmesserly/orgs","repos_url":"https://api.github.com/users/jmesserly/repos","events_url":"https://api.github.com/users/jmesserly/events{/privacy}","received_events_url":"https://api.github.com/users/jmesserly/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dart-lang/sdk/labels/area-vm","name":"area-vm","color":"c7def8"},{"url":"https://api.github.com/repos/dart-lang/sdk/labels/Type-Defect","name":"Type-Defect","color":"ededed"}],"state":"closed","locked":false,"assignee":{"login":"mhausner","id":8368434,"avatar_url":"https://avatars.githubusercontent.com/u/8368434?v=3","gravatar_id":"","url":"https://api.github.com/users/mhausner","html_url":"https://github.com/mhausner","followers_url":"https://api.github.com/users/mhausner/followers","following_url":"https://api.github.com/users/mhausner/following{/other_user}","gists_url":"https://api.github.com/users/mhausner/gists{/gist_id}","starred_url":"https://api.github.com/users/mhausner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mhausner/subscriptions","organizations_url":"https://api.github.com/users/mhausner/orgs","repos_url":"https://api.github.com/users/mhausner/repos","events_url":"https://api.github.com/users/mhausner/events{/privacy}","received_events_url":"https://api.github.com/users/mhausner/received_events","type":"User","site_admin":false},"milestone":null,"comments":6,"created_at":"2012-12-21T03:54:34Z","updated_at":"2016-01-25T23:36:20Z","closed_at":"2016-01-22T23:13:33Z","body":"See the code:\n\n&nbsp;&nbsp;V operator [\\](K key) {\n&nbsp;&nbsp;&nbsp;&nbsp;// TODO(hausner): Since the keys are sorted, we could do a binary\n&nbsp;&nbsp;&nbsp;&nbsp;// search. But is it worth it?\n&nbsp;&nbsp;&nbsp;&nbsp;for (int i = 0; i &lt; kvPairs_.length - 1; i += 2) {\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (key == kvPairs_[i]) {\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return kvPairs_[i+1];\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;return null;\n&nbsp;&nbsp;}\n\nO(N) lookup means you are better off not making const Maps, which is completely counter to the design of const."},"comment":{"url":"https://api.github.com/repos/dart-lang/sdk/issues/comments/174730588","html_url":"https://github.com/dart-lang/sdk/issues/7559#issuecomment-174730588","issue_url":"https://api.github.com/repos/dart-lang/sdk/issues/7559","id":174730588,"user":{"login":"jmesserly","id":1081711,"avatar_url":"https://avatars.githubusercontent.com/u/1081711?v=3","gravatar_id":"","url":"https://api.github.com/users/jmesserly","html_url":"https://github.com/jmesserly","followers_url":"https://api.github.com/users/jmesserly/followers","following_url":"https://api.github.com/users/jmesserly/following{/other_user}","gists_url":"https://api.github.com/users/jmesserly/gists{/gist_id}","starred_url":"https://api.github.com/users/jmesserly/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmesserly/subscriptions","organizations_url":"https://api.github.com/users/jmesserly/orgs","repos_url":"https://api.github.com/users/jmesserly/repos","events_url":"https://api.github.com/users/jmesserly/events{/privacy}","received_events_url":"https://api.github.com/users/jmesserly/received_events","type":"User","site_admin":false},"created_at":"2016-01-25T23:36:20Z","updated_at":"2016-01-25T23:36:20Z","body":"Yeah, the bug was more about the fact that key lookup is O(N), not the particular approach described in the TODO. O(N) doesn't match expectations about how Map lookup should work. The workaround is to avoid const maps and/or keep them small."}}