Коллизии - это когда хэшфункция для разных данных выдаёт одинаковый хэш (иными словами, такие a, b, a != b, что
hash(a) == hash(b)). В общем случае этого, конечно, не избежать. Пускай и существуют perfect hash function, они же PHF, они же идеальные хэш-функции - их подбирают под очень конкретные и заранее известные ключи, поэтому эта штука в хэшмапах общего назначения - самый частый гость - едва ли применима.Load factor
Понятие, часто всплывающие при малейшем рассмотрении кулуаров хэшмап. В сущности, просто нижний предел заполнения, после которого хэшмапа решает расширяться. Она-то и так расширяться должна, но это лучше делать не тогда, когда вот вообще прям каждый слот в каждом из бакетов заполнится - по понятным причинам. Чем ближе к заполнению, тем больше коллизии между нижними битами хэша, а плохо это потому, что...
Overflow buckets, its purpose and penalties
Как и было сказано, overflow бакеты формируют связный список. А это значит, что при лукапе значения нам придется теперь не только в основном бакете ключи перебирать, но и в новом. Поскольку overflow бакетов может быть произвольное количество (до тех пор, пока не стриггерит load factor ИЛИ их не станет чрезмерное количество - детальнее будет рассказано в секции "Рост"), то вместо 8 ключей нам может предстоять перебирать уже аж 30-40. Конечно, это амортизируется за счёт первичного сравнения по tophash (о котором будет сказано ниже), но это всё равно неприятно.