1.测试代码

public class MapKeySet {
    public static void main(String[] args) {

        System.out.println("##  TreeMap  ##");
        TreeMap<String , String> tm = new TreeMap<String , String>();
        tm.put("1", "OOO");
        tm.put("3", "OOO");
        tm.put("2", "OOO");
        tm.put("5", "OOO");
        tm.put("4", "OOO");
        tm.put("11", "OOO");
        tm.put("17", "OOO");
        tm.put("9", "OOO");

        Iterator<String> it2 =  tm.keySet().iterator();


        while (it2.hasNext()) {
            System.out.println(it2.next());
        }


        System.out.println("##  HashMap  ##");
        Map<String , String> hm = new HashMap<String , String>();
        hm.put("1", "OOO");
        hm.put("3", "OOO");
        hm.put("2", "OOO");
        hm.put("5", "OOO");
        hm.put("4", "OOO");
        hm.put("11", "OOO");
        hm.put("17", "OOO");
        hm.put("9", "OOO");

        Iterator<String> it3 =  hm.keySet().iterator();

        while (it3.hasNext()) {
            System.out.println(it3.next());
        }


        System.out.println("##  LinkedHashMap  ##");
        LinkedHashMap<String, String> lhm = new LinkedHashMap<String , String>();
        lhm.put("1", "OOO");
        lhm.put("3", "OOO");
        lhm.put("2", "OOO");
        lhm.put("5", "OOO");
        lhm.put("4", "OOO");
        lhm.put("11", "OOO");
        lhm.put("17", "OOO");
        lhm.put("9", "OOO");

        Iterator<String> it4 =  lhm.keySet().iterator();

        while (it4.hasNext()) {
            System.out.println(it4.next());
        }
    }
}

结果如下：

##  TreeMap  ##
1
11
17
2
3
4
5
9
##  HashMap  ##
11
1
2
3
4
5
17
9
##  LinkedHashMap  ##
1
3
2
5
4
11
17
9

从测试中可以看出：

• TreeMap为升序
• HashMap为乱序
• LinkedHashMap为插入的顺序

2.源码分析

2.1 TreeMap

    final class KeyIterator extends PrivateEntryIterator<K> {
        KeyIterator(Entry<K,V> first) {
            super(first);
        }
        public K next() {
            return nextEntry().key;
        }
    }

调用PrivateEntryIterator的nextEntry()方法

        final Entry<K,V> nextEntry() {
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = successor(e);
            lastReturned = e;
            return e;
        }

最后调用TreeMap的successor方法：

    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

2.2 HashMap

    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

调用HashIterator的nextNode()：

        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

可以看出是逐个桶的链表进行遍历，直到遍历到桶的最后！

2.3 LinkedHashMap

    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }

调用LinkedHashIterator的nextNode方法：

        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            next = e.after;
            return e;
        }

可知该遍历是通过after指针，也即按插入顺序的链表的after指针来遍历的。