Cross-language hashing: inconsistent empty-byte and signed-zero handling

[tisonkun]

While documenting cross-language input handling in apache/datasketches-rust#340, I found two inconsistencies in the Java and C++ implementations: empty byte inputs and signed floating-point zero. A Bloom filter written in Java can be read successfully in C++, but querying an item that was inserted in Java can return false. As in the Count-Min discussion, it would help to agree on the input contract and compatibility implications before changing implementations.

1. What happens

The reproduction below writes two separate Bloom filters in Java, each containing one item, then reads them in C++. Both use 1,024 bits, three hashes, and seed 9001.

Inserted item in Java	Java query for that item	C++ query after reading the same image
Empty byte[]	true	false
-0.0	true	false

These results were reproduced against Java ef440a8 and C++ c22f2b1, using JDK 25 and a C++17 compiler on little-endian hardware. The scope here is these source revisions; this is not a release-by-release or all-language audit.

2. Empty byte inputs

Here, an empty byte input means Java new byte[0] or a non-null C++ pointer with length zero. It does not mean a null pointer or an empty sketch.

Family	Java empty-byte update	C++ zero-length byte update	Source
HLL	Ignores it	Hashes and updates	Java, C++
CPC	Ignores it	Hashes and updates	Java, C++
Theta	Ignores it	Hashes and updates	Java, C++
Tuple keys	Ignores them	Hashes and updates	Java, C++
Bloom	Hashes and inserts	Ignores it	Java, C++
XOR	Hashes and inserts	No implementation at this revision	Java
Count-Min V1	Ignores it	Hashes and updates	Java, C++

The corresponding string update APIs skip empty strings in both languages. Thus an empty string and its zero-length byte encoding can also behave differently within one implementation.

For Bloom, C++ returns false for a zero-length byte query before hashing or inspecting the filter. Java performs the query normally. This also applies to queries combined with insertion. The serialized bits cannot resolve a query that returns before looking at them.

The Count-Min V2 proposal already specifies ignoring empty strings and byte arrays and returning zero for queries. That is a useful explicit contract for V2; the legacy V1 row above describes the checked implementation, not the V2 proposal.

3. Signed zero

Java's Double.doubleToLongBits canonicalizes NaNs but preserves the sign of zero:

+0.0 -> 0x0000000000000000
-0.0 -> 0x8000000000000000

The Java Bloom and XOR floating-point APIs pass these bits directly to xxHash64. Java HLL, CPC, Theta, and Tuple first normalize zero, effectively doing value == 0.0 ? 0.0 : value, then call Double.doubleToLongBits. C++ HLL, CPC, Theta, Tuple, and Bloom also normalize signed zero.

Family	Java	C++
HLL, CPC, Theta, Tuple	Maps both zeros to +0.0	Maps both zeros to +0.0
Bloom	Preserves the two bit patterns	Maps both zeros to +0.0
XOR	Preserves the two bit patterns	No implementation at this revision

Sources: Java Bloom, Java XOR, Java HLL, and C++ Bloom.

In the Bloom reproduction, Java sets the bits for -0.0. C++ reads the image, converts a -0.0 query to +0.0, and probes different positions. This is a mismatch in the bytes passed to the hash, not in xxHash64 itself. XOR demonstrates the same Java signed-zero convention, but is not a Java/C++ comparison because there is no C++ XOR implementation at the checked revision. Count-Min V2 does not define floating-point inputs.

4. Minimal reproduction

Save this as Repro.java. It writes the two Bloom images and also shows Java XOR's signed-zero behavior.

import java.nio.file.Files;
import java.nio.file.Path;
import org.apache.datasketches.filters.bloomfilter.BloomFilterBuilder;
import org.apache.datasketches.filters.xorfilter.XorFilterBuilder;

public class Repro {
  public static void main(String[] args) throws Exception {
    Path output = Path.of(args[0]);
    Files.createDirectories(output);

    var bytes = BloomFilterBuilder.createBySize(1024, 3, 9001);
    bytes.update(new byte[0]);
    System.out.println("Java Bloom empty bytes: " + bytes.query(new byte[0]));
    Files.write(output.resolve("empty-bytes.sk"), bytes.toByteArray());

    var zero = BloomFilterBuilder.createBySize(1024, 3, 9001);
    zero.update(-0.0);
    System.out.println("Java Bloom -0.0: " + zero.query(-0.0));
    System.out.println("Java Bloom +0.0: " + zero.query(+0.0));
    Files.write(output.resolve("negative-zero.sk"), zero.toByteArray());

    var xor = new XorFilterBuilder(16, 9001).update(-0.0).build();
    System.out.println("Java XOR -0.0: " + xor.query(-0.0));
    System.out.println("Java XOR +0.0: " + xor.query(+0.0));
  }
}

