What purpose does the newSetFromMap() method offer if I can just create something like a HashSet instead of a HashMap?

The Set returned by newSetFromMap() functions with the same ordering and concurrency characteristics of the map it is based off of. Some Map implementations also have a related Set implement, so using this method doesn't really help. That's the case with HashMap/HashSet and TreeMap/TreeSet. However, not all maps have this common partner. For instance, while there is a WeakHashMap, there is no WeakHashSet. Other user-generated collections might have similar situations. While you can get something like the key set from a Map, it won't be as closely tied to the underlying collection.