Crafting Custom Hash Functions in Python

Hash functions are fundamental to data structures like hash tables and dictionaries, enabling efficient data retrieval. This challenge asks you to implement several different hash functions in Python, exploring various techniques for mapping data to integer hash values. Understanding these techniques is crucial for optimizing performance and avoiding collisions in hash-based data structures.

Problem Description

Your task is to implement three distinct hash functions in Python:

1. Polynomial Rolling Hash: This function uses a polynomial expression to calculate the hash value. It's commonly used for string hashing and is relatively robust against collisions.
2. FNV-1a Hash: The Fowler–Noll–Vo (FNV) hash is a non-cryptographic hash function known for its speed and good distribution. You'll implement the FNV-1a variant.
3. Simple Modulo Hash: A basic hash function that calculates the hash value by taking the modulo of the input with a prime number. This is a good starting point for understanding hash function concepts.

Each function should accept a string as input and return an integer hash value. The functions should be designed to minimize collisions for common string inputs.

Examples

Example 1: Polynomial Rolling Hash

Input: "hello"
Output: 102387654 (Example - actual value will depend on the prime and base used)
Explanation: The hash is calculated using a polynomial expression with a base and a prime modulus. Each character's ASCII value is multiplied by a power of the base and summed, then taken modulo the prime.

Example 2: FNV-1a Hash

Input: "world"
Output: 2305727487 (Example - actual value will depend on the initial prime)
Explanation: The FNV-1a hash function iterates through the string, XORing the current hash value with the ASCII value of each character and then multiplying by a prime number.

Example 3: Simple Modulo Hash

Input: "python"
Output: 7 (Example - actual value will depend on the prime modulus used)
Explanation: The ASCII value of the string is summed, and then the modulo operation is performed with a prime number.

Constraints

• Input: The input to each hash function will be a string containing only ASCII characters.
• Output: Each hash function must return an integer.
• Prime Numbers: You should use prime numbers for the modulus in the Polynomial Rolling Hash and Simple Modulo Hash functions. A good choice for the Polynomial Rolling Hash is 101, and for the Simple Modulo Hash, 101 or 1009 are suitable. For FNV-1a, use the standard prime values.
• Base: For the Polynomial Rolling Hash, a base of 31 is commonly used.
• FNV-1a Constants: For the FNV-1a hash, use the standard initial prime (16777619) and the FNV prime (1099511627776).
• Collision Resistance: While perfect collision resistance is impossible, strive to minimize collisions for common string inputs.
• Performance: The hash functions should be reasonably efficient. Avoid unnecessary computations.

Notes

• Consider the potential for integer overflow when calculating hash values. Using the modulo operator (%) after each step can help prevent this.
• The choice of prime number and base significantly impacts the distribution of hash values and the likelihood of collisions. Experiment with different values to observe their effects.
• The FNV-1a hash function is designed to be fast and provide good distribution. Pay close attention to the standard algorithm when implementing it.
• Focus on clarity and readability in your code. Include comments to explain your logic.
• Test your hash functions with a variety of inputs, including empty strings, short strings, long strings, and strings with repeated characters, to ensure they behave as expected.