Save this as repro.cpp. It reads the exact images written by Java.

#include <fstream>
#include <iostream>
#include <string>
#include "bloom_filter.hpp"

int main(int argc, char** argv) {
  if (argc != 2) return 1;
  const std::string directory = argv[1];
  std::ifstream bytes_input(directory + "/empty-bytes.sk", std::ios::binary);
  std::ifstream zero_input(directory + "/negative-zero.sk", std::ios::binary);
  if (!bytes_input || !zero_input) return 1;
  auto bytes = datasketches::bloom_filter::deserialize(bytes_input);
  auto zero = datasketches::bloom_filter::deserialize(zero_input);

  const char backing = 0; // Non-null pointer; the byte input length is zero.
  std::cout << std::boolalpha
            << "C++ Bloom empty bytes: " << bytes.query(&backing, 0) << '\n'
            << "C++ Bloom -0.0: " << zero.query(-0.0) << '\n'
            << "C++ Bloom +0.0: " << zero.query(+0.0) << '\n';
}

Set JAVA_REPO and CPP_REPO to checkouts of the revisions above. From a separate directory containing the two source files, run:

mkdir -p classes
find "$JAVA_REPO/src/main/java" -name '*.java' > sources.txt
javac -d classes @sources.txt
java --class-path classes Repro.java images

c++ -std=c++17 \
  -I"$CPP_REPO/common/include" \
  -I"$CPP_REPO/filters/include" \
  repro.cpp -o repro
./repro images

Observed output:

Java Bloom empty bytes: true
Java Bloom -0.0: true
Java Bloom +0.0: false
Java XOR -0.0: true
Java XOR +0.0: false
C++ Bloom empty bytes: false
C++ Bloom -0.0: false
C++ Bloom +0.0: false

The false results for the empty-byte and -0.0 queries in C++ are for items that were actually inserted in Java. Deserialization succeeds in both cases.

5. Compatibility and possible next steps

I suggest agreeing on the input contract before adapting one implementation to another's current behavior:

1. Specify empty-string, empty-byte, and signed-zero handling for each interoperable family, including both updates and queries. We should say explicitly whether empty byte sequences are valid items, and whether floating-point -0.0 and +0.0 represent one item or two.
2. Add TCK cases that query images produced by another language for these boundary inputs. Byte round trips alone would not catch these failures. Include empty strings, empty byte sequences, both signs of zero, and multiple NaN payloads as controls for floating-point normalization.
3. Choose a compatibility plan before changing an existing input encoding. For example, if Java Bloom starts normalizing zero, old images containing only -0.0 still contain the old hash positions. Simply changing the update/query code would not migrate those images. Conversely, changing a reader's empty-input policy changes what it can query in existing images. We should decide whether explicit legacy handling, a format/version distinction, or a documented limitation is needed.

The Rust PR linked above documents input strategies and empty-input handling; it does not change runtime hashing behavior. Rust's existing canonical_float continues to normalize both signed zero and NaNs.

6. Questions for the community

• Are these input distinctions intentional, or should the cross-language contract align them?
• Should empty byte sequences follow the existing empty-string convention for each family, or be treated as real items? Should Bloom and XOR normalize signed zero like HLL, CPC, Theta, and Tuple?
• Which compatibility policy should apply to existing serialized images if we change these rules?
• Can we capture the agreed behavior in the TCK before making corresponding implementation changes?

[leerho]

Thank you, Tison, this is an excellent and thoughtful summary of a very important issue!

There are a number of compatibility cases that need to be handled explicitly:

Hashing Floating Point:

