Как захешировать структуру, содержащую ip-адрес и порт?

g_u_e_s_t · Регистрация: 06.02.2011

Студворк — интернет-сервис помощи студентам

Добрый вечер всем.
Есть некая структура в упрошенном виде:

C
1
2
3
4
struct session {
  struct sockaddr local;
  struct sockaddr peer;
};

Адреса могут быть как IPv4 так и IPv6. И мне хочется это как-то хэшировать.
Поиски говорят, что народ для похожих целей в основном использует вариации jhash от Bob Jenkins
Может кто-нибудь посоветует что-то другое?

@niXman · 04.10.2011, 23:59

http://en.cppreference.com/w/cpp/utility/hash
?

@niXman · 05.10.2011, 00:17

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

g_u_e_s_t · 05.10.2011, 00:20 **[ТС]**

niXman, это ж вроде FNV или я что-то попутал?
Если он, то не катит.

Добавлено через 2 минуты

Сообщение от niXman

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

А я тебя) с std::tr1::hash попутал

@niXman · 05.10.2011, 00:49

хотя нет... запутался. ща.

Добавлено через 22 минуты
по заявлению стандарта, std::hash инклюдится через functional.
и правда, но реализация находится в bits/functional_hash.h (см. строку 59)
что мы тут видим... кучу специализация для тривиальных типов, а самое интересное начинается со строки 127. где реализован _Hash_impl и _Fnv_hash_impl. второй, по идее, именно FNV хеш. тебе оно не надо. значит смотрим _Hash_impl. видно, что реализация хеширования вынесена в функцию _Hash_bytes. где же эта функция?.... а, вот она!
судя по коментам, используется алгоритм Murmur. (забавное название)

зы
собственно я никогда напрямую не юзал std::hash, но частенько ловил себя на мысле что разобраться нужно, т.к. это позволит избавиться от еще одного велосипеда

разобрался.

Добавлено через 5 минут
осталось понять как все это дело применить к твоей задаче) терпение...

g_u_e_s_t · 05.10.2011, 00:49 **[ТС]**

niXman, спасибо.
MurmurHash3 я рассматривал, мне нравиться, но смущает что например во всех ядрах юзают JHash.
Я наверное плохо сформулировал вопрос. Я не прошу найти мне какую-нибудь хэш ф-цию, я прошу так сказать поделиться личным опытом. Наверняка я тут не первый кому понадобилось хэшировать пары адрес:порт

@niXman · 05.10.2011, 01:45

ну не знаю.. по хешированию адрес:порт я вряд ли что умное скажу.

Добавлено через 45 минут
может кому сгодится:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <functional>
 
#include <sys/socket.h>
 
struct session {
   struct sockaddr local;
   struct sockaddr peer;
};
 
namespace std {
 
template<>
struct hash<session>: std::unary_function<session, size_t> {
   size_t operator()(const session& s) const {
      return _Hash_impl::hash(&s, sizeof(s));
   }
};
 
} // namespace std
 
int main() {
   session s;
   std::hash<session> h;
   std::cout << std::hex << h(s) << std::endl;
}

http://liveworkspace.org/code/... 2031e2fda1

g_u_e_s_t · 05.10.2011, 08:57 **[ТС]**

Сообщение от niXman

может кому сгодится:

Если брать Murmur, то явно не Murmur1 (она проигрывает и JHash и свежим Murmur практически по всем тестам) из stdc++, а Murmur3.

@niXman · 05.10.2011, 09:28

Сообщение от g_u_e_s_t

а Murmur3.

смотрел уже. невероятно высокая скорость хеширования.

g_u_e_s_t · 05.10.2011, 09:31 **[ТС]**

Угумс, впечатляет. И становиться еще не понятней почему в сетевом коде ядер и на линуксе и на бсд используют JHash.

@niXman · 05.10.2011, 09:58

возможно по лицензии не проходит. я вообще не нашел лицензии.

g_u_e_s_t · 05.10.2011, 10:40 **[ТС]**

Public domain - лучше не бывает)

Добавлено через 29 минут
Кажется нашел почему не хотят в ядра:
David Miller:

I'm trying to avoid multiplies that are not done in hardware on some
cpus.

Осталось выяснить скрывается ли под some cpus гавно мамонта или какая-то экзотика...

accept · 06.10.2011, 02:01

Сообщение от g_u_e_s_t

Есть некая структура в упрошенном виде:

