Hunspell Dictionary can fail to load with "Too many collisions" when its entry count is a multiple of 961

WordStorage, the hash table that holds a Hunspell Dictionary's words since 8.9.0, has one slot per entry (WordStorage.java:294: (int) (wordCount * hashFactor), default factor 1.0) and puts each word into slot Math.abs(String.hashCode() % tableSize) (build :390, lookup :109, on main 645d4fe14a20). A slot may hold at most 20 entries; the 21st throws RuntimeException: Too many collisions. Try a larger Dictionary#hashFactor (now 1.0). If this doesn't help, please report this to dev@lucene.apache.org (:399-404). String.hashCode() is the polynomial h = 31*h + c, so when the table size is a multiple of 961 = 31 x 31, every letter except the last two adds a multiple of 961: short words that share their last two letters crowd into a few slots.

A test dictionary of 961 plain words fails to load while 960 or 962 words load. In real use, the stock en_US dictionary (48,711 entries, hidden title-case entries included) plus a custom list of 300 words (49,011 = 51 x 961) fails: one slot gets 22 words, 21 of them six-letter "-er" words. Every release from 8.9.0 to 10.6.0 and main is affected; adding or removing one word avoids it.

• Entry count. Dictionary.mergeDictionaries reads every .dic stream, skips its first line ("number of entries (approximately, sometimes)", Dictionary.java:1016) and passes each word line to writeNormalizedWordEntry (:1034), which adds one entry (:1060), plus a hidden title-case entry for mixed-case words and flagged upper-case words (:1062-1064, :1068-1079). The offline sorter counts every entry (SortingStrategy.java:74-78, :91-92), and readSortedDictionaries passes that count and hashFactor() to WordStorage.Builder (Dictionary.java:1102-1104).
• Table size. hashTable = new int[(int) (wordCount * hashFactor)] (WordStorage.java:294). hashFactor() is protected and returns 1.0; its javadoc: "If there are too many hash collisions, the factor can be increased, resulting in faster access, but more memory usage" (Dictionary.java:1160-1168).
• Slot. Build: int hash = Math.abs(currentEntry.hashCode() % hashTable.length) (WordStorage.java:390). Lookup: Math.abs(CharsRef.stringHashCode(word, offset, length) % hashTable.length) (:109), the same polynomial result = 31 * result + chars[i] (CharsRef.java:86-93). No bit mixing.
• Limit. if (++chainLengths[hash] > 20) throws the RuntimeException (WordStorage.java:399-404). HunspellStemFilterFactory catches only ParseException (:115), so it escapes inform() unwrapped.

• For a lowercase ASCII word of up to 5 letters the sum does not overflow, and every term except the last two is a multiple of 31^2 = 961, so hash % 961 = (31*c[n-2] + c[n-1]) % 961: only the last two letters matter.
• Every 6-letter lowercase word wraps exactly once (its sum lies in [2^31, 2^32)), so its residue also depends only on the last two letters (a different residue class than the shorter words).
• With a table of m x 961 slots, slot % 961 = |hash % 961| (Math.abs turns the negative remainder of a wrapped hash positive), so the words of one such group can use only m of the slots. With exactly 961 slots, one slot.
• Minimal test: 961 slots; aing to uing and ang all have residue 630 (31 x 'n' + 'g' = 3,513 = 3 x 961 + 630), so slot 630 gets 22 entries. With 960 or 962 entries the busiest slot holds 3 (a slot count outside Lucene).
• en_US + 300 words: 49,011 = 51 x 961 slots; the six-letter "-er" words share 51 slots and the busiest gets 22 (Kepler, Walter, Xavier, archer, buzzer, career, ... and one longer word). At 49,010 or 49,012 entries the busiest slot holds 7.
• Multiples of 31^3 are worse: en_US + 10,871 words gives 59,582 = 2 x 31^3 slots, and one slot gets 61 six-letter words ending in "ter" (Finder, Master, Potter, ...); at 1.5x, 2x and 3x that size (3, 4 and 6 x 31^3) the busiest slot still holds 47, 32 and 26.
• Modulo 31 for small lists: short words that share their last letter can use only m of m x 31 slots. 31 entries (21 two-letter words ba to va plus 10 others) throw; 30 and 32 load. For real-size dictionaries the multiples of 961 are what matter.

