Равномерно распределяющая хеш-функция. Как задействовать все биты хеш-кода?
Простой модуль придумали в те времена (и для тех ситуаций), когда в качестве хэш-кода брался просто адрес объекта. Поскольку адрес часто делится на 4 (или на 8, или имеет вид 16*k+4, как в Borland-C на 8086), то чётная длина массива приводила бы к очень неравномерному распределению.
Вторая (не менее важная) причина - что часто используется внутреннее разрешение коллизий: в каждой "корзине" при этом лежит 0 или 1 элемент множества (никаких списков!). Если ячейка M, куда нужно положить элемент, уже занята, то вычисляют некоторый шаг K=f(M), и проверяют ячейки (M+K)%L, (M+2*K)%L, ..., пока не найдут свободную. Чтобы эта последовательность прошла через весь массив, нужно, чтобы K и L были взаимно простыми. Функцию f приходится вычислять часто, поэтому взаимная простота гарантируется тем, что L берётся простым числом.
Простой модуль придумали в те времена (и для тех ситуаций), когда в качестве хэш-кода брался просто адрес объекта. Поскольку адрес часто делится на 4 (или на 8, или имеет вид 16*k+4, как в Borland-C на 8086), то чётная длина массива приводила бы к очень неравномерному распределению.
Вторая (не менее важная) причина - что часто используется внутреннее разрешение коллизий: в каждой "корзине" при этом лежит 0 или 1 элемент множества (никаких списков!). Если ячейка M, куда нужно положить элемент, уже занята, то вычисляют некоторый шаг K=f(M), и проверяют ячейки (M+K)%L, (M+2*K)%L, ..., пока не найдут свободную. Чтобы эта последовательность прошла через весь массив, нужно, чтобы K и L были взаимно простыми. Функцию f приходится вычислять часто, поэтому взаимная простота гарантируется тем, что L берётся простым числом.