Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

MurmurHash це проста і швидка некриптографічна хеш функція яка підходить для загального пошуку на основі хешування Вона

MurmurHash

MurmurHash

MurmurHash — це проста і швидка некриптографічна хеш-функція, яка підходить для загального пошуку на основі хешування. Вона був створений Остіном Епплбі в 2008 році і зараз розміщена на GitHub разом із набором тестів під назвою «SMHasher». Вона існує в декількох варіантах , усі з яких опубліковані у відкритому доступі. Назва походить від двох основних операцій, множення (MU-ltiply) і повороту (R-otate), які використовуються у її внутрішньому циклі.

На відміну від криптографічних хеш-функцій, вона не розроблена спеціально для того, щоб її було важко відмінити зловмисником, що робить її непридатною для криптографічних цілей.


Із переваг функції автори виділяють простоту, хороший розподіл, хороший лавиновий ефект, висока швидкість и доволі висока стійкість до колізій.

Варіанти

MurmurHash3

Поточна версія — MurmurHash3 , яка повертає 32- або 128-бітове хеш-значення. При використанні 128-бітів версії x86 і x64 не видають однакові значення, оскільки алгоритми оптимізовано для відповідних платформ. MurmurHash3 було випущено разом із SMHasher — пакетом для тестування хеш-функцій.

MurmurHash2

MurmurHash2 видає 32- або 64-бітне значення. Він випускався в кількох варіантах, включаючи такі, які дозволяють використовувати інкрементальне хешування.

  • MurmurHash2 (32-розрядний, x86) - Оригінальна версія; містить недолік, який у деяких випадках призводить до більшої частоти колізій.
  • MurmurHash2A (32-розрядний, x86) – фіксований варіант із використанням конструкції Меркла–Дамгорда . Трохи повільніший.
  • CMurmurHash2A (32-розрядний, x86) - MurmurHash2A, але працює інкрементально.
  • MurmurHashNeutral2 (32-розрядний, x86) - повільніше, але endian і нейтральний до вирівнювання.
  • MurmurHashAligned2 (32-розрядний, x86) — повільніше, але виконує вирівняне читання (що безпечніше на деяких платформах).
  • MurmurHash64A (64-розрядна, x64) - оригінальна 64-bit версія. Оптимізована для 64-розрядної арифметики.
  • MurmurHash64B (64-розрядна, x86) - 64-розрядна версія, оптимізована для 32-розрядних платформ. Це не справжній 64-бітний хеш через недостатнє змішування смуг.

MurmurHash1

Оригінальний MurmurHash був створений як спроба створити швидшу функцію, ніж Lookup3 . Незважаючи на успіх, він не був ретельно протестований і не міг забезпечити створення 64-розрядних хешів, як у Lookup3. Вона мала досить елегантний дизайн, який пізніше буде перенесений на MurmurHash2, поєднуючи мультиплікативний хеш (схожий на хеш-функцію Фаулера–Нолла–Во ) та Xorshift .

Реалізації

Канонічна реалізація в , але функція була портована для багатьох популярних мов, включаючи Python, C, Go, C#, D, Lua, Perl, Ruby, Rust, PHP, Common Lisp, Haskell, [13] Elm, Clojure, [ Scala, Java, Erlang, Swift, Object Pascal, Kotlin, і JavaScript .

Вона використовується у ряді проектів з відкритим вихідним кодом, зокрема (версія 4.6), nginx (версія 1.0.1), Rubinius, libmemcached (драйвер C для Memcached ), npm (менеджер пакетів nodejs), maatkit, Hadoop, Kyoto Cabinet, Cassandra, Solr, vowpal wabbit, Elasticsearch, Guava, Kafka і RedHat Virtual Data Optimizer (VDO) .

Вразливості

Хеш-функції можуть бути вразливими до колізійних атак, коли користувач може вибрати вхідні дані таким чином, щоб навмисно спричинити хеш-колізії. Жан-Філіп Омассон і Деніел Дж. Бернштейн змогли показати, що навіть реалізації MurmurHash із використанням рандомізованого початкового числа вразливі до так званих атак HashDoS. За допомогою диференціального криптоаналізу вони змогли згенерувати вхідні дані, які призвели б до хеш-колізії. Автори атаки рекомендують замість цього використовувати власну функцію SipHash .

Алгоритм

