Easy-to-Find Hash Value Collision with Negative Coordinates
- 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.