переведи её в текст и хешируй его
"127.0.0.1:123;127.0.0.1:456"

g_u_e_s_t · 06.10.2011, 10:36 **[ТС]**

Сообщение от accept

переведи её в текст и хешируй его

Два вопроса:
Что это даст? Ну не понимаю я чем строка может быть лучше.
Чем? Какую хэш ф-цию то посоветуете.

PS: пока сделал прототип с JHash и протестировал пару /8 сетей за вычетом бродкаст и мультикаст адресов - работает, была 1 коллизия.

accept · 06.10.2011, 10:45

Сообщение от g_u_e_s_t

Что это даст? Ну не понимаю я чем строка может быть лучше.

строка всегда одинаковая и не зависит от реализации

Сообщение от g_u_e_s_t

Какую хэш ф-цию то посоветуете.

любую

g_u_e_s_t · 06.10.2011, 10:56 **[ТС]**

Сообщение от accept

строка всегда одинаковая и не зависит от реализации

У хэша будет "локальное" применение, в смысле за пределы машины он передаваться не будет.

А профит то в чем? Затраты на перевод есть, а хорошей (speed/avalanche/collisions) хэш ф-ции которой не все равно строка или байты как бы и нет... Точнее есть, но с короткими строками не дружат.

accept · 06.10.2011, 11:15

Сообщение от g_u_e_s_t

в смысле за пределы машины он передаваться не будет

смысл в том, чтобы не хешировать всю структуру, а собрать только то, что нужно

g_u_e_s_t · 06.10.2011, 11:24 **[ТС]**

Сообщение от accept

смысл в том, чтобы не хешировать всю структуру, а собрать только то, что нужно

Эм я и так поля размеров и выравнивания как бы и не собирался хэшировать...
В хэш идет 48/144 бита на адрес.

@prik · 06.10.2011, 14:26

Сообщение от g_u_e_s_t

а хорошей (speed/avalanche/collisions) хэш ф-ции которой не все равно строка или байты как бы и нет... Точнее есть, но с короткими строками не дружат.

А что за хеш для таких строк?

g_u_e_s_t · 06.10.2011, 14:31 **[ТС]**

Например вариация Murmur от гугла CityHash

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	04.10.2011, 23:59
	http://en.cppreference.com/w/cpp/utility/hash ? 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	05.10.2011, 00:17
	упс, не правильно понял тебя. 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	05.10.2011, 00:49
	хотя нет... запутался. ща. Добавлено через 22 минуты по заявлению стандарта, std::hash инклюдится через functional. и правда, но реализация находится в bits/functional_hash.h (см. строку 59) что мы тут видим... кучу специализация для тривиальных типов, а самое интересное начинается со строки 127. где реализован _Hash_impl и _Fnv_hash_impl. второй, по идее, именно FNV хеш. тебе оно не надо. значит смотрим _Hash_impl. видно, что реализация хеширования вынесена в функцию _Hash_bytes. где же эта функция?.... а, вот она! судя по коментам, используется алгоритм Murmur. (забавное название) зы собственно я никогда напрямую не юзал std::hash, но частенько ловил себя на мысле что разобраться нужно, т.к. это позволит избавиться от еще одного велосипеда разобрался. Добавлено через 5 минут осталось понять как все это дело применить к твоей задаче) терпение... 1

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	05.10.2011, 00:49 [ТС]
	niXman, спасибо. MurmurHash3 я рассматривал, мне нравиться, но смущает что например во всех ядрах юзают JHash. Я наверное плохо сформулировал вопрос. Я не прошу найти мне какую-нибудь хэш ф-цию, я прошу так сказать поделиться личным опытом. Наверняка я тут не первый кому понадобилось хэшировать пары адрес:порт 0

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	05.10.2011, 09:31 [ТС]
	Угумс, впечатляет. И становиться еще не понятней почему в сетевом коде ядер и на линуксе и на бсд используют JHash. 0

@niXman 3211 / 1459 / 74 Регистрация: 09.08.2009 Сообщений: 3,441 Записей в блоге: 2
	05.10.2011, 09:58
	возможно по лицензии не проходит. я вообще не нашел лицензии. 0

g_u_e_s_t 1259 / 650 / 44 Регистрация: 06.02.2011 Сообщений: 1,654
	06.10.2011, 14:31 [ТС]
	Например вариация Murmur от гугла CityHash 1