Using the FNV in HeFS.

The FNV (Fowler–Noll–Vo) hash function is a non-cryptographic hash function that is widely used for hash tables, checksums, and hash-based data structures. In HeFS, I use the FNV to compute hashes of file names and other identifiers.

Why?

It's much faster to compute and lookup than full UTF-8 names, it also opens the door for UTF-16 and UTF-32 names too.

How?

Using the FNV (64-bit FNV prime) is straightforward. Here's a simple implementation in C++:

#include <cstdint>
#include <string>

static uint64_t fnv_hash(const std::string& str) {
    if (str.empty()) return 0;

		const uint64_t FNV_OFFSET_BASIS = 0xCBF29CE484222325;
    const uint64_t FNV_PRIME = 0x100000001B3;
    
    uint64_t hash = FNV_OFFSET_BASIS;
    
    for (char& c : str) {
        hash ^= static_cast<uint64_t>(c);
        hash *= FNV_PRIME;
    }
    
    return hash;
}

Not suitable for production use, but it gives you an idea of how to compute the FNV hash. In HeFS, I use a more optimized version that handles UTF-8 strings and is designed for performance.

See STATIC UInt64 hefsi_hash_64(const Utf8Char* path) in HeFS+FileSystemParser.cpp for the actual implementation.

Where?

It is hosted in the NeKernel's repository in the HeFS source code, specifically in the HeFS+FileSystemParser.cpp file.

Conclusion

The FNV hash function is a powerful tool for efficiently handling file names and identifiers in HeFS. Its speed and simplicity make it an ideal choice for this purpose, allowing for quick lookups and minimal overhead in file system operations. NeKernel.org is an open-source project, and contributions are welcome. If you have suggestions or improvements for the FNV implementation or HeFS in general, feel free to contribute to the repository.