Макс, а Map с какой сложностью исполняет has на больших сетах ?
все зависит от колличества коллизий. Но вообще должен с O(1) в наилучшем случае (когда нет коллизий) и O(k), где k - это колличество коллизий для одного хеша в наихудшем ну или средняя рлотность коллизий для всей таблицы