Right well, its clear that at least in java, he doesn't pre-allocate the size of the hashmap. Thus, when the hashmap hits its maximum size, of course the resize operation has to copy all of the data into a new map, which makes this no longer O(N) but something like O(NlogN) or O(N^2) depending.