Last active
January 3, 2024 15:12
-
-
Save ttarchala/851a91a046aa88daf41ee062156e4f30 to your computer and use it in GitHub Desktop.
Excel hash function FNV-1a 32-bit
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // FNV1a: a 32-bit hash function | |
| // Accepts any input: string, number or bool. Returns 8 hex characters, or 0 if input is empty. | |
| // example of use: | |
| // =FNV1a("Hello world") | |
| // -> yields "594D29C7" | |
| // =FNV1a(42) | |
| // -> yields "87E38583" | |
| // | |
| // based on this SuperUser answer by Jason Kleban: | |
| // https://superuser.com/a/1720348/7659 | |
| FNV1a = LAMBDA(s, | |
| LET( | |
| Y, LAMBDA(G, a, b, m, res, | |
| IF( | |
| 0 < b, | |
| G(G, MOD(a, m) * 2, TRUNC(b / 2), m, IF(MOD(b, 2) = 1, MOD(res + MOD(a, m), m), res)), | |
| res | |
| ) | |
| ), | |
| mulmod, LAMBDA(a, b, m, Y(Y, a, b, m, 0)), | |
| p, 16777619 + N("FNV_prime for 32 bits"), | |
| o, 2166136261 + N("FNV_offset_basis for 32 bits"), | |
| m, POWER(2, 32) + N("modulus for 32 bits"), | |
| IF( | |
| ISBLANK(s), | |
| 0, | |
| DEC2HEX( | |
| REDUCE( | |
| o, | |
| ROW(INDIRECT("1:" & LEN(s))), | |
| LAMBDA(acc, i, mulmod(p, BITXOR(acc, CODE(MID(s, i, 1))), m)) | |
| ) | |
| ) | |
| ) | |
| ) | |
| ) |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Note: more than a couple of thousand entries, the 32-bit hash gives me too many collisions. I wanted to extend this to 64-bit, but that's too much for Excel integer handling capacity... So I am ready settle for 48-bit, but can't find a good FNV prime and offset for 48-bit. Any idea what they would be?