apache / apache/lucene

RunAutomaton#hashCode() can easily cause hash collision for different Automatons [LUCENE-10610]

Open
#11,646 23 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor type:bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.