I had pretty much exact problem. We keep index of row keys in Cassandra on time partitioned data (by hour), but do not want to re-insert the index each time there is a piece of data.

A ConcurrentLinkedHashMap (http://code.google.com/p/concurrentlinkedhashmap/) solved it easily. It does use more RAM though... but an insignificant amount on our heap.