Ah interesting, I hope it's that simple. TreeMap also conveniently has firstKey(), which could be used in place of creating an iterator to retrieve a single element in removeNextNode(), and save some object allocation. It will be interesting to see if the insertion time suffers noticeably (since it's log(N) for TreeMap, as opposed to constant time for HashMap).
BTW, I did some benchmarking and LinkedHashMap performs even better than TreeMap in this usage pattern (perhaps because LinkedHashMap is still constant-time whereas TreeMap is log(n)). So you might want to give this a try for a future release (it's also a simple drop-in replacement).