Iterate Koloboke Hashmap while modifying it

Question

I have a large hashmap (~3M entries) and am using Koloboke LongIntMap to implement it. I need to iterate the keys in the map, but be able to modify the map along the way. Some of the modifications may be structural (adding/deleting entries).

I don't want to pay the price for synchronized implementations or copied key lists unless it's absolutely necessary. I know the iteration result will be more or less random, leaving out some keys, maybe taking other keys twice, and it is not a problem in our application.

Is there any way to achieve such map iteration? Thanks in advance for any input.

score 2 · Accepted Answer · answered Aug 31 '15 at 18:25

The idiomatic way to iterate over Koloboke collection with modifications (key removals and updates, but not additions) is via cursor:

for (LongIntCursor cur = map.cursor(); cur.moveNext();) {
    long key = cur.key();
    int value = cur.value();
    if (checkSomething(key, value)) {
        cur.remove(); // remove the entry
    } else {
        cur.setValue(newValue); // update the value
    }
}

Additions are not supported, it should throw ConcurrentModificationException, the same way as java.util.HashMap do. The reason why this is so - if addition triggers full map rehash, it's impossible to finish iteration properly.

As a workaround, you could collect entries you want to insert into the map during iteration, and perform a bulk insert after the iteration:

// You could get primitive lists from fastutil, gs, hppc or trove
LongList keysToPut = keysToPutThreadLocal.get();
keysToPut.clear();
IntList valuesToPut = valuesToPutThreadLocal.get();
valuesToPut.clear();

for (LongIntCursor cur = map.cursor(); cur.moveNext();) {
    long key = cur.key();
    int value = cur.value();
    if (checkSomething(key, value)) {
        cur.remove(); // remove the entry
    } else {
        // want to insert a <newKey, newValue> entry
        keysToPut.add(newKey);
        valuesToPut.add(newValue);
    }
}
// bulk insert
for (int i = 0, toPut = keysToPut.size(); i < toPut; i++) {
    map.put(keysToPut.get(i), valuesToPut.get(i));
}

Thanks for clearing up why additions are not supported. I would need to allow additions as well and would be willing to lose iteration guarantees. I guess there is no way without digging into the source then? — martin.burian, Aug 31 '15 at 19:37
You could take another lib, some of them might not throw `ConcurrentModificationException` (AFAIR hppc states it doesn't hide any details and basically allows any, even unsafe use). — leventov, Aug 31 '15 at 20:03

Iterate Koloboke Hashmap while modifying it

1 Answers1