• What goes wrong. The dictionary, and the stemmer, analyzer or spell checker built on it, cannot be created at all: a loud, deterministic failure at load, the same with assertions on and off. Nothing is silently wrong and no index is touched.
• What it takes. For real-size dictionaries the total entry count, hidden title-case entries and duplicate lines included, must be a multiple of 961 (about one list size in 961; for a small list a multiple of 31 can be enough, like the 124 = 4 x 31-entry test dictionary that found it). The content must also put more than 20 short words with a common ending into one slot group: in the finder's survey only en_US crosses the limit at multiples of 961 (3 of 3 sizes); nb_NO stays at 13 or below and sv_SE at 10.
• Executed real cases (three independent custom-word generators). Through the plain constructor, en_US plus 300, 1,261, 2,222, 3,183, 6,066, 9,910 or 10,871 custom words fails; 11 other list sizes load and spell-check. Through HunspellStemFilterFactory with dictionary="en_US.dic,custom.dic": 300, 1,261 and 10,871 fail; 299, 301, 1,260, 1,262 and 10,870 load. A model predicts 13 failing sizes among the 18 multiples of 961 from 51 x 961 to 68 x 961 (custom lists of 300 to about 16,600 words; model only beyond the 7 executed).
• The advised remedy is not always available or enough. hashFactor() is protected (a Dictionary subclass is needed) and HunspellStemFilterFactory cannot set it (HunspellStemFilterFactory.java:111). An integer factor keeps the size a multiple of 961; at en_US + 10,871 words the factors 1.5, 2.0 and 3.0 still throw, which is exactly when the message asks for a report. At en_US + 300 words, 1.5, 2.0, 3.0 and 4.0 load.
• Workarounds. Add or remove one word. Direct-API users can subclass Dictionary and return a factor that makes the table size not divisible by 31, such as 1.1 (en_US + 10,871 words: 65,540 slots, loads); no fixed factor does that for every count.
• How likely: rare. No public report was found in the five years since 8.9.0.

Copy the test into lucene/analysis/common/src/test/org/apache/lucene/analysis/hunspell/ of a Lucene checkout and run it with gradle (command below). It uses only the public constructor; it sits in the hunspell package because the upstream hunspell tests do. With the mixed-hash fix it passes unchanged, so it doubles as the regression test.

Executed: gradle in a fresh scratch worktree of 645d4fe14a20 (fails with seed DEADBEEF, which picks assertions off, and with seed 933B0301 and -Ptests.asserts=true); the standalone runner on the stock main jars with -ea and -da, and on the release jars 8.0.0 to 10.6.0 (fails from 8.9.0 on, passes before).

Left out on purpose: the real en_US case, which needs an external dictionary file. Its executed numbers are under "Who is affected".

cp $REPRO/TestDictionary961Entries.java $LUCENE/lucene/analysis/common/src/test/org/apache/lucene/analysis/hunspell/
cd $LUCENE && ./gradlew :lucene:analysis:common:test --tests org.apache.lucene.analysis.hunspell.TestDictionary961Entries -Ptests.seed=DEADBEEF