є алгоритм Murmur3_32 // Примітка: у цій версії вся арифметика виконується з 32-розрядними беззнаковими цілими числами. // У разі переповнення результат обрізається за модулем 232 . input: key, len, seed c1 ← 0xcc9e2d51 c2 ← 0x1b873593 r1 ← 15 r2 ← 13 м ← 5 n ← 0xe6546b64 hash← seed for each fourByteChunk of key do 
 k ← fourByteChunk k ← k × c1 k ← k ROL r1 k ← k × c2 hash ← hash XOR k hash ← hash ROL r2 hash ← (hash × m) + n with any remainingBytesInKey do remainingBytes ← SwapToLittleEndian(remainingBytesInKey) // Примітка: зміна порядку байтів необхідна лише на машинах з непрямим порядком байтів (big-endian). remainingBytes ← remainingBytes × c1 remainingBytes ← remainingBytes ROL r1 remainingBytes ← remainingBytes × c2 hash ← hash XOR remainingBytes hash ← hash XOR len hash ← hash XOR (hash >> 16) hash ← hash × 0x85ebca6b hash ← hash XOR (hash >> 13) hash ← hash × 0xc2b2ae35 hash ← hash XOR (hash >> 16)

Нижче наведено зразок реалізації C (для ЦП з прямим порядком байтів):

