Имеется некое количество (от едениц до 10ков тысяч) списков (singly-linked) таких структур:
struct subnet {
    struct sockaddr addr;
    u_int8_t mask;
    u_int8_t exclude;
}
по которым после некой обработки строятся rb-деревья.
Суть проблемы в том, что часть списков может быть абсолютно идентична (равное количество совпадающих адресов в одной и той же последовательности).
Посоветуйте какую-нибудь легкую хеш функцию для адресов.

• хеширование   ip,mmmm, 10:56 , 21-Дек-10
  • хеширование   ip,guest, 11:25 , 21-Дек-10
• хеширование   ip,Andrey Mitrofanov, 11:00 , 21-Дек-10
  • хеширование   ip,guest, 11:19 , 21-Дек-10
    • хеширование   ip,mmmm, 11:31 , 21-Дек-10
      • хеширование   ip,guest, 11:38 , 21-Дек-10
        • хеширование   ip,mmmm, 11:52 , 21-Дек-10
          • хеширование   ip,guest, 12:03 , 21-Дек-10
    • хеширование   ip,Andrey Mitrofanov, 11:53 , 21-Дек-10
• хеширование   ip,pavel_simple, 13:07 , 21-Дек-10
  • хеширование   ip,guest, 13:41 , 21-Дек-10

> Имеется некое количество (от едениц до 10ков тысяч) списков (singly-linked) таких структур:
> struct subnet {
>     struct sockaddr addr;
>     u_int8_t mask;
>     u_int8_t exclude;
> }
> по которым после некой обработки строятся rb-деревья.
> Суть проблемы в том, что часть списков может быть абсолютно идентична (равное
> количество совпадающих адресов в одной и той же последовательности).
> Посоветуйте какую-нибудь легкую хеш функцию для адресов.

CRC32

> CRC32

В чистом виде не катит для списков, а строить массив из них лишняя трата времени и главное памяти.

http://google.ru/search?q=ipv4+address+hash

> http://google.ru/search?q=ipv4+address+hash

v4 лишнее)))
там может быть микс из v4/v6
Ну и уж извините, но ответ в стиле "выбирай сам" не очень интересен.

>> http://google.ru/search?q=ipv4+address+hash
> v4 лишнее)))
> там может быть микс из v4/v6
> Ну и уж извините, но ответ в стиле "выбирай сам" не очень
> интересен.

А md5 либо sha-1?
но по-моему они не такие и легковесные

> А md5 либо sha-1?
> но по-моему они не такие и легковесные

С ними тот же трабл, что и с crc. Это же все изначально блочные хэши.
Т.е. получаеться что я должен конвертировать список в массив (как минимум убрать указатели на следующий элемент).

>> А md5 либо sha-1?
>> но по-моему они не такие и легковесные
> С ними тот же трабл, что и с crc. Это же все
> изначально блочные хэши.
> Т.е. получаеться что я должен конвертировать список в массив (как минимум убрать
> указатели на следующий элемент).

Вот взгляните может это подойдет
http://ru.wikipedia.org/wiki/HMAC

> Вот взгляните может это подойдет
> http://ru.wikipedia.org/wiki/HMAC

Идея в том чтобы хешировать списки поэлементно используя в качестве ключа результат предыдущего хеширования?

Да, на здоровье. Вопрос в стиле "выберите за меня" ещё менее.

> Имеется некое количество (от едениц до 10ков тысяч) списков (singly-linked) таких структур:
> struct subnet {
>     struct sockaddr addr;
>     u_int8_t mask;
>     u_int8_t exclude;
> }
> по которым после некой обработки строятся rb-деревья.
> Суть проблемы в том, что часть списков может быть абсолютно идентична (равное
> количество совпадающих адресов в одной и той же последовательности).
> Посоветуйте какую-нибудь легкую хеш функцию для адресов.

в линухах в ядре чаще всего используют jhash -- а вообще можно посмотреть сдесь -- http://www.azillionmonkeys.com/qed/hash.html и сдесь http://burtleburtle.net/bob/hash/doobs.html

хотя вопрос из разряда "сделайте мне заебись"

спс за ссылки, читаю, интересно.