Flutter blue Guid 'operator==' will give false positives. about flutter_blue

[pauldemarco]

hashCode is also overridden, and forwards to _calcHashCode, which uses a ListEquality to compare byte for byte.

Do you have a specific test case that is showing a false positive?

[pauldemarco]

Closing for now. We can reopen if needed.

[djziegler]

I really looks like ListEquality.hash does a conventional hash rather than returning an int value that is a unique representation of the input value (Furthermore, ListEquality.hash is returning a 63 bit value, which is way fewer bits than in a GUID (see the & _HASH_MASK))

Source:

https://github.com/dart-lang/collection/blob/master/lib/src/equality.dart

class ListEquality implements Equality<List> {
// ....

int hash(List list) {
if (list == null) return null.hashCode;
// Jenkins's one-at-a-time hash function.
// This code is almost identical to the one in IterableEquality, except
// that it uses indexing instead of iterating to get the elements.
int hash = 0;
for (int i = 0; i < list.length; i++) {
int c = _elementEquality.hash(list[i]);
hash = (hash + c) & _HASH_MASK;
hash = (hash + (hash << 10)) & _HASH_MASK;
hash ^= (hash >> 6);
}
hash = (hash + (hash << 3)) & _HASH_MASK;
hash ^= (hash >> 11);
hash = (hash + (hash << 15)) & _HASH_MASK;
return hash;
}
}

[pauldemarco]

Interesting, I wonder what the collision rate would be, and if it's something to be concerned with. I'll reopen for now.

Consider looking into what the UUID lib does for this.

Related to #10

[djziegler]

Given that GUIDs have 128 bits and the hash codes you are using have 63 bits, each GUID will collide on average with 2^65 other GUIDs (36893488147419103232 other GUIDs).

As a general 'Globally Unique ID' class, having an '==' like this would kind of wreck the 'Unique ID' property.

However, given, that this is a flutter blue specific class, and that each program would only know about relatively few UUIDs (devices it has seen, service ids, characteristic ids etc), actual collisions will probably be pretty small.

However, if they do happen, it will be a really weird and hard to reproduce bug (for example a user will setup a fitness application with the UUID of the heart rate monitor. But it will just happen to collide with the UUID of a wireless camera - and you will have a really weird, hard to track down problem only effecting one user. Personally, I find these kinds of situations much more terrifying than a common bug - which one finds in testing and fixes.

For my purposes, I am just comparing the .toString () values of GUIDs - so it is not actually a problem for me.

On the other hand adding a check if ListEquality.equals () after the hash checks will add essentially no overhead.

Thank you for writing flutter blue - it is a massive relief to be free of Android SDK programming (which I am not a fan of), and I couldn't make the move until you wrote flutter blue.

[espresso3389]

I'm also afraid certain 'potential' false-positives on the current implementation.
Apparently, if equals(a, b) then hash(a) == hash(b) is true as mentioned on ListEquality hash method but the reverse is not always true.
The only and correct way is to compare all the bytes one by one though it is assumed to be slower than just comparing hashes.

[espresso3389]

I think, the operator == should be like this:

  operator ==(other) =>
    other is Guid && this.hashCode == other.hashCode && (const ListEquality<int>()).equals(_bytes, other._bytes);