isl-org / isl-org/Open3D

Easy-to-Find Hash Value Collision with Negative Coordinates

Open
#5,913 1 comment 1 reaction 1 assignee Claimed by @theNded View on GitHub
bug
Dominant language
C++
Stars
14k
Forks
2.6k
Avg merge
5d 18h
Merged PRs (30d)
6

Description

### Checklist

- [X] I have searched for [similar issues](https://github.com/isl-org/Open3D/issues).
- [X] For Python issues, I have tested with the [latest development wheel](http://www.open3d.org/docs/latest/getting_started.html#development-version-pip).
- [X] I have checked the [release documentation](http://www.open3d.org/docs/release/) and the [latest documentation](http://www.open3d.org/docs/latest/) (for `master` branch).

### Describe the issue

It appears that Open3D currently using [FNV1a function](https://github.com/isl-org/Open3D/blob/aa710ea7bb2e3a0fe3030264eb48373fd77cdb59/cpp/open3d/core/hashmap/Dispatch.h#L112-L126) ([wikipedia link](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function)) for hashing 3D coordinates. However, FNV1a can cause collisions extremely easily by negative coordinates. And the following piece of code can generate thousands of them with the same hash values,

```c++
#include
#include
#include

template
uint64_t FNV1a(const std::array &values) {
uint64_t hash = UINT64_C(14695981039346656037);
for (const auto &value : values) {
hash ^= static_cast(value);
hash *= UINT64_C(1099511628211);
}
return hash;
}

template
std::ostream &operator <<(std::ostream &stream, const std::array &values) {
stream << "(";
for (std::size_t i = 0; i < N; i++) {
stream << values[i];
if (i + 1 < N) {
stream << ", ";
}
}
stream << ")";
return stream;
}

int main() {
typedef std::array Point3D;

std::map map;
for (auto i = -100; i <= 100; i++) {
for (auto j = -100; j <= 100; j++) {
for (int k = -100; k <= 100; k++) {
auto now = Point3D({i, j, k});
auto value = FNV1a(now);
auto result = map.try_emplace(value, Point3D({i, j, k}));
if (!result.second) {
auto other = result.first->second;
std::cout << now << " <===> " << other << " "
<< value << " " << FNV1a(other) << std::endl;
}
}
}
}
return 0;
}
```

Outputs (last 10 lines):
```text
...
(100, 98, 90) <===> (100, -100, -92) 14594284135579372891 14594284135579372891
(100, 98, 91) <===> (100, -100, -91) 14594283036067744680 14594283036067744680
(100, 98, 92) <===> (100, -100, -94) 14594290732649142157 14594290732649142157
(100, 98, 93) <===> (100, -100, -93) 14594289633137513946 14594289633137513946
(100, 98, 94) <===> (100, -100, -96) 14594288533625885735 14594288533625885735
(100, 98, 95) <===> (100, -100, -95) 14594287434114257524 14594287434114257524
(100, 98, 96) <===> (100, -100, -98) 14594224761951449497 14594224761951449497
(100, 98, 97) <===> (100, -100, -97) 14594223662439821286 14594223662439821286
(100, 98, 98) <===> (100, -100, -100) 14594222562928193075 14594222562928193075
(100, 98, 99) <===> (100, -100, -99) 14594221463416564864 14594221463416564864
```

Since `eq_t` is used in the hash tables so there is no correctness issue. However, it might become a performance bug if we have a lot of hash values collisions.

### Steps to reproduce the bug

```python
import open3d
import numpy as np

# This should be the list that generated by the C++ program. I didn't include them here because it's a long list and it's a performance bug so the piece of code is only a reference to what I was talking about.
sources = np.asarray([
[100, 98, 90],
], dtype=np.int64)
queries = np.asarray([
[100, -100, -92],
], dtype=np.int64)

device = open3d.core.Device(open3d.core.Device.CUDA, 0)
sources = open3d.core.Tensor(sources, device=device)
queries = open3d.core.Tensor(queries, device=device)

key_shape = open3d.core.SizeVector([3])
hashset = open3d.core.HashSet(init_capacity=10,
key_dtype=open3d.core.Dtype.Int64,
key_element_shape=key_shape,
device=device)
hashset.insert(sources)
print(hashset.find(queries))
```

### Error message

_No response_

### Expected behavior

_No response_

### Open3D, Python and System information

```markdown
- Operating system: Arch Linux
- Python version: Python 3.8
- Open3D version: `0.16.1+5efea1ed1`
- System architecture: x86-64
- Is this a remote workstation?: no
- How did you install Open3D?: build from source
- Compiler version (if built from source): gcc 12.2.1 / cuda 11.8.0
```

### Additional information

An easy solution may be just to using another hash function, like just replacing the `^` (bitwise xor) by `+`. But I am not a hash function expert so I do not know if such changes in hash function could introduce other issues implicitly.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.