hash функция

#define N 256

h = (src_ip+dst_ip+proto+sport+dport+bytes) % N

первое, что пришло в голову +)

Ну может быть. только  тогда уж так:
#define N 256
h = (src_ip+dst_ip+proto+sport+dport) % N
так как мне нужно все строки у которых эти параметры совпадают
сложить байты. байты не обязательно чтобы совпадали.
(ну чтобы не сравнивать каждый параметр отдельно, а сравнить только их 
хэш функции).

Вы гарантируете что на разных наборах
src_ip+dst_ip+proto+sport+dport
ваша хэш функция не даст одинаковых результатов???
Пример:
src_ip = 192.168.1.1 
dst_ip 192.168.2.1
proto: 17
sport: 53
dport: 2446

и

src_ip: 192.168.1.1 
dst_ip: 192.168.2.1
proto: 6
sport: 64
dport: 2446

даст одинаковый результат хэш функции. хотя набор данных разный!!!
Не годится.

А хэш-функция и не обязана давать разные результаты на разных наборах.

Обязана.

Слабой хэш-функцией назывется односторонняя функция H(x), удовлетворяющая следующим условиям:
   1. аргумент х может быть строкой бит произвольной длины;
   2. значение H(x) должно быть строкой бит фиксированной длины;
   3. значение H(x) легко вычислить;
   4. для любого фиксированного x вычислительно невозможно найти другой x' != x, такой что H(x')=H(x).
      Пара x' != x, когда H(x')=H(x) называется коллизией хэш-функции.

На самом деле ты прав, вот что я откопал:
"Самый простой вид хеш-функции:
h(k) = k MOD M,
где k — ключ-число, M — размер хеш-таблицы (простое число)
Если ключ k — составной (состоит из нескольких слов / символов x1…xs), можно воспользоваться идеей Дж. Картера и М. Вегмана (1977):
h(k) = (h1(x1) + h2(x2) + ... + hs(xs)) MOD M."

Но к сожалению данный метод мне не подойдет.

Если нужно гарантированное отсутствие коллизий, то хэширование отметается сразу же.

> Обязана.

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

> 4. для любого фиксированного x вычислительно невозможно найти другой x' != x, такой что H(x')=H(x). Пара x' != x, когда H(x')=H(x) называется коллизией хэш-функции.

Это надо понимать так, что не должно существовать методов более эффективных, чем полный перебор. На практике имеет смысл в основном только в криптографии.

Хорошая хэш функция, та в которой вероятность коллизии равномерна для всех входных данных.

По теме: используй crc32 -- вероятность коллизии будет довольно низкой или даже crc16, если число строк не более пары-тройки тысяч.

Тебе вполне подойдёт и хэш с коллизиями. Используешь в качестве хэша, например, два последних байта в src_ip -- это 65536 значений. Заводишь память для 65536 значений следующей структуры, состоящей из значений src_ip, dst_ip, proto, sport , dport, bytes, next_record Где next_record -- ссылка на следующую запись. Далее алгоритм действий такой:

Очередную запись от сетевой карты, проверяешь на совпадение с остальными параметрами, которые хранятся по индексу, взятому как два последних байта из src_ip (xxx.xxx.xхх.a) и dest_ip (xxx.xxx.xxx.b), если там ещё ничего нет, до добавляешь эту запись, если совпадает, то плюсуешь bytes, если не совпадает инициализируешь next_record и заводишь список. При проверке проверяешь по всей цепочке в списке.

Достоинства (на мой взгляд) такого алгоритма в 1)малом числе коллизий из-за небольшой вероятности того, что при равных последних байтах в двух ip адресах будут разные остальные данные. 2)быстрым нахождением предыдущей записи из-за использования a.b как хэш значения.

Можно и усложнить, можно захотеть сбалансированное дерево сделать и т.п.

А "волшебной" хэш функции ты не найдёшь.

> Используешь в качестве хэша, например, два последних байта в src_ip -- это 65536 значений.

Хотел сказать два байта: по байту из src_ip и байт из dest_ip. А впрочем, смотри как тебе лучше, я тебе просто идею подкинул, которую можно и нужно приспособить к своим условиям.

хэш по определению с колизиями - другое дело, что вероянтости малы

можно поиграться с произведением простых чисел в неких степенях - коллизий быть не должно /вроде :)/, но числа гигантские ;)

man md5sum

ok. спасибо, идею понял попробую реализовать.

Посмотри ход хеш функции в ядре. В файле в котором описывается дефрагментация ip пакетов.. Там именно то что тебе нужно.

а чем тебе не устраивает склеивать все поля в строку и тд ???

в строку склеить можно, а что дальше???
сравнивать strcmp??? слишком затратно. 
хочу сравнивать числа.

ok. гляну.

p.s.
эт хорошо теперь у меня много идей смогу выбрать. thnx.

