Деревья для хранения tcp пакетов.

А вопрос в чем? Коллизия хэш-значений - стандартная ситуация, со стандартными средствами решения.

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

По всем одновременно. Ищется определенный пакет в дереве. А как решать ситуацию с коллизией? я использую функцию jhash и ядра линукса, и в дерево получается поместить максимум 30-40 пакетов, после этого возникает коллизия. Хочется их туда засунуть хотя бы пару сотен )

> Ищется определенный пакет в дереве.

Почему ты называешь хэш-таблицу "деревом"?

> А как решать ситуацию с коллизией?

Каждому хэш-значению соответствует _список_ элементов данных с этим значением (или указателей на них).

Не, ты меня не понял. У меня нет хеш таблицы. У меня есть дерево. В которое надо добавлять пакеты отлавливаемые через libpcap. Идентифицируются они по адресам и портам. Поэтому я вычисляю хеш из этих четырех чисел, и использую его как ключ в дереве.

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

Собственно прошу подобрать наиболее подходящую хеш функцию, или еще какой метод добавления пакетов в дерево.

> хеш таблица меня не устроила - эти самые списки с одинаковым хешем слишком длинные выходят. Коллизий слишком много. И дерево работает быстрее. в таблице в среднем надо проверить 10 вхождений, в дереве 4.

Здесь я совсем потерялся: количество коллизий не зависит от того, что используется - таблица или дерево, а только от используемой хэш-функции.

> Собственно прошу подобрать наиболее подходящую хеш функцию, или еще какой метод добавления пакетов в дерево.

Тебе нужна именно хэш-функция? ИМХО, здесь вполне подойдет обычное дерево с составным ключом *адрес1, адрес2, порт1, порт2".

> И дерево работает быстрее. в таблице в среднем надо проверить 10 вхождений

В таблице ≈10? Как так? Только одно!

> Каждому хэш-значению соответствует _список_ элементов данных с этим значением (или указателей на них).

>Коллизий слишком много

Вот тут (http://www.partow.net/programming/hashfunctions/index.html#AvailableHashFunct...) есть список из десятка функций. Возможно, вопрос в выборе оптимальной.

Всем спасибо! Пока остановился на бинарном дереве с составным ключом. Вроде по производительности устраивает.

На хеши обязательно погляжу.