The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

форумы  помощь  поиск  регистрация  майллист  вход/выход  слежка  RSS
"Компания Google открыла код hash-функций CityHash"
Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Изначальное сообщение [ Отслеживать ]

"Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от opennews (ok) on 12-Апр-11, 17:29 
Разработчики из компании Google представили (http://google-opensource.blogspot.com/2011/04/introducing-ci...) реализацию  64- и 128-разрядных hash-функций CityHash (http://code.google.com/p/cityhash/), позволяющих получить отпечаток фиксированной длинны, идентифицирующий больший по размеру набор входящих данных. Код функций написан на языке C++, распространяется в рамках лицензии MIT и разработан в стиле "все ради высокой производительности".

Код CityHash был написан для реализации высокопроизводительных хэш-таблиц, используемых для организации хранения баз ключ-значение. Функция  CityHash128 оптимизирована для строк размером в несколько сотен байт. Оптимизация кода, использование 64-разрядных регистров, обеспечение параллелизма выполнения на уровне инструкций и быстрый доступ к невыровненным областям памяти, позволили добиться значительного превосходства в производительности, по сравнению с другими реализациями хэшей. Ценой производительности является достаточно сильная...

URL: http://google-opensource.blogspot.com/2011/04/introducing-ci...
Новость: http://www.opennet.me/opennews/art.shtml?num=30218

Ответить | Правка | Cообщить модератору

Оглавление

Сообщения по теме [Сортировка по времени | RSS]


1. "Компания Google открыла код hash-функций CityHash"  –1 +/–
Сообщение от pavlinux (ok) on 12-Апр-11, 17:29 
http://code.google.com/p/cityhash/source/browse/trunk/src/ci...

А где там C++ ? :)

---

А, во, нашел

#include <algorithm>

using namespace std;

pair<uint64, uint64> v, w;
std::swap(z, x);

и всё :)

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

6. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от Аноним (??) on 12-Апр-11, 18:05 
По вашему любой код на плюсах должен использовать все, включая самые безумные, возможности этого монструозного языка?
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

8. "Компания Google открыла код hash-функций CityHash"  +2 +/–
Сообщение от parad (??) on 12-Апр-11, 18:32 
блин, ну оберни это в класс, сделай фабрику, опиши это в интерфейсах, как-нибудь припиши к этому буст, и оповести всех нас и компанию гугл о своих достижениях письмом на spam@google.com и очередным бессмысленно-неинформативным комментом здесь. порадуй.
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

23. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от pavlinux (ok) on 13-Апр-11, 01:00 
На, жуй

http://pavlinux.ru/CityHash/city.c
http://pavlinux.ru/CityHash/city.h

Кампилитца как С так С++ одновременно.

Ответить | Правка | ^ к родителю #8 | Наверх | Cообщить модератору

27. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от oops_ on 13-Апр-11, 05:33 
И где там C++?

А, во, нашел #ifdef __cplusplus

Ответить | Правка | ^ к родителю #23 | Наверх | Cообщить модератору

30. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от pavlinux (ok) on 13-Апр-11, 17:20 
> И где там C++?
> А, во, нашел #ifdef __cplusplus

:)

Ответить | Правка | ^ к родителю #27 | Наверх | Cообщить модератору

9. "Компания Google открыла код hash-функций CityHash"  –7 +/–
Сообщение от gildor on 12-Апр-11, 18:37 
В коде есть объявления локальных переменных в середине тела функции - такое C-компилятор не "переварит".
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

14. "Компания Google открыла код hash-функций CityHash"  +5 +/–
Сообщение от pavlinux (ok) on 12-Апр-11, 19:02 
> В коде есть объявления локальных переменных в середине тела функции - такое
> C-компилятор не "переварит".

переварит.

Ответить | Правка | ^ к родителю #9 | Наверх | Cообщить модератору

24. "Компания Google открыла код hash-функций CityHash"  –4 +/–
Сообщение от gildor on 13-Апр-11, 01:17 
> переварит.

Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис отключить.

Ответить | Правка | ^ к родителю #14 | Наверх | Cообщить модератору

25. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от pavlinux (ok) on 13-Апр-11, 01:28 
>> переварит.
> Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис
> отключить.

Я чего-то не пойму... где проблема? 


struct a {int x; int y;};
void vodi() {
    int x = 0;
    printf("%e\n", x);
    memset(NULL, 0, 1);

   for (int i = 0; i < 1024; i++) { // С99
      int x = 1024;                    // С99
          struct a vec = {i+2*i, (x+i)/i}; // С99
     }
}

какое место не нравиться?

Ответить | Правка | ^ к родителю #24 | Наверх | Cообщить модератору

31. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от gildor on 17-Май-11, 16:47 
>>> переварит.
>> Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис
>> отключить.
> Я чего-то не пойму... где проблема?
> ...
> какое место не нравиться?

Здесь всё в порядке. Но код вида


int a = 1;  // объявление переменной
a = a + 1;  // операция без объявления переменной
int b = 2;  // снова объявление переменной

по крайнёй мере Visual C++ 9 (2008) не возьмёт - в 3й строке выдаст ошибку, если компились файл как C, а не как C++. Недавно перекомпилировал SDL 1.3 - там как раз была такая проблема.
Ответить | Правка | ^ к родителю #25 | Наверх | Cообщить модератору

26. "Компания Google открыла код hash-функций CityHash"  +2 +/–
Сообщение от bircoph (ok) on 13-Апр-11, 04:32 
Уже лет 8 как жуёт без всяких расширений, если не больше.

Ответить | Правка | ^ к родителю #24 | Наверх | Cообщить модератору

10. "Компания Google открыла код hash-функций CityHash"  –1 +/–
Сообщение от User294 (ok) on 12-Апр-11, 18:53 
> http://code.google.com/p/cityhash/source/browse/trunk/src/ci...
> А где там C++ ? :)
> #include <algorithm>
> using namespace std;
> pair<uint64, uint64> v, w;
> std::swap(z, x);
> и всё :)

Еще коменты в виде // :).Или в свежих вариантах стандарта си это уже можно? Я понимаю что компилерам пофиг и они и это жрут, но формально // вроде как считается не совместимым с большей частью стандартов на си.


Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

11. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от Aleksey (??) on 12-Апр-11, 18:56 
Это C++. Там же теплейты, а это щастье доступно только на C++.
Ответить | Правка | ^ к родителю #10 | Наверх | Cообщить модератору

13. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от pavlinux (ok) on 12-Апр-11, 19:01 
>> http://code.google.com/p/cityhash/source/browse/trunk/src/ci...
>> А где там C++ ? :)
>> #include <algorithm>
>> using namespace std;
>> pair<uint64, uint64> v, w;
>> std::swap(z, x);
>> и всё :)
> Еще коменты в виде // :).Или в свежих вариантах стандарта си это
> уже можно?

С99 можно.

Ответить | Правка | ^ к родителю #10 | Наверх | Cообщить модератору

18. "Компания Google открыла код hash-функций CityHash"  –1 +/–
Сообщение от User294 (ok) on 12-Апр-11, 19:19 
> С99 можно.

А, тогда ок.

Ответить | Правка | ^ к родителю #13 | Наверх | Cообщить модератору

15. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от klalafuda on 12-Апр-11, 19:02 
> Еще коменты в виде // :).Или в свежих вариантах стандарта си это уже можно? Я понимаю что компилерам пофиг и они и это жрут, но формально // вроде как считается не совместимым с большей частью стандартов на си.

ISO/IEC 9899:1999 (E)

  6.4.9 Comments
1 Except within a character constant, a string literal, or a comment, the characters /*
  introduce a comment. The contents of such a comment are examined only to identify
  multibyte characters and to find the characters */ that terminate it.69)
2 Except within a character constant, a string literal, or a comment, the characters //
  introduce a comment that includes all multibyte characters up to, but not including, the
  next new-line character. The contents of such a comment are examined only to identify
  multibyte characters and to find the terminating new-line character.

Ответить | Правка | ^ к родителю #10 | Наверх | Cообщить модератору

17. "Компания Google открыла код hash-функций CityHash"  –6 +/–
Сообщение от Fixxxer (??) on 12-Апр-11, 19:19 
Согласен - везде где можно использовать возможности плюсов, надо их использовать. Не на убогом Си же в конце то концов писать? Хотя мазохистов в последнее время полно. =)
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

4. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от klalafuda on 12-Апр-11, 17:49 
Им было удобнее выразить uint128 через пару uint64 + uint64. Хотя от плюсов там конечно не много. Прямо скажем - ничего. Да и то, что есть... using namespace std - расстрел. stdlib.h vs cstdlib, переопределение uintXX_t в uintXX (нахуа?), сплошной char * vs std::string & и пр.. в общем, тяжелое бремя C просто так не проходит. Уж лучше бы написали на C и не вы&^$%&^сь почем зря.
Ответить | Правка | ^ к родителю #17 | Наверх | Cообщить модератору

5. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от klalafuda on 12-Апр-11, 17:53 
> Им было удобнее выразить uint128 через пару uint64 + uint64. Хотя от плюсов там конечно не много. Прямо скажем - ничего. Да и то, что есть... using namespace std - расстрел. stdlib.h vs cstdlib, переопределение uintXX_t в uintXX (нахуа?), сплошной char * vs std::string & и пр.. в общем, тяжелое бремя C просто так не проходит. Уж лучше бы написали на C и не вы&^$%&^сь почем зря.

