| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
PolAR
Зарегистрирован: 01.11.2004
Сообщения: 133
|
 Добавлено: Вс Май 15 2005 15:10 Заголовок сообщения: Help with hash function! |
 |
|
Sorry for english, still cannot set RU typing on my Linux  And my english is not really good
Problem:
I write program, working with network. I need to create & support TCP connection table. So i need halp with creating hash function, wich can associate INT with Socket ( IP1:port1-IP2:port2)!
and somehow need to remember that IP1 and IP2 can change their places ( because packets goes in to ways TUDA & OBRATNO 
I want to find the best way, because perfomance in my program is one of the MAINest things.
Language is C++
P.S. program is capture all packets
_________________
Come Together!! Right Now.... |
|
| Вернуться к началу |
|
 |
критикан
Зарегистрирован: 18.02.2005
Сообщения: 247
|
| Добавлено: Пн Май 16 2005 16:41 Заголовок сообщения: how-to-fly2elephant |
|
|
It's no need to calculate hash value from IP1:port1-IP2:port2 pair for it is already too short
-----------------------------
how-to-fly2elephant |
|
| Вернуться к началу |
|
|
PolAR
Зарегистрирован: 01.11.2004
Сообщения: 133
|
| Добавлено: Вт Май 17 2005 08:37 Заголовок сообщения: Re: how-to-fly2elephant |
|
|
| критикан писал(а): | It's no need to calculate hash value from IP1:port1-IP2:port2 pair for it is already too short
-----------------------------
how-to-fly2elephant |
А как выполнять преобразование (или слияние )этих 4-х типов к одному, чтобы получит необходимый индекс в таблице?
Я вообще решил эту проблему: сварганил класс ( Socket )с 4-мя полями данных ( 2 для IP и 2 для портов ) и загнал в map<Socket, data> .
Но если есть еще варианты - буду благодарен!!
_________________
Come Together!! Right Now.... |
|
| Вернуться к началу |
|
|
критикан
Зарегистрирован: 18.02.2005
Сообщения: 247
|
| Добавлено: Вт Май 17 2005 16:04 Заголовок сообщения: how-to-fly2whale |
|
|
| PolAR писал(а): | | А как выполнять преобразование (или слияние )этих 4-х типов к одному, чтобы получит необходимый индекс в таблице? |
С точки зрения производительности в большинстве практических случаев достаточно просто использовать 4-кратный поиск (разумеется, поиск должен быть быстрым), то есть зафиксировать некоторый порядок элементов и просто искать каждый из 4-х элементов, отмечая, найден он или нет.
Но если гражданин желает принципиально пользовать однократный поиск, то можно упорядочить (например, по возрастанию) элементы внутри четвёрки и, соответственно, перед поиском упорядочивать искомую четвёрку (при таком варианте быстрым должно быть упорядочивание). Главное -- обеспечить уникальность положения элемента внутри четвёрки. Кстати, если использовать хэш для обеспечения уникальности, то упорядочивать всё равно придётся.
-----------------------------
Re: how-to-fly2whale |
|
| Вернуться к началу |
|
|
Wladimir
Зарегистрирован: 02.03.2005
Сообщения: 150
Откуда: Ставропольский край
|
| Добавлено: Вт Май 17 2005 20:34 Заголовок сообщения: |
|
|
2 Polar:
Но IP-адрес-то - по определению - 4-байтовое целое (т.е. unsigned int или long). Разве с целыми есть проблемы? |
|
| Вернуться к началу |
|
|
PolAR
Зарегистрирован: 01.11.2004
Сообщения: 133
|
| Добавлено: Ср Май 18 2005 10:40 Заголовок сообщения: |
|
|
| Wladimir писал(а): | 2 Polar:
Но IP-адрес-то - по определению - 4-байтовое целое (т.е. unsigned int или long). Разве с целыми есть проблемы? |
С ним нет проблем, а вот когда их 2, да еще 2 порта ( unsigned short ) - и ключем в таблице является именно комбинация всех 4-х переменных!
Я так сделал: при формировании ключа сравниваю IP между собой, например:
есть класс:
| Код: | class Sock_Pair{
long ip1,ip2; // ip-addrs
u_short p1,p2;// ports
...
} |
есть IP1:port1 IP2:port2,тогда :
| Код: | if(IP1>IP2){ip1=IP2; ip2=IP1; p1=port2; p2=port1;}
else{наоборот} |
Класс Sock_Pair является ключем в
| Код: | | map<Sock_Pair, MY_DATA> table |
Меня интересует насколько производительна будет эта схема!
Вариант с 4-хкратным поиском тоже хорош ( если использовать какой-нить метод золотого сечения ? ).
Короче - которое решение быстрее?
map выигрывает за счет того что не надо ниче делать
_________________
Come Together!! Right Now.... |
|
| Вернуться к началу |
|
|
Wladimir
Зарегистрирован: 02.03.2005
Сообщения: 150
Откуда: Ставропольский край
|
| Добавлено: Ср Май 18 2005 20:19 Заголовок сообщения: |
|
|
А хеш-функции библиотеки Boost (boost.org) не смотрел?
Расширение STL, не вошедшее в прошлый стандарт C++.
Наверняка вполне пригоден и обычный перебор - но если тебя интересует хеш, там были несколько типовых релизаций. |
|
| Вернуться к началу |
|
|
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
