LINUX.ORG.RU
Форум — Development  

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


0

0
Нужно дерево в которое бы помещалась инфа о пакетах. Поля по которым будет производится вставка/поиск - адрес источника, назначения и порты. Поскольку их целых четыре то возникает проблема =) Пока мне приходит в голову вычислить для каждого хеш, и уже по нему добавлять в дерево инфу. Но хеши могут совпадать..
★★★★
← нити
Ссылка на элемент списка в другом списке →
А вопрос в чем? Коллизия хэш-значений - стандартная ситуация, со стандартными средствами решения.

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

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

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

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

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

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

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

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

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

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

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

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

tailgunner ★★★★★
()
Ответ на: комментарий от OxiD
> И дерево работает быстрее. в таблице в среднем надо проверить 10 вхождений

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

Sphinx ★★☆☆
()
Ответ на: комментарий от Sphinx
> Каждому хэш-значению соответствует _список_ элементов данных с этим значением (или указателей на них).
OxiD ★★★★
() автор топика
Ответ на: комментарий от anonymous
Всем спасибо! Пока остановился на бинарном дереве с составным ключом. Вроде по производительности устраивает.

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

OxiD ★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← нити
Development
Ссылка на элемент списка в другом списке →