A5HASH - Fast Hash Functions (in C/C++)

Introduction

The a5hash family of hash functions, available in the a5hash.h header file, provides high-performance hash functions, designed for hash-table, hash-map, and bloom-filter use cases. The code is portable, cross-platform, scalar, zero-allocation, header-only, inlinable C (compatible with C++). Released in open-source form under the MIT license.

The provided 64-bit and 128-bit hash functions of the a5hash family are compatible with 32-bit platforms, but their use there is not recommended due to reduced performance of a 64-bit multiplication. On 32-bit platforms it is recommended to use the available a5hash32() function which provides native 32-bit compatibility, if 32-bit hash values are sufficient.

The a5hash() 64-bit function achieves very high hashing throughput for small strings/messages (about 11 cycles/hash for 0-64-byte strings, hashed repeatedly on Zen 5). The bulk throughput is intentionally moderately fast (15 GB/s on Ryzen 9950X). Most recent competing "fast" hash functions aim to perform well both for common keyed string hash-maps and large data hashing. In most cases, this is done for the sake of better benchmark results, even though such hash functions rarely provide the streamed hashing required for large data or file hashing.

a5hash() was designed to be ultimately fast only for common string and small-key hash-maps, and hash-tables, by utilizing the "forced inlining" feature present in most modern C and C++ compilers: this is easily achievable, since in its compiled binary form, a5hash() is very small - about 270 to 330 bytes on x86-64 and arm64. Moreover, if the default seed (0) is used, or if data of a compile-time constant size is hashed, these conditions further reduce the code size and increase the hashing throughput.

Note that a5hash functions are not cryptographically secure. To minimize the risk of a successful collision attack (hash flooding) in open systems and in server-side internal structures, they should only be used with a secret seed, and their output should not be exposed. This is especially important if a malicious party is likely to try to influence the hash outputs. However, if "blinding multiplication" (BM, state cancellation) occurs at a random iteration, these functions immediately recover from the zeroed-out state (see below). a5hash functions should not be used for MACs or other strictly cryptographic purposes.

a5hash hash functions produce different hashes on big- and little-endian systems. This was a deliberate design choice to narrow down the scope of use cases to run-time hashing and embedded storage, as endianness correction usually imposes a significant performance penalty. If a reliable and fast hash function for files, with portable hashes, is needed, komihash is a great choice.

Overall, a5hash achieves three goals: attains an ultimate speed for run-time hashing of small keys, has very small code size, and uses a novel mathematical construct. Compared to most, if not all, existing hash functions, a5hash hash functions do not use explicit accumulators or folding of state variables: the full 128-bit result of multiplication is used directly as input on the next iteration. This construction appears to be near the minimal complexity required for high-quality hashing (in the SMHasher testing sense). Such a conclusion stems from the fact that the a5hash() function is structurally simple, and further reduction of the number of operations seems impossible, while other existing similarly simple constructs like xorshift do not provide high-quality hashing.

a5hash hash functions pass all SMHasher and SMHasher3 tests. The functions were also tested using the xxHash collision tester at various settings, with collision statistics meeting theoretical expectations.

These functions and the source code (which conforms to ISO C99) were quality-tested on: Clang, GCC, MSVC, and Intel C++ compilers; x86, x86-64 (Intel, AMD), and AArch64 (Apple Silicon) architectures; Windows 11, AlmaLinux 9.3, and macOS 15.3.2. Full C++ compliance is enabled conditionally and automatically when the source code is compiled with a C++ compiler.

Usage

Simply copy a5hash.h into a project. It is a header-only library.

#include <stdio.h>
#include "a5hash.h"

int main(void)
{
    const char s1[] = "This is a test of a5hash.";
    const char s2[] = "7 chars";

    printf( "0x%016llx\n", a5hash( s1, strlen( s1 ), 0 )); // 0xa04d5b1d10d1f246
    printf( "0x%016llx\n", a5hash( s2, strlen( s2 ), 0 )); // 0xe49a0cc72256bbac
}

As a bonus, the a5hash.h file provides the a5hash_umul128() general-purpose inline function which implements a portable unsigned 64x64 to 128-bit multiplication.

A5HASH-128

The a5hash128() function produces 128-bit hashes, and, compared to 64-bit a5hash() function, features a significantly higher performance for large data hashing - 48 GB/s on Ryzen 9950X. It is also fairly fast for use in hash-maps, but a bit slower than the a5hash() function. Among 128-bit hashes that pass the state-of-the-art tests, it's likely the fastest 128-bit hash function for hash-maps.

