NonBlockingHashMap seems to have unbounded growth when using unique keys, even if the actual set of entries is small.
This gist illustrates the problem: https://gist.github.com/3568485
It simply inserts and removes a monotonically increasing integer. I.e., the working set is at most one object, but the map still grows to use all available heap, at which point it will eventually die with a OutOfMemoryError.
This problem has been observed in the wild in Cassandra, where NonBlockingHashMap is used liberally.