static inline uint32_t murmur_32_scramble(uint32_t k) {  k *= 0xcc9e2d51;  k = (k << 15) | (k >> 17);  k *= 0x1b873593;  return k; } uint32_t murmur3_32(const uint8_t* key, size_t len, uint32_t seed) { uint32_t h = seed;  uint32_t k;  /* Read in groups of 4. */  for (size_t i = len >> 2; i; i--) {  // Here is a source of differing results across endiannesses.  // A swap here has no effects on hash properties though.  memcpy(&k, key, sizeof(uint32_t));  key += sizeof(uint32_t);  h ^= murmur_32_scramble(k);  h = (h << 13) | (h >> 19);  h = h * 5 + 0xe6546b64;  }    /* Read the rest. */  k = 0;  for (size_t i = len & 3; i; i--) {  k <<= 8;  k |= key[i - 1];  }  // A swap is *not* necessary here because the preceding loop already  // places the low bytes in the low places according to whatever endianness  // we use. Swaps only apply when the memory is copied in a chunk.  h ^= murmur_32_scramble(k);  /* Finalize. */ h ^= len; h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; h *= 0xc2b2ae35; h ^= h >> 16; return h; }

Дивись також

  • Некриптографічні хеш-функції

Посилання

  1. . Hbase.apache.org. 24 липня 2011. Архів оригіналу за 12 січня 2012. Процитовано 13 січня 2012.
  2. Chouza et al [ 2022-03-31 у Wayback Machine.].
  3. Couceiro et al (PDF) (порт.). с. 14. Процитовано 13 січня 2012.
  4. Tanjent (tanjent) wrote,3 March 2008 13:31:00. MurmurHash first announcement. Tanjent.livejournal.com. Процитовано 13 січня 2012.
  5. MurmurHash2-160. Simonhf.wordpress.com. 25 вересня 2010. Процитовано 13 січня 2012.
  6. MurmurHash3 on Github.
  7. Horvath, Adam (10 серпня 2012). MurMurHash3, an ultra fast hash algorithm for C# / .NET.
  8. MurmurHash2 on Github.
  9. MurmurHash2Flaw. Процитовано 15 січня 2019.
  10. MurmurHash3 (see note on MurmurHash2_x86_64). Процитовано 15 січня 2019.
  11. MurmurHash1. Процитовано 12 січня 2019.
  12. pyfasthash in Python. Процитовано 13 січня 2012.
  13. C implementation in qLibc by Seungyoung Kim.
  14. murmur3 in Go.
  15. Landman, Davy. Davy Landman in C#. Landman-code.blogspot.com. Процитовано 13 січня 2012.
  16. std.digest.murmurhash - D Programming Language. dlang.org. Процитовано 5 листопада 2016.
  17. Toru Maesaka in Perl. metacpan.org. Процитовано 13 січня 2012.
  18. Yuki Kurihara (16 жовтня 2014). Digest::MurmurHash. GitHub.com. Процитовано 18 березня 2015.
  19. stusmall/murmur3. GitHub. Процитовано 29 листопада 2015.
  20. PHP userland implementation of MurmurHash3. github.com. Процитовано 18 грудня 2017.
  21. PHP 8.1 with MurmurHash3 support.
  22. tarballs_are_good / murmurhash3. Процитовано 7 лютого 2015.
  23. Haskell. Hackage.haskell.org. Процитовано 13 січня 2012.
  24. Elm. package.elm-lang.org. Процитовано 12 червня 2019.
  25. Murmur3.java in Clojure source code on Github. clojure.org. Процитовано 11 березня 2014.
  26. Scala standard library implementation. 26 вересня 2014.
  27. Murmur3, part of Guava
  28. Murmur3A and Murmur3F Java classes on Github. greenrobot. Процитовано 5 листопада 2014.
  29. bipthelin/murmerl3. GitHub. Процитовано 21 жовтня 2015.
  30. Daisuke T (7 лютого 2019). MurmurHash-Swift. GitHub.com. Процитовано 10 лютого 2019.
  31. GitHub - Xor-el/HashLib4Pascal: Hashing for Modern Object Pascal
  32. goncalossilva/kotlinx-murmurhash. GitHub.com. 10 грудня 2021. Процитовано 14 грудня 2021.
  33. raycmorgan (owner). Javascript implementation by Ray Morgan. Gist.github.com. Процитовано 13 січня 2012.
  34. nginx. Процитовано 13 січня 2012.
  35. Rubinius. Процитовано 29 лютого 2012.
  36. libMemcached. libmemcached.org. Процитовано 21 жовтня 2015.
  37. switch from MD5 to murmur.
  38. maatkit. 24 березня 2009. Процитовано 13 січня 2012.
  39. . Fallabs.com. 4 березня 2011. Архів оригіналу за 28 грудня 2018. Процитовано 13 січня 2012.
  40. . apache.org. 15 листопада 2013. Архів оригіналу за 18 грудня 2013. Процитовано 19 грудня 2013.
  41. Introduction to Apache Cassandra™ + What’s New in 4.0 by Patrick McFadin. DataStax Presents. YouTube. 10 квітня 2019.
  42. . Архів оригіналу за 24 червня 2022. Процитовано 4 березня 2023.
  43. hash.cc in vowpalwabbit source code.
  44. Elasticsearch 2.0 - CRUD and routing changes.
  45. Guava Hashing.java.
  46. Kafka DefaultPartitioner.java.
  47. Virtual Data Optimizer source code
  48. Breaking Murmur: Hash-flooding DoS Reloaded.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

MurmurHash ce prosta i shvidka nekriptografichna hesh funkciya yaka pidhodit dlya zagalnogo poshuku na osnovi heshuvannya Vona buv stvorenij Ostinom Epplbi v 2008 roci i zaraz rozmishena na GitHub razom iz naborom testiv pid nazvoyu SMHasher Vona isnuye v dekilkoh variantah usi z yakih opublikovani u vidkritomu dostupi Nazva pohodit vid dvoh osnovnih operacij mnozhennya MU ltiply i povorotu R otate yaki vikoristovuyutsya u yiyi vnutrishnomu cikli Na vidminu vid kriptografichnih hesh funkcij vona ne rozroblena specialno dlya togo shob yiyi bulo vazhko vidminiti zlovmisnikom sho robit yiyi nepridatnoyu dlya kriptografichnih cilej Iz perevag funkciyi avtori vidilyayut prostotu horoshij rozpodil horoshij lavinovij efekt visoka shvidkist i dovoli visoka stijkist do kolizij VariantiMurmurHash3 Potochna versiya MurmurHash3 yaka povertaye 32 abo 128 bitove hesh znachennya Pri vikoristanni 128 bitiv versiyi x86 i x64 ne vidayut odnakovi znachennya oskilki algoritmi optimizovano dlya vidpovidnih platform MurmurHash3 bulo vipusheno razom iz SMHasher paketom dlya testuvannya hesh funkcij MurmurHash2 MurmurHash2 vidaye 32 abo 64 bitne znachennya Vin vipuskavsya v kilkoh variantah vklyuchayuchi taki yaki dozvolyayut vikoristovuvati inkrementalne heshuvannya MurmurHash2 32 rozryadnij x86 Originalna versiya mistit nedolik yakij u deyakih vipadkah prizvodit do bilshoyi chastoti kolizij MurmurHash2A 32 rozryadnij x86 fiksovanij variant iz vikoristannyam konstrukciyi Merkla Damgorda Trohi povilnishij CMurmurHash2A 32 rozryadnij x86 MurmurHash2A ale pracyuye inkrementalno MurmurHashNeutral2 32 rozryadnij x86 povilnishe ale endian i nejtralnij do virivnyuvannya MurmurHashAligned2 32 rozryadnij x86 povilnishe ale vikonuye virivnyane chitannya sho bezpechnishe na deyakih platformah MurmurHash64A 64 rozryadna x64 originalna 64 bit versiya Optimizovana dlya 64 rozryadnoyi arifmetiki MurmurHash64B 64 rozryadna x86 64 rozryadna versiya optimizovana dlya 32 rozryadnih platform Ce ne spravzhnij 64 bitnij hesh cherez nedostatnye zmishuvannya smug MurmurHash1 Originalnij MurmurHash buv stvorenij yak sproba stvoriti shvidshu funkciyu nizh Lookup3 Nezvazhayuchi na uspih vin ne buv retelno protestovanij i ne mig zabezpechiti stvorennya 64 rozryadnih heshiv yak u Lookup3 Vona mala dosit elegantnij dizajn yakij piznishe bude perenesenij na MurmurHash2 poyednuyuchi multiplikativnij hesh shozhij na hesh funkciyu Faulera Nolla Vo ta Xorshift RealizaciyiKanonichna realizaciya v C ale funkciya bula portovana dlya bagatoh populyarnih mov vklyuchayuchi Python C Go C D Lua Perl Ruby Rust PHP Common Lisp Haskell 13 Elm Clojure Scala Java Erlang Swift Object Pascal Kotlin i JavaScript Vona vikoristovuyetsya u ryadi proektiv z vidkritim vihidnim kodom zokrema libstdc versiya 4 6 nginx versiya 1 0 1 Rubinius libmemcached drajver C dlya Memcached npm menedzher paketiv nodejs maatkit Hadoop Kyoto Cabinet Cassandra Solr vowpal wabbit Elasticsearch Guava Kafka i RedHat Virtual Data Optimizer VDO VrazlivostiHesh funkciyi mozhut buti vrazlivimi do kolizijnih atak koli koristuvach mozhe vibrati vhidni dani takim chinom shob navmisno sprichiniti hesh koliziyi Zhan Filip Omasson i Deniel Dzh Bernshtejn zmogli pokazati sho navit realizaciyi MurmurHash iz vikoristannyam randomizovanogo pochatkovogo chisla vrazlivi do tak zvanih atak HashDoS Za dopomogoyu diferencialnogo kriptoanalizu voni zmogli zgeneruvati vhidni dani yaki prizveli b do hesh koliziyi Avtori ataki rekomenduyut zamist cogo vikoristovuvati vlasnu funkciyu SipHash Algoritmye algoritm Murmur3 32 Primitka u cij versiyi vsya arifmetika vikonuyetsya z 32 rozryadnimi bezznakovimi cilimi chislami U razi perepovnennya rezultat obrizayetsya za modulem 232 input key len seed c1 0xcc9e2d51 c2 0x1b873593 r1 15 r2 13 m 5 n 0xe6546b64 hash seed for each fourByteChunk of key do k fourByteChunk k k c1 k k ROL r1 k k c2 hash hash XOR k hash hash ROL r2 hash hash m n with any remainingBytesInKey do remainingBytes SwapToLittleEndian remainingBytesInKey Primitka zmina poryadku bajtiv neobhidna lishe na mashinah z nepryamim poryadkom bajtiv big endian remainingBytes remainingBytes c1 remainingBytes remainingBytes ROL r1 remainingBytes remainingBytes c2 hash hash XOR remainingBytes hash hash XOR len hash hash XOR hash gt gt 16 hash hash 0x85ebca6b hash hash XOR hash gt gt 13 hash hash 0xc2b2ae35 hash hash XOR hash gt gt 16 Nizhche navedeno zrazok realizaciyi C dlya CP z pryamim poryadkom bajtiv static inline uint32 t murmur 32 scramble uint32 t k k 0xcc9e2d51 k k lt lt 15 k gt gt 17 k 0x1b873593 return k uint32 t murmur3 32 const uint8 t key size t len uint32 t seed uint32 t h seed uint32 t k Read in groups of 4 for size t i len gt gt 2 i i Here is a source of differing results across endiannesses A swap here has no effects on hash properties though memcpy amp k key sizeof uint32 t key sizeof uint32 t h murmur 32 scramble k h h lt lt 13 h gt gt 19 h h 5 0xe6546b64 Read the rest k 0 for size t i len amp 3 i i k lt lt 8 k key i 1 A swap is not necessary here because the preceding loop already places the low bytes in the low places according to whatever endianness we use Swaps only apply when the memory is copied in a chunk h murmur 32 scramble k Finalize h len h h gt gt 16 h 0x85ebca6b h h gt gt 13 h 0xc2b2ae35 h h gt gt 16 return h Divis takozhNekriptografichni hesh funkciyiPosilannya Hbase apache org 24 lipnya 2011 Arhiv originalu za 12 sichnya 2012 Procitovano 13 sichnya 2012 Chouza et al 2022 03 31 u Wayback Machine Couceiro et al PDF port s 14 Procitovano 13 sichnya 2012 Tanjent tanjent wrote 3 March 2008 13 31 00 MurmurHash first announcement Tanjent livejournal com Procitovano 13 sichnya 2012 MurmurHash2 160 Simonhf wordpress com 25 veresnya 2010 Procitovano 13 sichnya 2012 MurmurHash3 on Github Horvath Adam 10 serpnya 2012 MurMurHash3 an ultra fast hash algorithm for C NET MurmurHash2 on Github MurmurHash2Flaw Procitovano 15 sichnya 2019 MurmurHash3 see note on MurmurHash2 x86 64 Procitovano 15 sichnya 2019 MurmurHash1 Procitovano 12 sichnya 2019 pyfasthash in Python Procitovano 13 sichnya 2012 C implementation in qLibc by Seungyoung Kim murmur3 in Go Landman Davy Davy Landman in C Landman code blogspot com Procitovano 13 sichnya 2012 std digest murmurhash D Programming Language dlang org Procitovano 5 listopada 2016 Toru Maesaka in Perl metacpan org Procitovano 13 sichnya 2012 Yuki Kurihara 16 zhovtnya 2014 Digest MurmurHash GitHub com Procitovano 18 bereznya 2015 stusmall murmur3 GitHub Procitovano 29 listopada 2015 PHP userland implementation of MurmurHash3 github com Procitovano 18 grudnya 2017 PHP 8 1 with MurmurHash3 support tarballs are good murmurhash3 Procitovano 7 lyutogo 2015 Haskell Hackage haskell org Procitovano 13 sichnya 2012 Elm package elm lang org Procitovano 12 chervnya 2019 Murmur3 java in Clojure source code on Github clojure org Procitovano 11 bereznya 2014 Scala standard library implementation 26 veresnya 2014 Murmur3 part of Guava Murmur3A and Murmur3F Java classes on Github greenrobot Procitovano 5 listopada 2014 bipthelin murmerl3 GitHub Procitovano 21 zhovtnya 2015 Daisuke T 7 lyutogo 2019 MurmurHash Swift GitHub com Procitovano 10 lyutogo 2019 GitHub Xor el HashLib4Pascal Hashing for Modern Object Pascal goncalossilva kotlinx murmurhash GitHub com 10 grudnya 2021 Procitovano 14 grudnya 2021 raycmorgan owner Javascript implementation by Ray Morgan Gist github com Procitovano 13 sichnya 2012 nginx Procitovano 13 sichnya 2012 Rubinius Procitovano 29 lyutogo 2012 libMemcached libmemcached org Procitovano 21 zhovtnya 2015 switch from MD5 to murmur maatkit 24 bereznya 2009 Procitovano 13 sichnya 2012 Fallabs com 4 bereznya 2011 Arhiv originalu za 28 grudnya 2018 Procitovano 13 sichnya 2012 apache org 15 listopada 2013 Arhiv originalu za 18 grudnya 2013 Procitovano 19 grudnya 2013 Introduction to Apache Cassandra What s New in 4 0 by Patrick McFadin DataStax Presents YouTube 10 kvitnya 2019 Arhiv originalu za 24 chervnya 2022 Procitovano 4 bereznya 2023 hash cc in vowpalwabbit source code Elasticsearch 2 0 CRUD and routing changes Guava Hashing java Kafka DefaultPartitioner java Virtual Data Optimizer source code Breaking Murmur Hash flooding DoS Reloaded

Дата публікації:
Топ