HabrПоиск в коллекциях или когда O(N) быстрее O(1)
На собеседованиях мы слышим или говорим сами, что поиск в массиве медленнее, чем в хеш-таблице. Кто-то даже вспоминает, что поиск в массиве имеет линейную сложность или O(n), а в хеш-таблице — константную O(1). Но работает ли это на практике? Что, если есть ситуации, когда поиск в массиве оказывается быстрее? Давайте не будем торопиться с выводами.