# gradle, main 645d4fe14a20, -Ptests.seed=933B0301 -Ptests.asserts=true
TestDictionary961Entries > testDictionaryWith961WordsLoads FAILED
    java.lang.AssertionError: expected the 961-word dictionary to load, but: java.lang.RuntimeException: Too many collisions. Try a larger Dictionary#hashFactor (now 1.0). If this doesn't help, please report this to dev@lucene.apache.org
        at org.apache.lucene.analysis.hunspell.TestDictionary961Entries.testDictionaryWith961WordsLoads(TestDictionary961Entries.java:46)

        Caused by:
        java.lang.RuntimeException: Too many collisions. Try a larger Dictionary#hashFactor (now 1.0). If this doesn't help, please report this to dev@lucene.apache.org
            at org.apache.lucene.analysis.hunspell.WordStorage$Builder.flushGroup(WordStorage.java:400)
            at org.apache.lucene.analysis.hunspell.WordStorage$Builder.add(WordStorage.java:325)
            at org.apache.lucene.analysis.hunspell.Dictionary.readSortedDictionaries(Dictionary.java:1149)
            at org.apache.lucene.analysis.hunspell.Dictionary.<init>(Dictionary.java:270)
            at org.apache.lucene.analysis.hunspell.Dictionary.<init>(Dictionary.java:213)
            at org.apache.lucene.analysis.hunspell.Dictionary.<init>(Dictionary.java:192)
            at org.apache.lucene.analysis.hunspell.TestDictionary961Entries.testDictionaryWith961WordsLoads(TestDictionary961Entries.java:43)

# standalone runner, seed DEADBEEF
main 645d4fe14a20  -ea / -da   tests_run=1 failures=1   same message
10.6.0             -da         tests_run=1 failures=1   same message
10.5.2             -ea / -da   tests_run=1 failures=1   same message
8.9.0              -da         tests_run=1 failures=1   "Too many collisions, please report this to dev@lucene.apache.org"
8.8.2              -da         tests_run=1 failures=0

