FNV

FNV (англ. Fowler–Noll–Vo) — простая хеш-функция для общего применения, разработанная Гленом Фаулером, Лондоном Керт Нолом и Фогном Во. Не является криптографической функцией. Существуют варианты для 32-, 64-, 128-, 256-, 512-, и 1024-битных хешей.

Математическая запись

Функция FNV:

,
,
,
— простое число,
— входная последовательность двоичных слов.

Модифицированная функция FNV:

,
.

Пример кода

Функция проста в реализации. Её основа — умножение на простое число и сложение по модулю 2 с входным текстом. 

const unsigned FNV_32_PRIME = 0x01000193;

unsigned int FNV1Hash (char *buf)
{
  unsigned int hval = 0x811c9dc5; // FNV0 hval = 0

  while (*buf)
    {
      hval *= FNV_32_PRIME;
      hval ^= (unsigned int)*buf++;
    }

  return hval;
}

Модификации

Существует модификация алгоритма, решающая некоторые его проблемы. В частности, проблему последнего байта. Весь смысл модификации — замена порядка операций на обратный. Сначала сложение, затем трансформация хеша (умножение на простое число).

Пример кода на C: 

unsigned int FNV1aHash (char *buf)
{	
  unsigned int hval = 0x811c9dc5;

  while (*buf)
    {
      hval ^= (unsigned int)*buf++;
      hval *= FNV_32_PRIME;
    }

  return hval;
}

Пример кода на Delphi: 

function FNV1aHash(const buf; len: Integer): LongWord;
var
  pb: PByte;
  i: Integer;
begin
  pb := PByte(@buf);
  Result := $811C9DC5;
  for i := len downto 1 do
  begin
    Result := (Result xor pb^) * $01000193;
    Inc(pb);
  end;
end;

Помимо вышеуказанной модификации были разработаны некоторые редакции алгоритма, улучшающие производительность. Примером таких функций являются FNV1A_Jesteress и FNV1A_Yorikke. Помимо работы над ускорением алгоритма, автор уделил внимание и качеству распределения[1].

Коллизии

Основная статья: Коллизия хеш-функции

Так как значение хеш-функции, приведённое в примере, 32-битное, вероятность появления коллизии значительно выше, чем у хеш-функций, возвращающих, к примеру, 128-битный хеш.

Ссылки

Примечания

  1. ↑ Модификации FNV и тестирование функции. Дата обращения: 10 ноября 2012. Архивировано 5 марта 2012 года.

Read other articles:

Alaska Peninsula

