A tree map is O(n*log n) on inserts, though.

For a hash map to be faster, you'd need to trade memory for speed, i.e have significantly more buckets than the expected size. This may however collide with good caching performance which I suspect is what the author observes.