I haven't investigated the problem, but the code looks good. Insertion will be more expensive, but is still O(1) expected. Merge reduces to add so that is covered as well (maybe add a test for that?).

There is another issue I just came around when thinking about this change once again: The packIDs are not deduplicated so far..
I need to think about how to best do this and change this to WIP in meanwhile..

I changed this such that now the check is performed in Index.merge(). IndexMap` stays unchanged now.

@aawsome Did you check the masterIndex benchmarks regarding the performance impact of the additional foreach loop?

Note that the additional foreachID loop is O(1) itself (at least if the undelying hash is not degenerated). Hence the total complexity of the merge is still roughly (neglecting hash growing of idx) O(n) with n being the number of elements of the index to be merged, i.e. idx2.

Moreover this change only affects the merge itself, and in real-world-scenarios this occurs during

• loading the index from index files into memory (should be dominated by loading and decrypting/deserializing the files)
• saving a new finished index during backup (this should happen quite rarely as backup itself should be mainly dominated by actually saving data)

So I do not expect any impact on real-life usage.

About benchmarking: Seems to me that none of the current benchmarks actually includes merging of indexes in the measurements.
I added the benchmark MasterIndexAlloc which creates and merges Indexes under measurement.
Here are the results comparing 5e63294 with b112533:

name                old time/op    new time/op    delta
MasterIndexAlloc-4     334ms ± 1%     460ms ± 1%  +37.68%  (p=0.000 n=9+8)

name                old alloc/op   new alloc/op   delta
MasterIndexAlloc-4     258MB ± 0%     258MB ± 0%     ~     (p=0.101 n=10+8)

name                old allocs/op  new allocs/op  delta
MasterIndexAlloc-4      317k ± 0%      317k ± 0%     ~     (p=0.267 n=10+6)