I don't agree that hashing would make it O(n), as it requires to handle hash collisions. This if course is not a real problem for average use cases, but after all that's not what the Landau thing is about, right? ;-) Usually, this would end up taking O(n log(n)) time, even with hashing. The main difference would be the constant that is involved. Of course it is hard to tell, but I would think that the HashSet would provide highly optimized code to do just this and it would be recommended to just use that.

I think learning C (and maybe also assembler) is a very good way to understand what really happens. Personally, I find it quite painful to program in these languages, as I prefer a higher order of thinking that does not distract me from doing algorithms and a good software design. But to understand what really happens and why XY now behaves just the way it does, I find it very useful that I have learned ANSI C and i386 Assembler.