# 目录 * [0. Java集合框架历史](#Java集合框架历史) * [1. Java集合概述](#1.Java集合概述) * [Collection集合概述](Collection集合概述) * [Map集合概述](#Map集合概述) * [Concurrent包下的集合概述](#Concurrent包下的集合概述) * [2. Java集合详解](#2.Java集合详解) * [Collection集合下常用实现类详解](#Collection集合下常用实现类详解) * [Iterator接口源码解析](#Iterator接口源码解析) * [Collection接口源码解析](#Collection接口源码解析) * [List接口源码解析](#List接口源码解析) * [AbstractCollection抽象类源码解析](#AbstractCollection抽象类源码解析) * [AbstractList抽象类源码解析](#AbstractList源码解析) * [ArrayList源码解析和使用](#ArrayList源码解析和使用) * [Vector源码解析和使用](#Vector源码解析和使用) * [Stack源码解析和使用](#Stack源码解析和使用) * [AbstractSequentialList抽象类源码解析](#AbstractSequentialList抽象类源码解析) * [LinkedList源码解析和使用](#LinkedList源码解析和使用) * [Set接口源码解析](#Set接口源码解析) * [AbstractSet源码解析](#AbstractSet源码解析) * [HashSet源码解析和使用](#HashSet源码解析和使用) * [TreeSet源码解析和使用](#TreeSet源码解析和使用) * [Queue接口源码解析](#Queue接口源码解析) * [Deque接口源码解析](#Deque接口源码解析) * [LinkedList使用](#LinkedList使用) * [Map集合下常用实现类详解](#Map集合下常用实现类详解) * [AbstractMap接口源码解析](#AbstractMap接口源码解析) * [HashMap源码解析和使用](#HashMap源码解析和使用) * [WeakHashMap源码解析和使用](#WeakHashMap源码解析和使用) * [TreeMap源码解析和使用](#TreeMap源码解析和使用) * [Hashtable源码解析和使用](#Hashtable源码解析和使用) * [Concurrent包下常用实现类详解](#Concurrent包下常用实现类详解) * [3. 集合框架中体现的设计模式和编程规范](#3.集合框架中体现的设计模式和编程规范) * [迭代器模式](#迭代器模式) * [适配器模式](#适配器模式) * [4. 其他](#4.其他) * [fail-fast机制](#fail-fast机制) * [MarkerInterface](#Marker-Interface) * [Collections工具类-操作集合]() * [Arrays工具类-操作数组]() * [5. 圈重点](#5.圈重点) * [6. Stream](#6.Stream) * [参考资料](#参考资料) # 0.Java集合框架历史 摘自Wikipedia [Java Collection Framework](https://en.wikipedia.org/wiki/Java_collections_framework): ``` Collection implementations in pre-JDK 1.2 versions of the Java platform included few data structure classes, but did not contain a collections framework.[3] The standard methods for grouping Java objects were via the array, the Vector, and the Hashtable classes, which unfortunately were not easy to extend, and did not implement a standard member interface.[4] To address the need for reusable collection data structures, several independent frameworks were developed,[3] the most used being Doug Lea's Collections package,[5] and ObjectSpace Generic Collection Library (JGL),[6] whose main goal was consistency with the C++ Standard Template Library (STL).[7] ``` 可知，早期的Java Group通过Array, Vector, HashTable这些类来实现，但是他们难扩展，后期大神们创建了独立的Java Data Structure Framework，并且在日后这些framework被build进入JDK中，慢慢形成了Java Collection Framework。 # 1.Java集合概述 Java的集合类位于java.util.*包下，大体分为2类，Collection和Map，另外就是2个工具类。Concurrent是jdk1.5引入的（在这之前java语言内置对多线程的支持比较有限），主要代码由Doug Lea完成。 ## Collection集合概述 1. 概述 * Collection包含3个分支 ``` AbstractCollection是抽象类，实现了部分Collection中的API，如contains，toArray, remove, toString等方法。 ``` * Queue ``` 队列是一种特殊的线性表，允许在表的头部进行删除操作，在表的尾部进行插入操作。有2个继承接口，BlockingQueue(阻塞队列)和Deque(双向队列)。AbstractQueue是抽象类，实现了Queue中的大部分API，常见实现类有LinkedQueue。 ``` * List ``` List是一个有序的队列，每个元素都有它的索引，第一个元素的索引值为0。AbstractList是抽象类，实现了List中的大部分API，常见实现类有LinkedList, ArrayList, Vector, Stack。 ``` * Set ``` Set是一个不允许有重复元素的集合。 AbstractSet是抽象类，实现了Set中的大部分API，常见的实现类有HashSet, TreeSet。 ``` ## Map集合概述 1. 概述 * Map包含1个分支 ``` Map是一个映射接口，即key-value的键值对。AbstractMap是抽象类，实现了Map中的大部分API，HashMap, TreeMap, WeakHashMap是其实现类。 ``` 2. 源码阅读 `接口定义` ```java public interface Map ``` `常用方法` ```java abstract void clear() abstract boolean containsKey(Object key) abstract boolean containsValue(Object value) abstract Set> entrySet() abstract boolean equals(Object object) abstract V get(Object key) abstract int hashCode() abstract boolean isEmpty() abstract Set keySet() abstract V put(K key, V value) abstract void putAll(Map extends K, ? extends V> map) abstract V remove(Object key) abstract int size() abstract Collection values() ``` ``` Map 是一个键值对(key-value)映射接口。Map映射中不能包含重复的键；每个键最多只能映射到一个值。 Map 接口提供三种collection 视图，允许以键集(keySet())、值集(values())或键-值(entrySet())映射关系集的形式查看某个映射的内容。 Map 映射顺序。有些实现类，可以明确保证其顺序，如 TreeMap；另一些映射实现则不保证顺序，如 HashMap 类。 Map 的实现类应该提供2个“标准的”构造方法：第一个，void（无参数）构造方法，用于创建空映射；第二个，带有单个 Map 类型参数的构造方法，用于创建一个与其参数具有相同键-值映射关系的新映射。实际上，后一个构造方法允许用户复制任意映射，生成所需类的一个等价映射。尽管无法强制执行此建议（因为接口不能包含构造方法），但是 JDK 中所有通用的映射实现都遵从它。 ``` [Map的三种Collection视图例子 MapTest01.java] ```java // key视图 Set keys = hashMap.keySet(); Iterator iteratorKeys = keys.iterator(); while (iteratorKeys.hasNext()) { System.out.println(iteratorKeys.next()); } // value视图 Collection values = hashMap.values(); Iterator iteratorValues = values.iterator(); while (iteratorValues.hasNext()) { System.out.println(iteratorValues.next()); } // key-value视图 Set> entrySets = hashMap.entrySet(); Iterator> iteratorEntrySets = entrySets.iterator(); while (iteratorEntrySets.hasNext()) { Entry entry = iteratorEntrySets.next(); System.out.println(String.format("key: %s, value: %s", entry.getKey(), entry.getValue())); } ``` ## Concurrent包下的集合概述 1. 概述 * Concurrent主要有3个package组成 * java.util.concurrent ``` 提供大部分关于并发的接口和类，如BlockingQueue, ConcurrentHashMap, ExecutorService等 ``` * java.util.concurrent.atomic ``` 提供所有的原子类操作，如AtomicInteger, AtomicLong等 ``` * java.util.concurrent.locks ``` 提供锁相关的类，如Lock, ReentrantLock, ReadWriteLock, Confition等 ``` # 2.Java集合详解 ## Collection集合下常用实现类详解 ### Iterator接口源码解析 `总结` ``` iterator.remove()方法必须要在调用了next()方法之后，否则会报IllegalStateException。 if the next method has not yet been called, or the remove method has already been called after the last call to the next method ``` `常用方法` ```java boolean hasNext() E next() void remove() ``` ### Collection接口源码解析 `接口定义`： ```java /* 说明： Collection集合用于存Object的，不支持存储基础数据类型，这是由Collection接口的定义决定的： Collection 这样写会报错： Syntax error, insert "Dimensions" to complete ReferenceType List ints = new ArrayList(); */ public interface Collection extends Iterable ``` `常用方法` ```java abstract boolean add(E object) // addAll参数为E或E的子类 abstract boolean addAll(Collection extends E> collection) abstract void clear() abstract boolean contains(Object object) abstract boolean containsAll(Collection> collection) abstract boolean equals(Object object) abstract int hashCode() abstract boolean isEmpty() abstract Iterator iterator() abstract boolean remove(Object object) abstract boolean removeAll(Collection> collection) abstract boolean retainAll(Collection> collection) /* * Returns the number of elements in this collection. If this collection * contains more than Integer.MAX_VALUE elements, returns * Integer.MAX_VALUE. * Integer.MIN_VALUE是-（2的31次方），Integer.MAX_VALUE是2的31次方减1 */ abstract int size() abstract T[] toArray(T[] array) abstract Object[] toArray() ``` ### List接口源码解析 `总结` ``` List是有序的，支持随机访问（通过索引下标访问） List允许重复的值（原因是它的数据存储方式） ``` `常用方法` ```java boolean add(E) void add(int, E) boolean addAll(int, Collection extends E>) boolean addAll(Collection extends E>) void clear() boolean contains(Object) //AbstractCollection中通过iterator迭代遍历判断 ArrayList中通过调用indexOf(o) >= 0 来判断是否包含 boolean containsAll(Collection>) boolean equals(Object) E get(int) int hashCode() int indexOf(Object) boolean isEmpty() Iterator iterator() int lastIndexOf(Object) ListIterator listIterator() ListIterator listIterator(int) E remove(int) boolean remove(Object) boolean removeAll(Collection>) boolean retainAll(Collection> a) // b.retainAll(a) 移除b中有而a中没有的所有元素，所以结果是a的子集 E set(int, E) int size() List subList(int, int) Object[] toArray() T[] toArray(T[]) ``` ```java ListIterator.java boolean hasNext() boolean hasPrevioud() E next() E previous() int nextIndex() int previousIndex() ``` #### AbstractCollection抽象类源码解析 `总结` ``` AbstractCollection是个抽象类，继承自Collection接口，并实现了其中的方法，同时添加了toString()方法 ``` `常用方法` ```java private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 减8的原因是某些VMs存储了数据的header private static T[] finishToArry(T[] r, Iterator> it) // 用于将集合转换为数组 private static int hugeCapacity(int minCapacity) // 用于finishToArry boolean add(E e) // 未实现 boolean addAll(int index, Collection extends E> c) // 未实现 void clear() boolean contains(Object o) // 迭代遍历判断 boolean containsAll(Collection> c) // for循环遍历c，然后通过调用contains判断 boolean isEmpty() // 通过判断size()==0，size()未实现 Iterator iterator() // 未实现 boolean remove(Object o) //迭代器遍历删除 boolean removeAll(Collection> c) boolean retainAll(Collection> c) int size(); Object[] toArray() T[] toArray(T[]) String toString() // 迭代遍历集合，通过StringBuilder接收组合输出 ``` #### AbstractList源码解析 `总结` ``` AbstractList中有Itr(继承Iterator)和ListItr(继承ListIterator)两个内部类 在迭代遍历过程中，如果出现对集合的写的行为（list.remove(obj)），会报出ConcurrentModificationException。 AbstractList中仍然没有实现add方法 ``` ```java // list调用remove方法会导致modCount的值改变 private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } // 通过调用iterator.remove()可以保证不会报ConcurrentModificationException public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } ``` ##### ArrayList源码解析和使用 `总结` 1. ArrayList是一个数据集合，相当于一个动态数组(Object[] elementData)。与Java中的数据相比，它的容量能动态增长，默认长度时10(DEFAULT_CAPACITY)，扩容时新的容量=原始容量 + 原始容量>>1 2. ArrayList实现了RandomAccess接口（Marker Interface），又由于其数据以数据存储，因此支持快速随机查找，但是修改和删除效率不高 ```java // Collections中通过RandomAccess接口判断 public static int binarySearch(List extends Comparable super T>> list, T key) { if (list instanceof RandomAccess || list.size() extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable ``` 1. Vector是一个矢量队列，支持比本的添加、修改、删除、遍历等功能 2. Vector实现了RandomAccess接口，即支持随机访问功能（get(int index)） 3. Vector中的public API都是加了synchronized关键字来保证线程安全 ##### Stack源码解析和使用 `总结` ``` Stack是栈，特性是先进后出(FILO, First In Last Out) Stack是继承自Vector，也是通过数据实现的 ``` `常用方法` ```java Object push(Object element) // 把对象压入堆栈 Object pop() // 移除堆栈顶部对象，并作为此方法的返回值返回该对象 Object peek() // 查看堆栈顶部的对象，但不从堆栈中移除它 ``` #### AbstractSequentialList抽象类源码解析 `总结` ``` 这个抽象类没什么特别 ``` ##### LinkedList源码解析和使用 `总结` ```java public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable {} ``` ``` LinkedList实现了Deque接口，能对它进行双向列表操作，也就是说顺序访问会非常高效，随机访问效率比较低 LinkedList不是线程安全的，可以通过List list = Collections.synchronizedList(new LinkedList(...))来转换，不过LinkedList的数据类型会丢失 LinkedList中使用Node对象来存储数据 ``` `常用方法` ```java boolean add(E element) // offer属于 offer in interface Deque, add 属于 add in interface Collection void(int index, E element) // 判断index==size，=就linkLast, or linkBefore void addFirst(E element) void addLast(E element) void clear() // 清空，注意GC Object clone() // 浅拷贝 shallow copy Iterator descendingIterator() // 倒着输出 E element() // 获取第一个元素 E get(int index) E getFirst(); E getLast(); int indexOf(Object object) int lastIndexOf(Object object) ListIterator listIterator(int index) boolean offer(E element) // offer属于 offer in interface Deque, add 属于 add in interface Collection boolean offerFirst(E element) boolean offerLast(E element) E peek() // 返回链表中的第一个元素，并且不会移除 E peekFirst() // 和peek没啥区别 E peekLast() E poll() // 返回链表中的第一个元素，并且会移除掉 E pollFirst() // 链表为空时会返回null E pollLast() E pop() // 链表为空时会报NoSuchElementException，这就是区别 void push(E e) // 添加到链表的第一个元素 E remove（） // 删除第一个元素 E remove E set(int index, E element) // 替换指定位置的元素 ``` LinkedList可以作为FIFO的队列，使用如下方法： ```java // Queue boolean add(e) // add比offer的区别在于add时如果capacity超了，会报错，而offer不会 boolean offer(e) E remove() // 返回队列的第一个元素，并且删除，如果队列为空，报NoSuchElementException E poll() // 返回队列的第一个元素，并且删除，如果队列为空，返回null E element() // 返回队列的第一个元素，不删除，如果队列为空，报NoSuchElementException E peek() // 返回队列的第一个元素，不删除，如果队列为空，返回null ``` LinkedList也可以作为FILO的栈，使用如下方法： ```java push(e) pop() peek() ``` `源码解析` ```java private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } ``` LinkedList在内部定义了一个叫做Node类型的静态内部类，Node就是一个节点，链表中的节点，有3个属性。 ```java // 3个属性 transient int size = 0; // 集合链表内节点数量 transient Node first; // 首节点 transient Node last; // 尾节点 ``` ```java // Appends the specified element to the end of this list public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ... ``` ### Set接口源码解析 `总结` ``` Set是继承自Collection的接口，是一个不允许有重复元素的结合。 AbstractSet是一个抽象类，继承自AbstractCollection，AbstractCollection实现了Set中的绝大部分函数 HashSet和TreeSet是Set的两个实现类 HashSet依赖HashMap，它实际上是通过HashMap实现的，HashSet中的元素是无序的 TreeSet依赖TreeMap，它实际上是通过TreeMap实现的，TreeSet中的元素是有序的 ``` #### AbstractSet源码解析 AbstractSet没有对Set做多少的实现，其继承了AbstractCollection `源码解析` ```java public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Collection c = (Collection) o; if (c.size() != size()) return false; try { return containsAll(c); } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; } } ``` ##### HashSet源码解析和使用 `总结` ``` HashSet是一个没有重复元素的集合，它是由HashMap实现的（HashMap中key不能重复），不保证元素的顺序，而且HashSet允许使用null元素。 HashSet是非同步的，因此如果多线程同时访问一个HashSet，而其中至少有一个线程修改了该HashSet的话，那么需要保持外部同步，通常可以对该Set的对象封装来完成同步操作，也可以使用Collections.synchronizedSet方法来完成。 HashSet是通过Iterator迭代遍历的 ``` `常用方法` ```java HashSet() HashSet(int initialCapacity) HashSet(int initialCapacity, float loadFactor) HashSet(int initialCapacity, float loadFactor, boolean dummy) HashSet(Collection extends E> c) boolean add(E) void clear() Object clone() boolean contains(Object object) boolean isEmpty() Iterator iterator() boolean remove(Object object) int size() ``` `源码解析` ```java private transient HashMap map; // Dummy value to associate with an Object in the backing Map private transient HashMap map; // new一个HashSet的时候其实是new的HashMap public HashSet() { map = new HashMap<>(); } /* * Constructs a new set containing the elements in the specified * collection. The HashMap is created with default load factor * (0.75) and an initial capacity sufficient to contain the elements in * the specified collection. * * @param c the collection whose elements are to be placed into this set * @throws NullPointerException if the specified collection is null 调用的是Math.max((int) (c.size()/.75f) + 1, 16), 比较(int) (c.size()/.75f) + 1和16的大小 选择加载因子为.75是出于效率的考虑（时间和空间成本） 如果HashMap的当前size >= threadhold(也就是Math.max((int) (c.size()/.75f) + 1, 16))，那么在添加元素的时候，size是要翻倍的，也就是说HashMap的容量必须是2的指数，具体跟踪put方法 */ public HashSet(Collection extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } public V put(K key, V value) { if (table == EMPTY_TABLE) { /* 会重新计算capacity int capacity = roundUpToPowerOf2(toSize); roundUpToPowerOf2（toSize） return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); } */ inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); // 这里调用addEntry return null; } // 迭代遍历的时候遍历的是key public Iterator iterator() { return map.keySet().iterator(); } // add的时候插入的是key public boolean add(E e) { return map.put(e, PRESENT)==null; } /** 浅拷贝 * Returns a shallow copy of this HashSet instance: the elements * themselves are not cloned. * * @return a shallow copy of this set */ public Object clone() { try { HashSet newSet = (HashSet) super.clone(); newSet.map = (HashMap) map.clone(); return newSet; } catch (CloneNotSupportedException e) { throw new InternalError(); } } /** * Save the state of this HashSet instance to a stream (that is, * serialize it). * * @serialData The capacity of the backing HashMap instance * (int), and its load factor (float) are emitted, followed by * the size of the set (the number of elements it contains) * (int), followed by all of its elements (each an Object) in * no particular order. */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out HashMap capacity and load factor s.writeInt(map.capacity()); s.writeFloat(map.loadFactor()); // Write out size s.writeInt(map.size()); // Write out all elements in the proper order. for (E e : map.keySet()) s.writeObject(e); } /** * Reconstitute the HashSet instance from a stream (that is, * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in HashMap capacity and load factor and create backing HashMap int capacity = s.readInt(); float loadFactor = s.readFloat(); map = (((HashSet)this) instanceof LinkedHashSet ? new LinkedHashMap(capacity, loadFactor) : new HashMap(capacity, loadFactor)); // Read in size int size = s.readInt(); // Read in all elements in the proper order. for (int i=0; i extends AbstractSet implements NavigableSet, Cloneable, Serializable {} ``` ``` TreeSet是一个有序并且没有重复的Set集合，它是通过TreeMap实现的 TreeSet实现了NavigableSet接口，因此其支持集合的导航方法，如lower（返回小于）, floor（返回小于等于）, ceiling（返回大于等于）, higher（返回大于），如果不存在这样的元素，则返回null ``` `源码解析` ```java // The backing map. 数据存储在这个对象中 private transient NavigableMap m; private static final Object ORESENT = new Obect(); public TreeSet() { this(new TreeMap()); } public TreeSet(Collection extends E> c) { this(); addAll(c); } // 带比较器的构造函数 public TreeSet(Comparator super E> comparator) { this(new TreeMap<>(comparator)); } TreeSet(NavigableMap m) { this.m = m; } public TreeSet(SortedSet s) { this(s.comparator()); addAll(s); } // 迭代器 public Iterator iterator() { return m.navigableKeySet().iterator(); } public boolean add(E e) { return m.put(e, PRESENT)==null; } /* Returns the least key greater than or equal to the given key, or {@code null} if there is no such key. 返回集合中大于等于给定元素的最小元素，有点绕，还是英文比较好理解 */ public E ceiling(E e) { return m.ceilingKey(e); } /* Returns the least key strictly greater than the given key, or {@code null} if there is no such key. 返回集合中大于给定元素的最小元素 */ public E higher(E e) { return m.higherKey(e); } /* Returns the greatest key strictly less than the given key, or {@code null} if there is no such key. 返回集合中小于给定元素的最大元素 */ public E lower(E e) { return m.lowerKey(e); } /* Returns the greatest key less than or equal to the given key, or {@code null} if there is no such key. 返回几何中小于或等于给定元素的最大元素 */ public E floor(E e) { return m.floorKey(e); } ``` ### Queue接口源码解析 `源码分析` ```java public interface Queue extends Collection { boolean add(e) // add比offer的区别在于add时如果capacity超了，会报错，而offer不会 boolean offer(e) E remove() // 返回队列的第一个元素，并且删除，如果队列为空，报NoSuchElementException E poll() // 返回队列的第一个元素，并且删除，如果队列为空，返回null E element() // 返回队列的第一个元素，不删除，如果队列为空，报NoSuchElementException E peek() // 返回队列的第一个元素，不删除，如果队列为空，返回null } ``` ### Deque接口源码解析 `总结` ``` 双向队列，继承自Queue接口，同时提供了丰富的操作队列的方法，具体可参考LinkedList源码分析 ``` ##### LinkedList使用 Go to here [LinkedList源码解析和使用](#LinkedList源码解析和使用) ## Map集合下常用实现类详解 `总结` ``` Map是一个键值对的接口，Map AbstractMap实现了Map接口，但是几乎没有实现Map中的方法，但是却定义了一些常用的方法 SortedMap继承自Map接口，SortedMap中的内容是排序了的键值对，排序的方法是通过比较器（Comparator） NavigableMap是继承自SortedMap的接口，相对于SortedMap，NavigableMap有一系列的导航方法，如获取>, <, >=, <=的值 TreeMap继承自AbstractMap，实现了NavigableMap接口，因此，TreeMap是有序的键值对 HashMap继承自AbstractMap，没有实现SortedMap，因此，HashMap不是有序的键值对。HashMap允许插入key或者value为null的元素 Hashtable没有继承自AbstractMap，继承的是Dictionary，实现了Map接口，因此，Hashtable是无序的键值对。Hashtable不允许插入key或者value为null的元素，Hashtable的方法加了synchronized关键字，保证了线程的安全。 WeakhashMap继承自AbstractMap，大致来说它与HashMap的键类型不同，WeakHashMap使用的是“弱键”（内存不足时会被GC收掉） ``` `源码分析` ```java void clear(); boolean containsKey(Object key); boolean containsValue(Object value); Set entrySet(); boolean equals(Object o); V get(Object obj); boolean isEmpty(); Set keySet(); // 返回key的集合，因为key不重复，所以用Set接收 V put(K k, V v); void putAll(Map extends K, ? extends V> m); V remove(Object key); int size(); Collections values(); // 返回value的结合，values是重复的 // Map中还有一个内置的接口 Map#entrySet() interface Entry { K getKey(); V getValue(); int hashCode(); V setValue(V); boolean equals(Object obj) } ``` #### AbstractMap接口源码解析 AbstractMap实现了Map接口，实现了一些通用的方法 `源码解析` ```java // 巧妙的写法 private static boolean eq(Object o1, Object o2) { return o1 == null ? o2 == null : o1.equals(o2); } ``` ##### HashMap源码解析和使用 `定义` ```java public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {} ``` `构造函数` ```java public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); // initial capacity=16 load factor=0.75 } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) {} public HashMap(Map extends K, ? extends V> m) {} ``` `public method` ```java void clear() Object clone() boolean containsKey(Object key) boolean containsValue(Object value) Set> entrySet() V get(Object obj) boolean isEmpty() Set keySet() V put(K k, V v) void putAll(Map extends K, ? extends V>) V remove(Object obj) int size() String toString() Collection values() ``` `源码解析` ```java // 数据存储在这里，一个叫table的变量中 transient Entry[] table = (Entry[]) EMPTY_TABLE; // 看下Entry的定义，每一个Entry是一个单向链表 static class Entry implements Map.Entry { final K key; V value; Entry next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; } } // 接下来我们就看下HashMap是如何存储值的。我们都知道HashMap中使用put(K k, V v)来存储值 public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); // 存储null key，直接调价到table[0]中 int hash = hash(key); // 首先根据key计算出hash值 int i = indexFor(hash, table.length); // 再根据hash值，计算出数据索引，也就是Entry在table中的索引 // 然后根据索引找到table中的Entry（是一个单向链表），通过e.next循环遍历单项链表 for (Entry e = table[i]; e != null; e = e.next) { Object k; // 将key与每一个Entry的key进行对比，哈希值进行对比，如果key已经存在就替换掉旧值，并且返回旧值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 如果key不存在Entry链表中，就新建一个Entry addEntry(hash, key, value, i); return null; } // addEntry的时候索引值为0， private V putForNullKey(V value) { for (Entry e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } // 在table中的index是0，所以HashMap有一个固定存储key为null的值，此位置为table的第一个位置 void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); // size翻倍 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } // 插入null值之后，循环调用Map#put方法插入1-18 ::hash:: 0 ::key:: null ::value:: 1 ::bucketIndex:: 0 ::hash:: 50 ::key:: 1 ::value:: value 1 ::bucketIndex:: 2 ::hash:: 49 ::key:: 2 ::value:: value 2 ::bucketIndex:: 1 ::hash:: 48 ::key:: 3 ::value:: value 3 ::bucketIndex:: 0 ::hash:: 55 ::key:: 4 ::value:: value 4 ::bucketIndex:: 7 ::hash:: 54 ::key:: 5 ::value:: value 5 ::bucketIndex:: 6 ::hash:: 53 ::key:: 6 ::value:: value 6 ::bucketIndex:: 5 ::hash:: 52 ::key:: 7 ::value:: value 7 ::bucketIndex:: 4 ::hash:: 59 ::key:: 8 ::value:: value 8 ::bucketIndex:: 11 ::hash:: 58 ::key:: 9 ::value:: value 9 ::bucketIndex:: 10 ::hash:: 1650 ::key:: 10 ::value:: value 10 ::bucketIndex:: 2 ::hash:: 1614 ::key:: 11 ::value:: value 11 ::bucketIndex:: 14 ::hash:: 1615 ::key:: 12 ::value:: value 12 ::bucketIndex:: 15 ::hash:: 1612 ::key:: 13 ::value:: value 13 ::bucketIndex:: 12 ::hash:: 1613 ::key:: 14 ::value:: value 14 ::bucketIndex:: 13 ::hash:: 1610 ::key:: 15 ::value:: value 15 ::bucketIndex:: 10 ::hash:: 1611 ::key:: 16 ::value:: value 16 ::bucketIndex:: 11 ::hash:: 1608 ::key:: 17 ::value:: value 17 ::bucketIndex:: 8 ``` `总结` ``` HashMap继承于AbstractMap类，实现了Map接口。Map是"key-value键值对"接口，AbstractMap实现了"键值对"的通用函数接口。 HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。 table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。 size是HashMap的大小，它是HashMap保存的键值对的数量。 threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。 　　loadFactor就是加载因子。 　　modCount是用来实现fail-fast机制的。 ``` ##### WeakHashMap源码解析和使用 `定义` ```java public class WeakhashMap extends AbstractMap implements Map {} ``` `构造函数和HashMap类似` ```java public WeakHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public WeakHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public WeakHashMap(int initialCapacity, float loadFactor) {} public WeakHashMap(Map extends K, ? extends V> m) {} ``` `重要变量` ```java private static final int DEFAULT_INITIAL_CAPACITY = 16; private static final int MAXIMUM_CAPACITY = 1 << 30; private static final float DEFAULT_LOAD_FACTOR = 0.75F; Entry[] table; private int size; private int threshold; private final float loadFactor; private final ReferenceQueue