Simplest Hash Functions
5 days ago
- #non-cryptographic hashing
- #hash functions
- #performance optimization
- The article discusses non-cryptographic hash functions designed for speed and simplicity rather than security.
- It introduces rapidhash, a fast but insecure hash that uses XOR and multiplication, and warns against using it with adversarial input due to potential collisions.
- Simpler hash functions based on addition or addition with rotation are suggested for non-adversarial scenarios like processing static data or in retrocomputing.
- The article emphasizes that while these minimal hash functions are not secure, they can be suitable for specific use cases where HashDoS attacks are not a concern.
- It explains hash table basics, highlighting the importance of good hash functions for even distribution of entries across buckets to ensure fast access.
- The addition hash is tested on real data, showing acceptable bit probability and collision performance, though its weaknesses are exposed with structured inputs like domain names.
- Multiplication-based hashing, such as folded multiplication, is presented as a more effective way to spread entropy and reduce collisions.
- The article notes that modern hash tables often use the low bits of hashes for indexing, which influences hash function design choices like using rotation to move entropy downward.
- A recipe for a simple hash function is provided, suggesting using fast operations like addition, XOR, and multiplication, and considering hardware instructions for better performance.
- The tone is playful and exploratory, encouraging readers to consider trade-offs between security, speed, and simplicity in hash function selection.