Java中的Map实现

源码来自JDK8

Map接口

public interface Map<K,V> { interface Entry<K,V> { } }

HashMap

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //容量参数 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量 aka 16 static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量 static final float DEFAULT_LOAD_FACTOR = 0.75f; //链表转红黑树参数 static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64; //数据存储的结构 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } transient Node<K,V>[] table; }

LinkedHashMap

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{ transient LinkedHashMap.Entry<K,V> head; transient LinkedHashMap.Entry<K,V> tail; static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; } }

TreeMap

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ private final Comparator<? super K> comparator; private transient Entry<K,V> root;//红黑树的根节点 public TreeMap() { comparator = null; } static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; } }

TreeMap的底层数据结构是红黑树。

ConcurrentModificationException

在Java开发过程中，遍历集合的同时对集合进行修改就会出现java.util.ConcurrentModificationException异常。以HashMap中的代码展示：

@Override public void forEach(BiConsumer<? super K, ? super V> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e.key, e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } }