Здравствуйте, samius, Вы писали:

S>В общем, верно. Но цель хэшфункции, как правило, как раз в минимизации коллизий.

Коллизий будет одинаково и при переборе всех элементов и при использовании только 4 байт.

S>В каком-то частном случае — не возражаю. В общем случае — не согласен. Общеупотребимы те способы вычисления хэша массива, которые при отличии даже в одном элементе, имеют тенденцию вычислять разное значение.

Это кто сказал?

Обычно разные массивы имеют разное начало или разный конец (в зависимости от направленности массива). По этому целесообразно взять 2 байта в начале 2 байта в конце.

Количество коллизий будет одинаково. Если вы задействуете все элементы, коллизии будут у даже не похожих массивов. Если только 4 байта -- коллизии будут у похожих массивов, у которых одинаковое начало и конец.

Кто сказал что одно лучше другого? Пусть уж лучше похожие массивы имеют одинаковый хеш-код.

S>ЗЫ. При увеличиении вероятности коллизии нелинейным образом возрастает необходимость выполнения сравнения, которое обычно дороже чем вычисление хэша.

А вот и нет. Операция сравнения работает пока не найдет разные элементы. То есть она редко перебирает все элементы массива. А вот неправильная операция вычисления хеш-кода перебирает элементы массива во всех случаях. По этому вместо ускорения получаем замедление.

Сорри, согласен. Но кто сказал что коллизий будет меньше, если вы переберете все элементы массива?