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

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

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

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

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

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

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

FNV-1 алгоритм үүнийг хэрхэн хийдгийг хэд хэдэн алхмаар тайлбарлая:

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

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

Алхам 2: Орцуудыг Нэг нэгээр нь Нэмэх (Өгөгдөл боловсруулах)

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

Алхам 3: Нууц Үржүүлэгчтэй Хольж Боловсруулах (FNV Prime)

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

Алхам 4: Шидэт Тоос Шархлах (XOR үйлдэл)

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

Алхам 5: Дахин Давтан Хийх

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

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

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

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