Fowler-Noll-Vo FNV1-64 Хэш кодын тооцоолуур

FNV-1 64 битийн хэш функц нь Fowler–Noll–Vo (FNV) хэш функцүүдийн гэр бүлийн нэг хэсэг бөгөөд хэш утгын сайн хуваарилалтыг хадгалахын зэрэгцээ хурдан хэш хийх зориулалттай. Энэ нь ихэвчлэн хэш хүснэгт, шалгах нийлбэр, өгөгдөл хайх зэрэг програмуудад ашиглагддаг. Энэ нь 64 бит (8 байт) хэш код үүсгэдэг бөгөөд ихэвчлэн 16 оронтой арван арван тоогоор илэрхийлэгддэг.

Бүрэн тодруулга: Би энэ хуудсанд ашигласан хэш функцийн тодорхой хэрэгжилтийг бичээгүй. Энэ нь PHP програмчлалын хэлэнд багтсан стандарт функц юм. Би зөвхөн вэб интерфэйсийг энд олон нийтэд нээлттэй болгох үүднээс хийсэн.

Fowler-Noll-Vo FNV-1 64 бит Хэш Алгоритмын Тухай

Би математикийн шинжлэх ухааны хүн биш ч энэ хэш функцийн талаар өөрийн таньдаг хүмүүс ойлгохуйц нэгэн жишээгээр тайлбарлахыг хичээнэ. Хэрвээ та шинжлэх ухааны хувьд зөв, аймшигтай математик тайлбар хүсч байвал, та үүнийг хаа нэгтээ олж чадна ;-)

Юуны өмнө, FNV-1 алгоритмыг тусгай смүүти бэлтгэх жор гэж бодоод үзье. Та бүрдүүлж байгаа бүртгэл бүр (жишээ нь жимс, сүү, эсвэл бал) нь өгөгдлийн нэг хэсэг (жишээ нь үсэг, тоо эсвэл бүрэн файл) гэсэн утгатай.

Одоо, зорилго нь эдгээр бүрдэл хэсгүүдийг маш тодорхой аргаар холино гэж төсөөлөөд үзье. Тиймээс жорын хамгийн жижиг өөрчлөлт ч (жишээ нь нэг илүү тоор жимс нэмэх) смүүтийн амтыг бүрэн өөрчилнө. Энэ нь хэш функцийн ажиллах арга - тэд бүх уникаль бүрдэл хэсгүүдийн (эсвэл оруулах өгөгдлийн) хувьд нэгэн төрлийн "амт" (эсвэл хэш утга) үүсгэдэг.

FNV-1 алгоритм үүнийг олон шаттай процессыг ашиглан хийдэг:

Алхам 1: Сууриа эхлэх (Offset Basis)

Энэ нь таны холигчид тусгай смүүтигийн суурь хийж байгаа юм шиг төсөөлөөд үзье. Энэ суурь нь ямар ч бүрдэл хэсэг нэмсэн ч өөрчлөгдөхгүй, үргэлж нэгэн ижилхэн байна. FNV-1-д үүнийг "offset basis" гэж нэрлэдэг - зөвхөн эхлүүлэх тоо юм.

Алхам 2: Бүрдэл хэсгүүдийг нэг бүрчлэн нэмэх (Өгөгдөл боловсруулах)

Одоо та бүрдэл хэсгүүдээ нэг нэгээр нь нэмнэ - жишээ нь, нэг төрлийн тоор жимс, дараа нь нэг банан, дараа нь жаахан бал. Эдгээр бүрдэл хэсэг бүр нь өгөгдлийн нэг байт юм.

Алхам 3: Нууц үржүүлэгчтэй холих (FNV Prime)

Бүрдэл хэсгүүдийг нэмсний дараа, холих товчлуурыг дарах болно, гэхдээ энд нэг өөрчлөлт байна: холигч нь бүх зүйлсийг нууц "шидэт тоо" гэж нэрлэгдэх FNV prime -ээр үржүүлнэ. Энэ нь бүх зүйлсийг сайн холино.

Алхам 4: Шидэт нунтаг нэмэх (XOR үйлдэл)

Дараагийн бүрдэл хэсэг нэмэхээс өмнө, та бага зэрэг шидэт нунтаг нэмнэ (энэ нь XOR үйлдэл юм). Энэ нь амтыг санаандгүйгээр эргүүлж, жижиг өөрчлөлтүүд ч том өөрчлөлт хийхийг баталгаажуулна.

Алхам 5: Дуусах хүртэл давтана

Та бүх бүрдэл хэсэг нэмсэн болгоны дараа холих, шидэт нунтаг нэмсээр байгаад бүхнийг боловсруулна.

Алхам 6: Эцсийн смүүти (Хэш утга)

Харин та дууссан үедээ смүүтигээ цутгана. Эцсийн амт (хэш утга) нь тухайн нарийн бүрдэл хэсгүүдийн яг түүхий хослолд онцгой байдаг. Хэрвээ та бүр нэг илүү тоор жимс нэмсэн бол амт нь бүрэн өөрчлөгдөх байсан.

Энд танилцуулсан хувилбар нь анхны FNV-1 64 бит хувилбар юм. Мөн сайжруулсан FNV-1a 64 бит хувилбар бас байдаг: Fowler-Noll-Vo FNV1a-64 Хэш кодын тооцоолуур