Introduction

Hashing is a fundamental concept in computer science used to uniquely represent objects, perform efficient data retrieval, and manage sets or dictionaries. When dealing with unordered sequences of small integers, specialized hashing techniques can be optimized to improve performance and reduce collisions. This article explores various methods for hashing such sequences, explains the technical tradeoffs, and provides concrete examples.

Basics of Hashing

Hashing transforms an input (or key) into a fixed-size hash code through a hash function. A good hash function must satisfy two properties:

1. Determinism: The same input always produces the same hash value.
2. Uniformity: Different inputs distribute evenly over the hash space to minimize collisions.

Hash collisions occur when different inputs produce the same hash value, leading to degraded performance in hash-based data structures.

The Core Challenge: Order Independence

When hashing an unordered sequence (a multiset), the hash function must be commutative. Sequences containing the same elements in different orders must produce the same hash value. For example, {3, 1, 2} and {2, 3, 1} must hash identically.

This rules out standard approaches like hashing concatenated elements or using position-dependent calculations. Instead, we need operations that are inherently order-independent.

Techniques for Order-Independent Hashing

1. XOR-Based Hashing

XOR each element's individual hash together. Since XOR is both commutative and associative, the result is order-independent:

$$H = h(a_1) \oplus h(a_2) \oplus \ldots \oplus h(a_n)$$

Pros: Simple and fast ($O(n)$ time).

Cons: XOR has a critical weakness. Duplicate elements cancel out because $x \oplus x = 0$. The multisets {1, 1, 2} and {2} would hash identically. This makes XOR unsuitable when duplicates matter.

2. Summation-Based Hashing

Sum the individual element hashes:

$$H = \sum_{i=1}^{n} h(a_i)$$

This handles duplicates correctly since $h(x) + h(x) \neq h(x)$ in general. However, it is more prone to accidental collisions compared to multiplicative approaches, since many different multisets can produce the same sum.

3. Prime Product Hashing

Assign each possible integer value a distinct prime number and compute the product:

$$H = \prod_{i=1}^{n} p(a_i)$$

where $p(k)$ maps integer $k$ to the $k$-th prime number. By the fundamental theorem of arithmetic, the product uniquely identifies the multiset (up to overflow). For small integers, you can precompute a prime table:

1PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
2
3def multiset_hash(seq):
4    result = 1
5    for x in seq:
6        result *= PRIMES[x]
7    return result
8
9# {1, 2, 3} and {3, 1, 2} both produce 3 * 5 * 7 = 105

Pros: Collision-free for multisets (within overflow limits), handles duplicates correctly.

Cons: Products grow quickly. For large sequences, you need modular arithmetic, which reintroduces collision possibility.

4. Sorted Canonical Form

Sort the sequence and then apply any standard hash function to the sorted result. Sorting is the simplest conceptual approach:

def canonical_hash(seq):
    return hash(tuple(sorted(seq)))

Pros: Straightforward, leverages existing hash functions.

Cons: Sorting adds $O(n \log n)$ overhead. For small integer ranges, counting sort reduces this to $O(n + k)$ where $k$ is the range of values.

5. Counting Vector Hashing

Since the integers are small, represent the multiset as a frequency vector and hash the vector:

1def counting_hash(seq, max_val):
2    counts = [0] * (max_val + 1)
3    for x in seq:
4        counts[x] += 1
5    return hash(tuple(counts))

This runs in $O(n + k)$ time and $O(k)$ space, where $k$ is the range of integer values. It is highly efficient when $k$ is small.

Comparison of Methods

Practical Considerations

• Hash quality: For practical use, combine a commutative aggregation (sum or product) with a strong per-element hash function (like MurmurHash or xxHash) to reduce collision probability.
• Overflow handling: With prime products, use modular arithmetic ($H \mod M$ for a large prime $M$) to keep values bounded.
• Small integer range: When the range of possible values is small, the counting vector approach is often the most practical. It avoids sorting overhead and naturally handles duplicates.

Applications

• Data deduplication: Identify identical datasets regardless of element ordering.
• Database query optimization: Hash-based grouping of multiset-valued columns.
• Game state hashing: Board positions where piece order does not matter (e.g., Zobrist hashing in chess uses XOR for incremental updates).
• Chemical compound identification: Molecular formulas are essentially multisets of atoms.

Summary

Hashing unordered sequences of small integers requires order-independent hash functions. For most practical purposes, prime product hashing or counting vector hashing provides the best combination of correctness and efficiency. XOR is fast but fails with duplicates. Summation works but has higher collision risk. The canonical sort approach is simple but adds sorting overhead. Choose the method based on your constraints around duplicate handling, integer range, and performance requirements.