> в строку склеить можно, а что дальше??? сравнивать strcmp??? слишком затратно. хочу сравнивать числа.

Здается мне ты двоешник.

Если тебе не нужно коллизий, то в хэше тебе нужно столько же байт, сколько и в исходных данных.

*_ip это по 4 байта, proto я не знаю сколько -- допустим 1, *port это по 2 байта. Итого 4 + 4 + 1 + 2 + 2 = 13 байт. 13-байтовых чисел пока не бывает.

Тебе нужно просто склеить эти 13 байт в один кусок и сравнивать эти 13 байт с помощью memcmp().

>Здается мне ты двоешник.
Исходя из того, что слово "сдается", пишется так и никак иначе,
у меня сложилось аналогичное мнение относительно тебя.

Просвети пожалуйста что такое 13 байтовое число??? и почему их не бывает???

По теме:
если ты прочтешь еще раз внимательно сообщения, то поймешь что 
говоря о числах я имел ввиду алгоритм предложенный anonymous_incognito, 
в нем никаких чисел, для хранения которых требуется 13 байт не надо. 

> Если тебе не нужно коллизий, то в хэше тебе нужно столько же байт, сколько и в исходных данных.

Если бы ты внимательно читал сообщения, ты бы понял, что я это уже осознал.

Спасибо за еще один вариант решения мое задачи.
Буду выбирать самый быстродействующий.

p.s.
если ты споришь с идиотом, вероятно тоже самое делает и он.

> Исходя из того, что слово "сдается", пишется так и никак иначе, у меня сложилось аналогичное мнение относительно тебя.

засохни карапусс:)

> Просвети пожалуйста что такое 13 байтовое число??? и почему их не бывает???

любое целое представляется набором байт. 1-o, 2-х, 4-х и иногда 8-ми байтовые целые в современных процессорах реализуются эффективно.

а 13-и или 16-ти байтовое целое тебе придется эмулировать несколькими целыми более маленького размера.

> Если бы ты внимательно читал сообщения, ты бы понял, что я это уже осознал.

то есть тебе не страшны коллизии? Ну тогда да -- crc32 нормальный вариант. Но спорно, что быстрее -- много раз вычислять crc32 или много раз делать memcmp 13-ти байтовых строк.

> засохни карапусс:)
:-)
>любое целое представляется набором байт. 1-o, 2-х, 4-х и иногда 8-ми байтовые целые в современных процессорах реализуются эффективно.
А не целое??? Числа с плавающей запятой как-то иначе представляются???
:-)))
>а 13-и или 16-ти байтовое целое тебе придется эмулировать несколькими целыми более маленького размера.
Ну вот а ты говорил, что несуществует. Я уже приготовился вбивать числа, чтобы доказать тебе что они существуют.
Может ты имел ввиду типы данных поддерживаемые процессором???

Коллизи мне как раз страшны. Я пока не успел рассматреть все варианты,
но пока мне нравится идея anonymous_incognito.
Т.е. в идеале как мне кажется это выглядит так: 
сбалансированное дерево,а листья кроме того связаны между собой.
Как в оракле, когда происходит index range scan. чтобы поиск был быстрым.
ключ это по два последних байта из ip адресов, ну или можно как-то сюда добавить порт. но чтобы ключ занимал не  больше 2 байт.
Тогда с одной стороны поиск будет быстрым, и служебной информации
будет не слишком много.

p.s.
с деревьями дело не имел. 
Тяжело ли будет реализовать сбалансированное дело и как оно поведет
себя при вставке???

я спать пошел.

> Тяжело ли будет реализовать сбалансированное дело и как оно поведет себя при вставке???

На практике, о нём начинают задумываться, когда не устраивает существующая скорость. В рамках, озвученной тобой задачи, я бы не стал заморачиваться над сбалансированными деревьями, если только вдруг не устроит скорость. Кстати, глянь решение, которое тебе предложил OxiD, про работу в ядре с дефрагментацией пакетов -- возможно там интересные алгоритмы.

Если иметь ввиду, алгоритм, который я предложил, но учитывать ещё и порт в индексе, то в общем случае, номер порта занимает 2 байта и вместе с 2 байтами от ip адресов, в итоге будет 4 байта. Если хочешь использовать всё-таки, 2 байта, то или тогда брать именно хэш функцию от полной строки или от этих четырёх байт, например поделив, по модулю на 65536. Нет ничего страшного в коллизиях хэш-функции, они приводят только к некоторому усложнению структуры данных, когда предусматривается хранение для каждого хэш-индекса не одного исходного значения, а нескольких. Если хэш функция подобрана правильно, то коллизий на конкретном наборе данных или вообще не случится или их будет немного, они поместятся в список при индексе и из-за небольшого количества не сильно замедлят поиск по хэш значению.