http://www.cnblogs.com/tstd/p/5064032.html
主要看下nextEntry()这个方法，该方法主要思路是，首选拿去HashMap低层数组中第一个不为null的节点，每次调用迭代器的next()方法，就用该节点next一下，当当前节点next到最后为null，就拿数组中下一个不为null的节点继续遍历。什么意思呢，就是循环从数组第一个索引开始，遍历整个Hash表。
LinkedHashMap的迭代器
看到private static final Object PRESENT = new Object();不知道你有没有一点疑问呢。这里使用一个静态的常量Object类来充当HashMap的value，既然这里map的value是没有意义的，为什么不直接使用null值来充当value呢？比如写成这样子private final ObjectPRESENT = null;我们都知道的是，Java首先将变量PRESENT分配在栈空间，而将new出来的Object分配到堆空间，这里的new Object()是占用堆内存的（一个空的Object对象占用8byte），而null值我们知道，是不会在堆空间分配内存的。那么想一想这里为什么不使用null值。想到什么吗，看一个异常类java.lang.NullPointerException， 噢买尬，这绝对是Java程序员的一个噩梦，这是所有Java程序猿都会遇到的一个异常，你看到这个异常你以为很好解决，但是有些时候也不是那么容易解决，Java号称没有指针，但是处处碰到NullPointerException。所以啊，为了从根源上避免NullPointerException的出现，浪费8个byte又怎么样，在下面的代码中我再也不会写这样的代码啦if (xxx == null) { ... } else {....}，好爽。
public boolean add(E e) { return map .put(e, PRESENT)== null; } /** * 删除指定集合c中的所有元素，该方法在AbstractSet中 */ public boolean removeAll(Collection<?> c) { boolean modified = false; // 判断当前HashSet元素个数和指定集合c的元素个数，目的是减少遍历次数 if (size() > c.size()) { // 如果当前HashSet元素多，则遍历集合c，将集合c中的元素一个个删除 for (Iterator<?> i = c.iterator(); i.hasNext(); ) modified |= remove(i.next()); } else { // 如果集合c元素多，则遍历当前HashSet，将集合c中包含的元素一个个删除 for (Iterator<?> i = iterator(); i.hasNext(); ) { if (c.contains(i.next())) { i.remove(); modified = true; } } } return modified; }
4 public boolean contains(Object o) { 5 return map .containsKey(o); 6 } 7 8 /** 9 * 检查是否包含指定集合中所有元素，该方法在AbstractCollection中 10 */ 11 public boolean containsAll(Collection<?> c) { 12 // 取得集合c的迭代器Iterator 13 Iterator<?> e = c.iterator(); 14 // 遍历迭代器，只要集合c中有一个元素不属于当前HashSet，则返回false 15 while (e.hasNext()) 16 if (!contains(e.next())) 17 return false; 18 return true; 19 }
8 public Iterator<E> iterator() { 9 return map .keySet().iterator(); 10 }HashMap:
1 public Set<K> keySet() { 2 Set<K> ks = keySet; 3 return (ks != null ? ks : (keySet = new KeySet())); 4 }
1 private final class KeySet extends AbstractSet<K> { 2 public Iterator<K> iterator() { 3 return newKeyIterator(); 4 } 5 public int size() { 6 return size ; 7 } 8 public boolean contains(Object o) { 9 return containsKey(o); 10 } 11 public boolean remove(Object o) { 12 return HashMap.this.removeEntryForKey(o) != null; 13 } 14 public void clear() { 15 HashMap. this.clear(); 16 } 17 }
1 private final class KeyIterator extends HashIterator<K> { 2 public K next() { 3 return nextEntry().getKey(); 4 } 5 }
1 private abstract class HashIterator<E> implements Iterator<E> { 2 // 下一个需要返回的节点 3 Entry<K,V> next; // next entry to return 4 int expectedModCount ; // For fast-fail 5 int index ; // current slot 6 // 当前需要返回的节点 7 Entry<K,V> current;// current entry 8 9 HashIterator() { 10 expectedModCount = modCount ; 11 if (size > 0) { // advance to first entry 12 Entry[] t = table; 13 // 初始化next参数，将next赋值为HashMap底层的第一个不为null节点 14 while (index < t.length && ( next = t[index ++]) == null) 15 ; 16 } 17 } 18 19 public final boolean hasNext() { 20 return next != null; 21 } 22 23 final Entry<K,V> nextEntry() { 24 if (modCount != expectedModCount) 25 throw new ConcurrentModificationException(); 26 // 取得HashMap底层数组中链表的一个节点 27 Entry<K,V> e = next; 28 if (e == null) 29 throw new NoSuchElementException(); 30 31 // 将next指向下一个节点，并判断是否为null 32 if ((next = e.next) == null) { 33 Entry[] t = table; 34 // 如果为null，则遍历真个数组，知道取得一个不为null的节点 35 while (index < t.length && ( next = t[index ++]) == null) 36 ; 37 } 38 current = e; 39 // 返回当前节点 40 return e; 41 } 42 43 public void remove() { 44 if (current == null) 45 throw new IllegalStateException(); 46 if (modCount != expectedModCount) 47 throw new ConcurrentModificationException(); 48 Object k = current.key ; 49 current = null; 50 HashMap. this.removeEntryForKey(k); 51 expectedModCount = modCount ; 52 } 54 }
LinkedHashMap的迭代器
1 private abstract class LinkedHashIterator<T> implements Iterator<T> { 2 // header.after为LinkedHashMap双向链表的第一个节点，因为LinkedHashMap的header节点不保存数据 3 Entry<K,V> nextEntry = header .after; 4 // 最后一次返回的节点 5 Entry<K,V> lastReturned = null; 6 7 /** 8 * The modCount value that the iterator believes that the backing 9 * List should have. If this expectation is violated, the iterator 10 * has detected concurrent modification. 11 */ 12 int expectedModCount = modCount; 13 14 public boolean hasNext() { 15 return nextEntry != header; 16 } 17 18 public void remove() { 19 if (lastReturned == null) 20 throw new IllegalStateException(); 21 if (modCount != expectedModCount) 22 throw new ConcurrentModificationException(); 23 24 LinkedHashMap. this.remove(lastReturned .key); 25 lastReturned = null; 26 expectedModCount = modCount ; 27 } 28 29 Entry<K,V> nextEntry() { 30 if (modCount != expectedModCount) 31 throw new ConcurrentModificationException(); 32 if (nextEntry == header) 33 throw new NoSuchElementException(); 34 35 // 将要返回的节点nextEntry赋值给lastReturned 36 // 将nextEntry赋值给临时变量e（因为接下来nextEntry要指向下一个节点） 37 Entry<K,V> e = lastReturned = nextEntry ; 38 // 将nextEntry指向下一个节点 39 nextEntry = e.after ; 40 // 放回当前需返回的节点 41 return e; 42 } 43 }
可以看出LinkedHashMap的迭代器，不在遍历真个Hash表，而只是遍历其自身维护的双向循环链表，这样就不在需要对数组中是否为空节点进行的判断。所以说LinkedHashMap在迭代器上的效率面通常是高与HashMap的，既然这里是通常，那么什么时候不通常呢，那就是HashMap中元素较少，分布均匀，没有空节点的时候。
