I'm writing a Java framework to manipulate a large amount of data in-memory, where many "cells" that are near each other will have the same value.

I'm looking for algorithms and/or techniques specially designed to eliminate those duplication while maintaining fast in-memory read access speed. That is, techniques that keeps an O(1) read-access speed.

My data is store in immutable objects, to allow fast multi-threading. The data itself can be anything, from 4 bits-per-cell to doubles to arrays of beans, etc.

2 Answers 2


If there is a lot of repetition of values then some form of run length encoding might work for the compression side, the tricky part would be maintaining O(1) lookup (or if we relax that constraint slightly, fast lookup)

you could get log m lookup relatively easily (where m is the number of runs , not the number of values) by instead of storing the length with each value store the index

e.g. using the wikipedia example of


instead of storing the lengths with each value for a run (added parens for clarity)

(12 W)(1 B)(12 W)(3 B)(24 W)(1 B)(14 W)

we could store the indexes at which we change value (pluss an ending value if necessary)

(0 W)(12 B)(13 W)(25 B)(28 W)(52 B)(53 W)(67 null) 

we can then use a binary search on the index to find the value for any index in log(m) which may be quick enough?


Look into memoization. You may be able to store pointers to the data, or a partial prefix of it, instead of the data itself.

Of course if your data are small enough this may not be a win.

Not the answer you're looking for? Browse other questions tagged or ask your own question.