Step 2: hash function
// hash_table.c
// https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
// algorithm fnv-1a is
// hash := FNV_offset_basis
// for each byte_of_data to be hashed do
// hash := hash XOR byte_of_data
// hash := hash × FNV_prime
// return hash
uint64_t hash(const char* key) {
uint64_t hash = FNV_offset_basis;
int len = strlen(key);
for (int i=0; i<len; ++i) {
hash ^= key[i];
hash *= FNV_prime;
}
return hash;
}
XOR(Exclusive or) is a logical operator that works on bits. Let’s denote it by ^. If the two bits it takes as input are the same, the result is 0, otherwise it is 1. This implements an exclusive or operation, i.e. exactly one argument has to be 1 for the final result to be 1. We can show this using a truth table:
Screenshot 2023-12-29 at 5.26.30 PM.png
Most programming languages implement ^ as a bitwise operator, meaning XOR is individually applied to each bit in a string of bits (e.g. a byte).
Some Useful Properties
- a ^ a = 0
- a ^ 0 = a
- a ^ b = b ^ a
- a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
- a ^ b ^ a = a ^ a ^ b = b
Those can all be checked though truth table, but I haven't looked into the mathematical proof
An interesting application for XOR in leetcode: https://leetcode.com/problems/single-number/description/
class Solution {
public:
int singleNumber(vector<int>& nums) {
if (nums.size() == 1){
return nums[0];
}
// a ^ a = 0
// a ^ b = b ^ a;
// a ^ b ^ c = a ^ (b ^ c) = (a ^ c ) ^ b
int ans = 0;
for (int i = 0; i < nums.size(); i++){
ans ^= nums[i];
}
return ans;
}
};
