RunAutomaton#hashCode() can easily cause hash collision for different Automatons [LUCENE-10610]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
Current RunAutomaton#hashCode() is:
```java
`@Override`
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + alphabetSize;
result = prime * result + points.length;
result = prime * result + size;
return result;
}
```
Since it does not take account of the contents of the `points` array, this returns the same value for different automatons when their alphabet size and state size are the same.
For example, this test code passes.
```java
public void testHashCode() throws IOException {
PrefixQuery q1 = new PrefixQuery(new Term("field", "aba"));
PrefixQuery q2 = new PrefixQuery(new Term("field", "fee"));
assert q1.compiled.runAutomaton.hashCode() == q2.compiled.runAutomaton.hashCode();
}
```
I suspect this is a bug?
Note that I think it's not a serious one; all callers of this `hashCode()` take account of additional information when calculating their own hash value, it seems there is no substantial impact on higher-level APIs.
---
Migrated from [LUCENE-10610](https://issues.apache.org/jira/browse/LUCENE-10610) by Tomoko Uchida (@mocobeta), updated Jun 11 2022
Contributor guide
Research direction
Start with RunAutomaton#hashCode() and inspect how the points array contributes to automaton identity. Reproduce the collision using the PrefixQuery examples for "aba" and "fee", then add a regression test near the existing automaton tests. Done means different automatons with the same alphabet and state sizes no longer collide solely because their points contents differ.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 48/100