You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "leerho (via GitHub)" <gi...@apache.org> on 2026/10/01 20:09:45 UTC
[I] Array-of-strings tuple sketch: key hashing is incompatible with Java (UTF-8 vs UTF-16) [datasketches-go]
leerho opened a new issue, #191:
URL: https://github.com/apache/datasketches-go/issues/191
@proost, `GenerateHashKeyFromStrings` in `tuple/arrayofstrings_sketch.go` hashes the UTF-8 bytes of the key strings. Java's `tuple/Util.stringArrHash` hashes the joined key as UTF-16 code units (`XxHash.hashCharArr`, 2 bytes per `char`, little-endian), with the same seed and `,` separator. As a result, Go and Java AoS sketches built from the same keys share no hashes, and cross-language unions and intersections are wrong. This was confirmed with the `aos_*` snapshots in datasketches-tck: Go's snapshots match C++'s, and neither matches Java's.
Java's AoS has been released for years and is the reference. The fix is to convert each key from UTF-8 to UTF-16 code units, with surrogate pairs above U+FFFF, and hash them as little-endian bytes with `,` as `2c 00`. In Go, `utf16.Encode([]rune(s))` gives the code units. Please also add a test that checks hashes against the Java snapshots, including `aos_unicode`.
Note that the AoS sketch was released in v0.2.0, so this change invalidates AoS sketches saved with v0.2.0. Please call it out in the release notes.
The same issue in C++ is apache/datasketches-cpp#533, which we are fixing for the C++ 5.3.0 release.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [I] Array-of-strings tuple sketch: key hashing is incompatible with Java (UTF-8 vs UTF-16) [datasketches-go]
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #191:
URL: https://github.com/apache/datasketches-go/issues/191#issuecomment-5940780932
Two additions to include in the fix:
1. **Hash input, precisely:** the UTF-16 code units of the joined key, as **little-endian bytes with no byte-order mark** (UTF-16LE). This is what Java's `XxHash.hashCharArr(s.toCharArray(), ...)` hashes. Note that a generic "UTF-16" converter is not the same thing: Java's own `StandardCharsets.UTF_16`, for example, writes a `FE FF` byte-order mark followed by big-endian bytes.
2. **Document the key-join behavior.** Key elements are joined with `","` without escaping, so different keys that join to the same string hash the same and are treated as one key, for example `{"a,b"}` and `{"a", "b"}`, or an empty array and `{""}`. We can't change this without breaking compatibility with Java, so all implementations must keep this behavior. Please note it in the API documentation, along these lines:
> Key arrays are hashed by joining their elements with `","`. Keys that join to the same string, for example `{"a,b"}` and `{"a", "b"}`, are treated as the same key. If key elements may contain commas, escape or encode them before updating the sketch.
We'll add the same note to the Java documentation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [I] Array-of-strings tuple sketch: key hashing is incompatible with Java (UTF-8 vs UTF-16) [datasketches-go]
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #191:
URL: https://github.com/apache/datasketches-go/issues/191#issuecomment-5985593372
A note on how this differs from the C++ case (apache/datasketches-cpp#533):
C++ fixed its version by **reverting** the AoS sketch (apache/datasketches-cpp#537). That cost nothing because the C++ AoS sketch had never been released. Go can't do the same: AoS shipped in **v0.2.0**, so users may already have saved Go AoS sketches. Removing the sketch or changing its key hashing breaks those saved sketches either way.
So the Go fix has to be a **breaking change in a minor release (v0.3.0)**, which a pre-1.0 module allows, with the release notes saying clearly that:
- AoS sketches serialized by v0.2.0 hash their keys differently from the fixed version (and from Java), so they can't be combined with sketches built after the fix. Users should rebuild them from the source data.
- Key arrays are joined with `","` without escaping (see the note above).
Which encoding Go switches to (UTF-16LE to match Java, or UTF-8 everywhere) still depends on the dev@ discussion: https://lists.apache.org/thread/5vlbnodmw8h5s0oc1988f4pdhkjnv8qw
Meanwhile, the datasketches-tck snapshots keep the 27 `aos_*_go.sk` files as v0.2.0 writes them. When the fix lands, the next TCK snapshot update will show them as deterministic changes, so the format change will be visible in review.
Separately, apache/datasketches-go#193 fixes `make generate-go-snapshots`, which currently fails on `main` with `ErrHashExceedsTheta`. It doesn't change any hashing.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org