• canonicalize +/- 0.0 (as you mentioned)
• canonicalize NaNs (Java has a built in canonicalized NaN, but you have to specify it, I'm not sure if other languages have this)

Handling NULL and empty objects
These cases may just mean better documentation, but needs some thought.

• Standardize on how to interpret NULL as well as guidelines on situations where it is OK emit a NULL.
• Standardize oh how to interpret empty Objects (arrays), as well guidelines on situations where it is OK emit an empty Object (as you mentioned).

String encoding
In Java, anyway, we assume UTF-8 everywhere, with one historical exception.

Possible next steps:

1. I agree and wish to add the above cases as well.
2. I agree, but will require careful orchestration. Existing code attempting to test newer images will always fail. And since the various languages will create their fixes asynchronously, the CL tests will have to pay attention to the SerVer bytes and code versions and existing CL tests will need to be updated.
3. I would like to put a nuance on this, specifically WRT the hashing assumptions. I certainly agree that we have a plan before we start changing any code. But these incompatibilities impact historically serialized images. The way we have handled incompatible serialization formats in the past was to change the Serialization Version (SerVer) byte in the preamble. The deserialization code then needs to be updated to be able to properly read the older SerVer as well as the latest one.

However, in the past the changes we faced were simple, like the offset of the Flags byte. We have not had to deal with this situation of incompatible hash assumptions. I'm not sure there is a graceful way forward. Certainly we should change the SerVer, for detection purposes, but then what, throw an exception telling the user to revert to an earlier code version? I don't know the answer.

Questions:

• As far as I am aware, these inconsistencies are an oversight and certainly not intentional.
• I'm not familiar with what you mean by "empty byte sequences" do you mean byte[] = {0,0,0...} or byte[0]?
  Bloom and XOR should definitely canonicalize signed zero and NaNs like HLL, CPC, Theta, and Tuple.
• We need one policy, which could be kept in TCK as well as copied to our Website.
• Yes, I certainly hope we can capture our policy here first.

[leerho]

A follow-up on my comment above. The Count-Min version 2 spec, now in apache/datasketches-tck#21 · docs: add the Count-Min…, has placeholders for these rules in section 4:

4.4: null and empty items;
4.5: floating-point items, covering ±0.0 and NaN canonicalization;
4.6: other types.

Each placeholder states what Count-Min version 2 does today. For example, it ignores empty strings, empty byte arrays and nulls, and it doesn’t define floating-point items for this sketch. Each one points here for the shared policy. Once we agree on that policy, I’d suggest specifying it once in the TCK, for example in a docs/input-encoding.md, and having each family’s format spec refer to it.

And to answer my own question about “empty byte sequences”: I see you defined it in section 2 of your post. It means a zero-length array (new byte[0], or a non-null C++ pointer with length zero), not an array of zeros. Thanks!

[tisonkun]

Thanks @leerho!

I agree with defining the shared hashed-input rules once in docs/input-hashing.md (disambiguated from encoding for codec) and having each family's format spec reference them.

I suggest defining the target contract and compiling an inventory of current implementations at pinned revisions first, then working out legacy-image migration for each affected family.

docs/input-hashing.md would cover:

1. Supported inputs and byte encoding: integer widening and byte order, UTF-8 strings without a length prefix or terminator, and raw byte sequences. Each family spec declares its supported types and defines its hash algorithm, seed derivation, and hash-to-state mapping.
2. Floating-point normalization: map -0.0 and +0.0 to +0.0, map all NaNs to one canonical bit pattern such as 0x7FF8000000000000, and specify byte order and float/f32 widening.
3. Null and empty inputs: I propose ignoring empty strings and zero-length byte sequences: updates are no-ops, membership and query-and-update calls return false, and Count-Min estimate and both bounds return 0. APIs with nullable inputs such as null, nil, or nullptr would follow the same rule, without requiring non-nullable APIs to accept nulls.
4. Conformance tests: encoding and hash vectors, plus cross-language behavioral checks after deserialization. Empty-input cases should also run against non-empty sketches.

Conformance should be based on an implementation's documented cross-language usage contract. For example, Rust's generic Hash API can document encoding wrappers and caller-side empty-input checks, while typed APIs in other languages perform those checks inside update and query. Both are fine if the contract is explicit and tested.

The inventory should cover Java, C++, Go, Rust, and Python by family, overload, and operation. For each case, it should record both raw API behavior and any caller-side steps required by the contract.

Once the target contract and implementation differences are clear, perhaps @leerho you could help assess the compatibility options for each affected family? That includes where a SerVer change makes sense, what guarantees we can provide for existing images, and whether some fixes should be explicitly breaking.

If this sounds good, I can start drafting docs/input-hashing.md with open choices marked and build out the implementation inventory for review.