хеш-функция для src dest IP + порт
Так, я смотрю на различные хеш-функции для использования для хеширования 4 IP кортежа и порта для идентификации потоков.
Один я столкнулся, был
((size_t)(key.src.s_addr) * 59) ^
((size_t)(key.dst.s_addr)) ^
((size_t)(key.sport) << 16) ^
((size_t)(key.dport)) ^
((size_t)(key.proto));
Теперь ни за что в жизни я не могу объяснить начало, используемое (59). почему не 31, и затем почему идут, портят его путем умножения спорта на питание 2. Существует ли лучшая хеш-функция, которая будет использоваться для IP-адресов?
2 ответа
Простое число используется потому, что, когда одно значение умножается на простое число, оно имеет более высокую вероятность остаться уникальным, когда другие аналогичные операции накапливаются поверх него. Конкретное значение 59 могло быть выбрано произвольно или намеренно. Сложно сказать. Возможно, 59 имели тенденцию генерировать лучшее распределение значений на основе наиболее вероятных входных данных.
Сдвиг на 16 может быть вызван тем, что порты ограничены диапазоном 2 ^ 16. Похоже, что функция перемещает исходный порт в верхнюю часть битового поля, оставляя порт назначения в нижней части. Думаю, это можно объяснить в следующем абзаце.
Другая причина, по которой происходит умножение (и это верно и для операции сдвига), заключается в том, что оно нарушает ассоциативный характер хеш-функции. Помните, что XOR является ассоциативным, поэтому IP-адреса src = 192.168.1.1 и dst = 192.168.1.254 будут хешировать до того же значения, что и src = 192.168.1.254 и dst = 192.168.1.1 (поменяно местами), если бы умножения не было.
Изучите выходные данные функции на предмет равномерного распределения. Если вам это не нравится, вставьте несколько разных простых чисел, пока не получите дистрибутив, который вам нравится. Хеширование может быть очень мрачным искусством без «правильного» ответа.