Loop Through a set of Objects

I have a map of key-value pairs of huge size, approxi开发者_运维知识库mately 10^7, and I have to loop through it 15 times a second in order to update its contents Is there any class or structure that offers good complexity and reduces the time needed to loop through?

Currently, I am using TreeMap but the complexity is log n only for contains, put, get and remove. Looping through the elements is of n complexity

Do you know any structure or do you have any idea that may reduce the complexity below n?

If you have to arbitrary loop over the entire collection, you will not get better than n. If you have to loop the entire collection, you could use a simple ArrayList. but if you need to access specific data in the collection using a key, TreeMap will be fine.

You can't beat the O(n) bound on any sequential (or finitely parallel) computer, if your problem is just to look at all of O(n) values.

If you have a finitely parallel machine and depending on exactly how you're updating the elements, you could achieve speedup. For instance, using CUDA and a GPU or OpenMP/MPI and a cluster/multi-core workstation, you could compute A[i] = A[i]^3 or some such with good speedup. Of course, then there's the question of communication... but this might be something to look at.