Peninsula extending towards the Aleutian Islands in Southwest Alaska, United States This article is about a region in Southwest Alaska. For the entire state, see Alaska. Map of Alaska Peninsula Volcanoes on the Alaska Peninsula Peulik Volcano and cottongrass meadow The Alaska Peninsula[1] (also called Aleut Peninsula[2] or Aleutian Peninsula,[3] Aleut: Alasxix̂; Sugpiaq: Aluuwiq, Al'uwiq) is a peninsula extending about 497 mi (800 km) to the southwest from t...

 

Northeastern Huskies football

Former college football team of Northeastern University For information on all Northeastern University sports, see Northeastern Huskies. Northeastern Huskies footballFirst season1933Last season2009StadiumParsons Field(capacity: 7,000)Field surfaceArtificial turfLocationBoston, MassachusettsNCAA divisionDivision I FCSConferenceColonial Athletic AssociationAll-time record289–366–17 (.443)Bowl record0–1 (.000)Conference titles1 (2002)RivalriesBoston University Terrier...

 

The Best of Missing Persons

1987 greatest hits album by Missing PersonsThe Best of Missing PersonsGreatest hits album by Missing PersonsReleased1987Recorded1980–1986GenreNew wave, synth-popLength60:26LabelCapitolProducerKen Scott, Terry Bozzio, Bruce Swedien, Jeff Bova, Bernard EdwardsMissing Persons chronology Color in Your Life(1986) The Best of Missing Persons(1987) Late Nights Early Days(1997) Professional ratingsReview scoresSourceRatingAllmusic[1] The Best of Missing Persons is a greatest hits al...

Haris Seferović

Haris Seferović Informasi pribadiTanggal lahir 22 Februari 1992 (umur 32)Tempat lahir Sursee, SwissTinggi 1,89 m (6 ft 2+1⁄2 in)Posisi bermain PenyerangInformasi klubKlub saat ini Eintracht FrankfurtNomor 9Karier junior1999–2004 Sursee2004–2007 Luzern2007–2009 GrasshopperKarier senior*Tahun Tim Tampil (Gol)2009–2010 Grasshopper 3 (0)2010–2013 Fiorentina 8 (0)2011–2012 → Neuchâtel Xamax (pinjaman) 10 (2)2012 → Lecce (pinjaman) 5 (0)2013 → Novara (...

 

Shahmeran Hamam

Historical hamam in Tarsus, Turkey 36°55′03″N 34°53′49″E / 36.91750°N 34.89694°E / 36.91750; 34.89694 This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Shahmeran Hamam – news · newspapers · books · scholar · JSTOR (May 2020) (Learn how and when to remove this template messag...

 

Человек прямоходящий

† Человек прямоходящий Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:Синапсиды�...

Daftar Bupati Barito Selatan

Berikut ini adalah Daftar Bupati Barito Selatan yang menjabat sejak pembentukannya pada tahun 1959.[1] No. Bupati[2] Mulai menjabat Akhir menjabat Ket. Wakil Bupati 1 Gomer Tamin Binti 1959 1961 Tidak ada 2 Benyamin A. Tidja 1961 1967 3 Urbanus Martjun S.H. 1967 1975 — Tunjung Silam 1975 1976 Penjabat sementara 4 Drs. H. Mangkusari 1976 1981 5 H. Kamberani Seman B.A. 1981 1986 1986 1991 6 Drs. H.Asmawi Agani 1991 1996 7 Ir. H. Achmad Diran 1996 2001 8 Ir. H. Baharuddin H. Li...

 

My Heart Will Go On

Untuk episode Supernatural, lihat My Heart Will Go On (Supernatural). My Heart Will Go OnSingel oleh Céline Diondari album Let's Talk About Love dan Titanic: Music from the Motion PictureDirilis8 Desember 1997 (1997-12-08)FormatSingel CD, singel 12, singel mini CD, singel kasetDirekamMay 1997 Wallyworld, The Hit FactoryGenrePop, simfoniDurasi4:40 (versi album)5:11 (versi soundtrack)LabelColumbia, EpicPenciptaJames Horner, Will Jennings[1]ProduserSimon Franglen, James Horner, Wal...

 

U.S. National Championships 1948

U.S. National Championships 1948 Sport Tennis Data 10 settembre - 19 settembre Edizione 68ª Categoria Grande Slam (ITF) Località New York e Chestnut Hill, USA Campioni Singolare maschile Pancho Gonzales Singolare femminile Margaret Osborne duPont Doppio maschile Gardnar Mulloy / Bill Talbert Doppio femminile Louise Brough / Margaret Osborne Doppio misto Louise Brough / Tom Brown 1947 1949 Gli U.S. National Championships 1948 (conosciuti oggi come US Open) sono stati la 68ª edizione degli ...

ماشين غان كيلي

ماشين غان كيلي   معلومات شخصية الميلاد 22 أبريل 1990 (34 سنة)[1]  هيوستن  الإقامة لوس أنجلوس  مواطنة الولايات المتحدة  العشير ميغان فوكس (يونيو 2020–)[2]  عدد الأولاد 1 [3]  الحياة الفنية النوع هيب هوب،  وبوب راب  [لغات أخرى]‏،  وراب روك،  وب...

 

Reaksi berantai polimerase

Alat pengatur siklus suhu yang biasanya digunakan pada teknik reaksi berantai polimeraseReaksi berantai polimerase (bahasa Inggris: polymerase chain reaction, disingkat PCR) adalah metode untuk menciptakan jutaan hingga miliaran salinan dari segmen asam deoksiribonukleat (DNA) tertentu, yang memungkinkan ilmuwan untuk melipatgandakan sampel DNA yang sangat sedikit hingga mencapai jumlah yang cukup untuk dipelajari secara detail. Metode ini ditemukan pada tahun 1983 oleh Kary Mullis, ahli biok...

 

周處除三害 (電影)

周處除三害The Pig, The Snake and The Pigeon正式版海報基本资料导演黃精甫监制李烈黃江豐動作指導洪昰顥编剧黃精甫主演阮經天袁富華陳以文王淨李李仁謝瓊煖配乐盧律銘林孝親林思妤保卜摄影王金城剪辑黃精甫林雍益制片商一種態度電影股份有限公司片长134分鐘产地 臺灣语言國語粵語台語上映及发行上映日期 2023年10月6日 (2023-10-06)（台灣） 2023年11月2日 (2023-11-02)（香�...

Casato di Rohan

Disambiguazione – Se stai cercando altri significati, vedi De Rohan. RohanÁ plusDi rosso a nove maglie d'oro, disposte 3, 3, 3.Stato Ducato di Bretagna Regno di Francia Francia Casata di derivazionePorhoët Titoli Principe di Guéméné Principe di Soubise Principe di Rochefort Principe di Léon Principe di Maubuisson Pari di Francia Duca di Rohan Duca di Montbazon Duca di Bouillon Duca di Frontenay Duca di Rohan-Rohan Duca di Loudun Conte di Rohan Conte di Montbazon Conte di Montaub...

 

Ahmad Bagdja

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Februari 2023. Ahmad BagdjaLahirAhmad Bagdja01 Maret 1945 (umur 79)Lebakwangi, Kuningan, Jawa Barat, Hindia BelandaMeninggal6 Februari 2020(2020-02-06) (umur 74)RS Jakarta Medical Center Daerah Khusus Ibukota Jakarta, IndonesiaKebangsaanIndonesiaPekerjaanu...

 

Madurai Veeran

For other uses, see Madurai Veeran (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Madurai Veeran – news · newspapers · books · scholar · JSTOR (August 2020) (Learn how and when to remove this message) Tamil folk hero Madurai VeeranA statue of Madurai Veeran in Salem, Tamil Nadu.WeaponSword...

Shimazu Tadayoshi (2nd)

Ini adalah nama Jepang, nama keluarganya adalah Shimazu. Shimazu Tadayoshi Shimazu Tadayoshi (島津忠義code: ja is deprecated , 22 Mei 1840 – 26 Desember 1897) adalah daimyō Jepang dari periode Edo akhir, yang memerintah Domain Satsuma sebagai daimyō ke-11 dan terakhir. Selama masa jabatannya, sebagian besar kekuatan politik di Satsuma dipegang oleh ayahnya, Hisamitsu. Keturunan Istri sah: Teruko, meninggal saat melahirkan 1869 Fusako (1869–1871) Istri kedua: Yasuko, me...

 

Wolfgang Neuss

For the German rower, see Wolfgang Neuß (rower). You can help expand this article with text translated from the corresponding article in German. (May 2022) Click [show] for important translation instructions. View a machine-translated version of the German article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting m...

 

Lasinavir

Lasinavir Names Systematic IUPAC name tert-Butyl (3S,4S,6R,9S)-13-benzyl-12-hydroxy-6,9-dioxo-7-(propan-2-yl)-10-[(2,3,4-trimethoxyphenyl)methyl]-2-oxa-5,8,14-triazapentadecan-15-oate Identifiers CAS Number 175385-62-3 Y 3D model (JSmol) Interactive image ChemSpider 408297 Y PubChem CID 464372 UNII 0QGV8237I3 Y InChI InChI=1S/C35H53N3O9/c1-22(2)29(33(41)36-17-18-43-6)38-32(40)25(20-24-15-16-28(44-7)31(46-9)30(24)45-8)21-27(39)26(19-23-13-11-10-12-14-23)37-34(42)47-35(3,4)5/h10...

Richmond High School (Richmond, California)

This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (May 2020) (Learn how and when to remove this message) Public school in California, United StatesRichmond High SchoolLocation1250 - 23rd St. RichmondCalifornia 94804510United StatesCoordinates37°57′07″N 122°20′32″W / 37.9518682°N 122.3421929°W / 37.9518682; -122.34219...

 

Grand Conseil du canton de Vaud

Grand Conseil Législature 2022-2027 Armoiries du canton de Vaud.Présentation Type Parlement cantonal Création 1803 Lieu Lausanne Durée du mandat 5 ans Présidence Président Laurent Miéville (Vert'libéraux) Élection 27 juin 2023 1re vice-président Jean-François Thuillard (UDC) Élection 27 juin 2023 2e vice-président Stéphane Montangero (PS) Élection 27 juin 2023 Structure Membres 150 députés Composition actuelle.Données clés Groupes politiques PLR (5...