PS: Впрочем, к самому алгоритму и получаемому хешу это отношения не имеет. Переписывается на что угодно как угодно в течении часа. Если очень хочется. Всего лишь мелкие придирки к стилю конкретного девелупера гугла, не более. А вот то, что описание подоплеки и математическое обоснование алгоритма отсутствует и есть лишь тупой код не важно какого размера - use it on your own risk. Удачи.

Ответить | Правка | ^ к родителю #4 | Наверх | Cообщить модератору

7. "Компания Google открыла код hash-функций CityHash"  –1 +/–
Сообщение от pavlinux (ok) on 12-Апр-11, 18:10 
static uint128 CityMurmur(const char *s,...

Как англоязычные программеры читают этот бред?! :)

cтатичный бцел128 ГородМурмур(пост символ *s,...

Ответить | Правка | ^ к родителю #5 | Наверх | Cообщить модератору

12. "Компания Google открыла код hash-функций CityHash"  –1 +/–
Сообщение от User294 (ok) on 12-Апр-11, 19:00 
> static uint128 CityMurmur(const char *s,...
> Как англоязычные программеры читают этот бред?! :)
> cтатичный бцел128 ГородМурмур(пост символ *s,...

А все-равно у нас круче умеют :). На вот тебе, http://habrahabr.ru/blogs/compilers/116301/
Самопальный гопоязык то черт с ним, а вот "сишный" сорц в коментах выглядит убедительно....

Ответить | Правка | ^ к родителю #7 | Наверх | Cообщить модератору

16. "Компания Google открыла код hash-функций CityHash"  +1 +/–
Сообщение от Аноним (??) on 12-Апр-11, 19:16 
CityMurmur - ШёпотГорода, что такого?
Ответить | Правка | ^ к родителю #7 | Наверх | Cообщить модератору

28. "Компания Google открыла код hash-функций CityHash"  +/–
Сообщение от Аноним (??) on 13-Апр-11, 09:25 
char* вместо std::string это как раз очень правильно, с остальным согласен.
Ответить | Правка | ^ к родителю #4 | Наверх | Cообщить модератору

19. "Компания Google открыла код hash-функций CityHash"  +1 +/–
Сообщение от Aquarius (ok) on 12-Апр-11, 19:39 
> Утверждается, что представленные функции не подходят для использования в криптографии, так как алгоритм работы CityHash подразумевает смешивание битов входящего потока, что допускает появление коллизий (вероятность коллизий крайне низка, что подтверждено накопленной статистикой).

существование коллизий - генетическое свойство любых hash-функций

P.S. математики это доказали задолго до появления компьютеров

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

22. "Компания Google открыла код hash-функций CityHash"  –1 +/–
Сообщение от User294 (ok) on 12-Апр-11, 21:18 
Все правильно, просто для криптографически стойких хеш-функций подбор коллизии для известного хеша должен быть сравним по затратности с лобовым брутфорсом. У гугли видимо это требование не выполняется - видимо, можно подобрать коллизии существенно проще. Поэтому их функция может и неплоха для некоторых применений (как фукция для hash-table), но не годится для криптографических применений(как функция криптографически удостоверяющая неизменность некоего сообщения, например). А то что существует бесконечно много наборов данных которые мапятся в 128-битный результат не понятно только идиотам да копирасам которые дошли до того что пытаются качать права на вполне конкретные хеши :))))
Ответить | Правка | ^ к родителю #19 | Наверх | Cообщить модератору

29. "Компания Google открыла код hash-функций CityHash"  +1 +/–
Сообщение от kibab on 13-Апр-11, 16:15 
Её и не предполагается использовать для криптографии. Об этом в статье написано.
Ответить | Правка | ^ к родителю #22 | Наверх | Cообщить модератору

20. "Компания Google открыла код hash-функций CityHash"  +2 +/–
Сообщение от Аноним (??) on 12-Апр-11, 19:44 
> Утверждается, что представленные функции не подходят для использования в криптографии, так как алгоритм работы CityHash подразумевает смешивание битов входящего потока, что допускает появление коллизий (вероятность коллизий крайне низка, что подтверждено накопленной статистикой).

Давно не читал подобного бреда.

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

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

21. "Компания Google открыла код hash-функций CityHash"  +1 +/–
Сообщение от FastDuck on 12-Апр-11, 21:08 
Мы вам верим, но всё же - где ссылка на бенчмарки?
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей 		Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру