Python icon indicating copy to clipboard operation
Python copied to clipboard

Add FNV-1a hash algorithm implementation

Open rodrigobnogueira opened this issue 3 weeks ago • 0 comments

Description

Implements the FNV-1a (Fowler-Noll-Vo) hash algorithm with both 32-bit and 64-bit variants. FNV-1a is a fast, non-cryptographic hash function widely used in hash tables, bloom filters, and caches.

Changes

  • Added hashes/fnv.py with complete implementation of:
    • fnv1a_32(): 32-bit variant
    • fnv1a_64(): 64-bit variant
  • Simple XOR-multiply algorithm
  • 22 comprehensive doctests (11 per variant)
  • Full type hints and English documentation

Features

  • Extremely simple and fast implementation
  • Excellent distribution properties
  • Used in popular systems (hash tables, databases)
  • Complements existing hash algorithms (CRC32, MD5, SHA)

Real-world Applications

  • Hash tables and hash maps
  • Bloom filters
  • Database indexing
  • Cache implementations
  • Checksums for data integrity

References

  • https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
  • http://www.isthe.com/chongo/tech/comp/fnv/

Testing

  • All 22 doctests pass
  • Passes ruff linting
  • Passes mypy type checking
  • Tested with various inputs including edge cases

Checklist

  • [x] I have read and followed the contributing guidelines
  • [x] This pull request is not a duplicate
  • [x] The algorithm is implemented from scratch
  • [x] The code follows the repository style
  • [x] I have read CONTRIBUTING.md
  • [x] This pull request is all my own work -- I have not plagiarized
  • [x] I know that pull requests will not be merged if they fail the automated tests
  • [x] This PR only changes one algorithm file
  • [x] All new Python files are placed inside an existing directory (hashes/)
  • [x] All filenames are in all lowercase characters with no spaces or dashes
  • [x] All functions and variable names follow Python naming conventions
  • [x] All function parameters and return values are annotated with Python type hints
  • [x] All functions have doctests that pass the automated testing
  • [x] All new algorithms include at least one URL that points to Wikipedia or another similar explanation

rodrigobnogueira avatar Dec 25 '25 18:12 rodrigobnogueira