Как работает итератор в HashSet java

HashSet реализован на основе HashMap, соответственно его iterator проходит по ключам этого мапа.

 public class HashSet<E>
     extends AbstractSet<E>
     implements Set<E>, Cloneable, java.io.Serializable {
     ...
     private transient HashMap<E,Object> map;
     ...
     /**
      * Returns an iterator over the elements in this set.  The elements
      * are returned in no particular order.
      *
      * @return an Iterator over the elements in this set
      * @see ConcurrentModificationException
      */
      public Iterator<E> iterator() {
         return map.keySet().iterator();
      }
 }

Что касается LinkedHashSet, то он наследует HashSet и не переопределяет iterator(), это означает, что работает все тот же метод. Да и сложно было ждать чего-то другого, iterator и должен перебирать всю коллекцию.