By setting the function's rh pointer argument to 0, NULL, or nullptr (in C++), it can also be used as a 64-bit hash function with high bulk throughput.

#include <stdio.h>
#include "a5hash.h"

int main(void)
{
    const char s1[] = "This is a test of a5hash128.";
    uint64_t h[ 2 ];

    h[ 0 ] = a5hash128( s1, strlen( s1 ), 0, h + 1 );

    printf( "0x%016llx%016llx\n", h[ 0 ], h[ 1 ]); // 0xdd2f427007acd1b23609225842ec8020
}

Comparisons

The benchmark was performed using SMHasher3 (commit 7be7e9e820724779926c052db41c15bf88d5863b) on a Xeon E-2386G (Rocket Lake) running AlmaLinux 9.3. This benchmark includes only the fastest hash functions that pass all state-of-the-art tests. XXH3-64 here does not, but it is too popular to exclude it. rapidhash source code explicitly notes it is based on wyhash.

Small-key speed values are in cycles per hash, while other values are in cycles per operation. std init and std run are std::unordered_map init and running tests, par init and par run are greg7mdp/parallel-hashmap init and running tests. All values are averages over 10 runs.

| Hash function | Small-key speed | std init | std run | par init | par run | |---------------|-----------------|----------|---------|----------|---------| | a5hash | 11.50 | 523 | 404 | 294 | 277 | | rapidhash | 18.10 | 526 | 430 | 308 | 292 | | rust-ahash-fb | 19.33 | 533 | 429 | 286 | 304 | | XXH3-64 | 21.31 | 533 | 428 | 292 | 290 | | komihash | 22.54 | 539 | 434 | 285 | 296 | | polymurhash | 28.44 | 537 | 458 | 335 | 335 |

Customizing C++ namespace

In C++ environments where it is undesirable to export a5hash symbols into the global namespace, the A5HASH_NS_CUSTOM macro can be defined externally:

#define A5HASH_NS_CUSTOM a5hash
#include "a5hash.h"

Similarly, a5hash symbols can be placed into any other custom namespace (e.g., a namespace with hash functions):

#define A5HASH_NS_CUSTOM my_hashes
#include "a5hash.h"

This way, a5hash functions can be referenced like my_hashes::a5hash(...). Note that since all a5hash functions have the static inline specifier, there can be no ABI conflicts, even if the a5hash.h header is included in unrelated, mixed C/C++, compilation units.

Seeding

All a5hash functions can be seeded with values of any statistical quality. However, a resistance against hash flooding requires the seeds to be maximum-entropy, uniformly random values.

A5RAND

The a5rand() function available in the a5hash.h file implements a simple, but reliable, self-starting, and fast (0.50 cycles/byte) 64-bit pseudo-random number generator (PRNG) with a 2^64 period. It is based on the same mathematical construct as the a5hash() hash function. a5rand() passes PractRand tests (at least up to 1 TB length, at the default settings) and SmokeRand tests (full setting).

#include <stdio.h>
#include "a5hash.h"

int main(void)
{
    uint64_t Seed1 = 0, Seed2 = 0;
    int i;

    for( i = 0; i < 8; i++ )
    {
        printf( "%016llx\n", a5rand( &Seed1, &Seed2 ));
    }
}

Output:

2492492492492491
83958cf072b19e08
1ae643aae6b8922e
f463902672f2a1a0
f7a47a8942e378b5
778d796d5f66470f
966ed0e1a9317374
aea26585979bf755

Design Analysis

Why A5?

The constants 0xAAAA... and 0x5555... used in a5hash() and a5rand() represent repetitions of 10 and 01 bit-pairs over register. While they do not look special as adders in PRNGs, or even look controversial due to the absence of bit-wise spectral information, they have the important property of substantially reducing internal biases of any given number.

Consider this code, which calculates the sum of internal successive bit independence estimates of a set of numbers, and the same for set's numbers XORed and summed with the 0xAAAA constant, if a set number's successive bit independence is low. The output shows that the estimates are higher for numbers that have been XORed or added with the constant. Other statistically uniform constants also increase the estimates, but to a lesser extent, making the 0xAAAA... and 0x5555... constants special.

This example empirically explains why both a5hash() and a5rand() generate high-quality random numbers despite their reliance on multiplicatio