• Contract. The public constructors list only @throws IOException Can be thrown while reading from the InputStreams and @throws ParseException Can be thrown if the content of the files does not meet expected formats (Dictionary.java:186-187, :203-204, :223-224). Dictionary is not marked @lucene.experimental. No javadoc, package doc, MIGRATE.md entry or test documents a size or content limit; the analysis-common tests never mention hashFactor, "Too many collisions" or the chain length.
• History. In the LUCENE-9825 review (apache/lucene-solr#2459), Michael McCandless asked whether exceeding the cap was "statistically a small but non-trivial possibility". The author, Peter Gromov, answered: "Yes, it's a nontrivial possibility. I thought following the pattern please report this to dev@lucene.apache.org would be enough (in which case we could either raise this limit, or rehash automatically, or suggest to alter the dictionary if it's wrong). Do you think we should be more proactive here?" (2021-03-08), and Michael McCandless replied "I think this exception and it's message is great -- no need to be more proactive" (2021-03-09). On #12464, which added hashFactor, Dawid Weiss wrote: "Most people will use it out of the box and we can then count on their feedback if something is not right" (2023-07-27). Neither review discusses the table-size effect; CHANGES lists #12464 under 9.8.0 "Improvements".
• Effect. 960 and 962 entries load, 961 does not; a stock dictionary plus 300 words fails, 299 or 301 load. The cause is structural, not an unlucky random collision.

The strongest case for "works as designed" (the cross-model reviewer rated it moderate): the 20-entry cap is a deliberate safety limit that the reviewers endorsed ("+1 to keep this safety", "no need to be more proactive"), the message names the remedy (hashFactor), HunspellStemFilterFactory is @lucene.experimental, and a throws list need not be exhaustive.

Why it fails: the reviewers accepted the cap as a detector for presumed-random collisions plus a reporting channel, and the author's planned answer to a report on a dictionary that is not wrong was a code change ("raise this limit, or rehash automatically"). Here the input is a stock dictionary plus plain words and the cause is deterministic. The remedy cannot be reached from the factory and is not reliable (1.5, 2.0 and 3.0 fail at en_US + 10,871 words). Dictionary itself is not experimental, and "experimental" waives API compatibility, not loading valid data. The devil's advocate, the adjudication and two tie-breaks each rejected the works-as-designed case.

Three options. The mixed hash was validated with gradle in a scratch worktree at 645d4fe14a20; the other two were not executed. Whatever the choice, the build and lookup slot computations must stay identical.

In WordStorage, add a private static slot(int stringHash, int tableSize) that returns Math.floorMod(BitMixer.mix32(stringHash), tableSize) and use it in lookupWord (:109) and in Builder.flushGroup (:390). BitMixer is org.apache.lucene.internal.hppc.BitMixer from core. Same logic as the study's fix, re-formatted for google-java-format.

import org.apache.lucene.internal.hppc.BitMixer;

  private static int slot(int stringHash, int tableSize) {
    return Math.floorMod(BitMixer.mix32(stringHash), tableSize);
  }

  // lookupWord (:109)
  int hash = slot(CharsRef.stringHashCode(word, offset, length), hashTable.length);
  // Builder.flushGroup (:390)
  int hash = slot(currentEntry.hashCode(), hashTable.length);

Trade-offs

• A few integer operations per lookup (mix32: two multiplies, three xor-shifts); no benchmark was run.
• No format change: WordStorage is in memory only and rebuilt at every load.
• org.apache.lucene.internal.hppc is exported by core "temporarily" to all modules (module-info.java:55-57); WordStorage already imports IntArrayList from it. A committer may prefer a local mixer.
• Word enumeration (processAllWords, WordStorage.java:178) walks the table in slot order, so that order changes; suggestion ranking breaks ties by the word itself (GeneratingSuggester.java:103-106, :450-452).
• The 20-entry cap stays. The mixed hash removes the radix-31 / table-size correlation shown here; it is still a fixed hash, so other inputs can still collide, but in the recorded survey the longest chain was at most 10 for every dictionary and size tried. That fits what the 2021 review intended the cap for.

What the checks validated

• Gradle, fresh scratch worktree at 645d4fe14a20 + the fix (its javadoc corrected after the cross-model fact check, code unchanged), -Ptests.seed=933B0402 -Ptests.asserts=true: :lucene:analysis:common:checkGoogleJavaFormat passes; the hunspell test package, the minimal test included, passes: 159 tests in 47 suites (146 run, 13 skipped), 0 failures, 0 errors. The skipped suites (TestAllDictionaries, TestPerformance, TestHunspellRepositoryTestCases) need external dictionaries. The unpatched checkout fails the minimal test in the same worktree. The previous wording of the diff gave the same counts (seeds 933B0302 and DEADBEEF, and in the fact checks).
• Shadowed on the stock main jars: the minimal test passes with -ea and -da; en_US plus k custom words loads and spell-checks for every k tried (0, 299, 300, 301, 1,261, 2,222, 3,183, 6,066, 9,910, 10,871).
• Earlier runs of the study's equivalent fix: the finder's 7 tests, the independent reproducer's 11 and Lucene's 146 hunspell tests pass; the real-dictionary survey's longest chain is at most 10 for every size tried.

Bump (int) (wordCount * hashFactor) until it is not a multiple of 31 (or use a prime size).

Trade-offs

Smaller, but it keeps the unmixed polynomial hash, and a user-chosen factor would be adjusted silently. Modelled only: with sizes coprime to 31 the en_US worst chain is 8; not run in Lucene.

The two responses the author named in the 2021 review.

Trade-offs

Raising the limit only moves the threshold (61 entries in one slot at 2 x 31^3). Rehashing needs a second pass over the sorted entries, because the builder writes each entry into the table as it goes. Not executed.

Method: semi-formal (the hunt's tier for bounded-exhaustive checks), in a hunt unit that compared Lucene's Hunspell SET encodings with reference codec tables on the stock main jars.

• The decode leg loads a one-word-per-byte test dictionary for every non-control high byte of each loadable SET encoding and compares Hunspell.spell with the codec tables.
• The all-high-byte ISO8859-3 dictionary (89 words plus 35 hidden title-case entries = 124 = 4 x 31 entries) failed to load for a reason unrelated to decoding.
• A ddmin-style minimiser showed that removing any single word makes it load, so the trigger is the entry count.
• The String.hashCode() modulo 31 / 961 hypothesis was then confirmed by a slot count outside Lucene and a survey of real dictionaries (en_US, nb_NO, sv_SE and Lucene's test dictionaries), and reduced to a public-API JUnit test, later to the single test shown here.