Java集合框架

本文整理自 兰亭风雨 的专栏。

Java 集合框架

Java集合框架可以大致分为五个部分：List 列表、Set 列表、Map映射、迭代器(Iterator、Enumeration)、工具类(Arrays、Conllection)。

从上图中可以看出，集合类主要分为两大类：Collection 和 Map。

Java 集合框架的组成

接口

Collection接口

Collection 是 List、Set 等集合高度抽象出来的接口，它包含了这些集合的基本操作，它主要又分为两大部分：List 和 Set。

List接口

List 接口通常表示一个列表（数组、队列、链表、栈等），其中的元素可以重复，常用实现类为 ArrayList 和 LinkedList ，另外还有不常用的 Vector。另外，LinkedList 还是实现了 Queue 接口，因此也可以作为队列使用。

Set接口

Set 接口通常表示一个集合，其中的元素不允许重复（通过 hashcode 和 equals 函数保证），常用实现类有 HashSet 和 TreeSet ，HashSet 是通过 Map 中的 HashMap 实现的，而 TreeSet 是通过 Map 中的 TreeMap 实现的。另外，TreeSet 还实现了 SortedSet 接口，因此是有序的集合（集合中的元素要实现 Comparable 接口，并覆写 Compartor 函数才行）。

Map接口

Map 是一个映射接口，其中的每个元素都是一个 key-value 键值对，同样抽象类 AbstractMap 通过适配器模式实现了 Map 接口中的大部分函数，TreeMap、HashMap、WeakHashMap 等实现类都通过继承 AbstractMap 来实现，另外，不常用的 HashTable 直接实现了 Map 接口，它和 Vector 都是 JDK1.0 就引入的集合类。

Iterator接口

Iterator 是遍历集合的迭代器（不能遍历 Map，只用来遍历 Collection），Collection 的实现类都实现了 iterator() 函数，它返回一个 Iterator 对象，用来遍历集合，ListIterator 则专门用来遍历 List。而 Enumeration 则是 JDK1.0 时引入的，作用与 Iterator 相同，但它的功能比 Iterator 要少，它只能再 Hashtable、Vector 和 Stack 中使用。

其他

工具类

Arrays 和 Collections 是用来操作数组、集合的两个工具类，例如在 ArrayList 和 Vector 中大量调用了 Arrays.Copyof() 方法，而 Collections 中有很多静态方法可以返回各集合类的 synchronized 版本，即线程安全的版本，当然了，如果要用线程安全的结合类，首选 Concurrent 并发包下的对应的集合类。

抽象类

我们看到，抽象类 AbstractCollection、AbstractList 和 AbstractSet 分别实现了 Collection、List 和 Set 接口，这就是在 Java 集合框架中用的很多的适配器设计模式，用这些抽象类去实现接口，在抽象类中实现接口中的若干或全部方法，这样下面的一些类只需直接继承该抽象类，并实现自己需要的方法即可，而不用实现接口中的全部抽象方法。

实体类

ArrayList

简介

• ArrayList 是基于数组实现的，是一个动态数组，其容量能自动增长，类似于 C 语言中的动态申请内存，动态增长内存。
• ArrayList 不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类，也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
• ArrayList 实现了 Serializable 接口，因此它支持序列化，能够通过序列化传输，实现了 RandomAccess 接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了 Cloneable 接口，能被克隆。

源码特征

• ArrayList 有三个构造器

  • 无参构造方法构造的 ArrayList 的容量默认为10
  • 带容量大小参数的构造方法
  • 带有 Collection 参数的构造方法，将 Collection 转化为数组赋给 ArrayList 的实现数组 elementData

• 扩充容量的方法 ensureCapacity ：ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍加1，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后用 Arrays.copyof() 方法将元素拷贝到新的数组（详见下面的第3点）。从中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用 ArrayList，否则建议使用 LinkedList。

• ArrayList 的实现中大量地调用了 Arrays.copyof() 和 System.arraycopy() 方法。

  • Arrays.copyof() 方法实际上是在其内部又创建了一个长度为 newlength 的数组，调用 System.arraycopy() 方法，将原来数组中的元素复制到了新的数组中。
  • System.arraycopy() 方法。该方法被标记了 native，调用了系统的 C/C++ 代码，在 JDK 中是看不到的，但在 openJDK 中可以看到其源码。该函数实际上最终调用了 C 语言的 memmove() 函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java 强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。

• 注意 ArrayList 的两个转化为静态数组的 toArray 方法。

  • Object[] toArray() 方法。该方法有可能会抛出 java.lang.ClassCastException 异常，如果直接用向下转型的方法，将整个 ArrayList 集合转变为指定类型的 Array 数组，便会抛出该异常，而如果转化为 Array 数组时不向下转型，而是将每个元素向下转型，则不会抛出该异常，显然对数组中的元素一个个进行向下转型，效率不高，且不太方便。

  • <T> T[] toArray(T[] a) 方法。该方法可以直接将 ArrayList 转换得到的 Array 进行整体向下转型（转型其实是在该方法的源码中实现的），且从该方法的源码中可以看出，参数 a 的大小不足时，内部会调用 Arrays.copyOf 方法，该方法内部创建一个新的数组返回，因此对该方法的常用形式如下：

    public static Integer[] vectorToArray2(ArrayList<Integer> v) {  
        Integer[] newText = (Integer[])v.toArray(new Integer[0]);  
        return newText;  
    }

• ArrayList 基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

• 在查找给定元素索引值等的方法中，源码都将该元素的值分为 null 和不为 null 两种情况处理，ArrayList 中允许元素为 null。

LinkedList

简介

• LinkedList 是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。
• LinkedList 同样是非线程安全的，只在单线程下适合使用。
• LinkedList 实现了 Serializable 接口，因此它支持序列化，能够通过序列化传输，实现了 Cloneable 接口，能被克隆。

源码特征

• LinkedList 的实现是基于双向循环链表的，且头结点中不存放数据(即使用虚拟头结点)

• LinkedList 有两个不同的构造方法。无参构造方法直接建立一个仅包含 head 节点的空链表，包含 Collection 的构造方法，先调用无参构造方法建立一个空链表，而后将 Collection 中的数据加入到链表的尾部后面。

• 在查找和删除某元素时，源码中都划分为该元素为 null 和不为 null 两种情况来处理，LinkedList 中允许元素为 null。

• LinkedList 是基于链表实现的，因此不存在容量不足的问题，所以这里没有扩容的方法。

• 注意源码中的 Entry<E> entry(int index) 方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将 index 与长度 size 的一半比较，如果 index<size/2 ，就只从位置 0 往后遍历到位置 index 处，而如果 index>size/2，就只从位置 size 往前遍历到位置 index 处。这样可以减少一部分不必要的遍历，从而提高一定的效率（实际上效率还是很低）。

  // 获取双向链表中指定位置的节点  
  private Entry<E> entry(int index) {  
      if (index < 0 || index >= size)  
          throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+size);  
      Entry<E> e = header;  
      // 获取index处的节点。  
      // 若index < 双向链表长度的1/2,则从前先后查找;  
      // 否则，从后向前查找。  
      if (index < (size >> 1)) {  
          for (int i = 0; i <= index; i++)  
              e = e.next;  
      } else {  
          for (int i = size; i > index; i--)  
              e = e.previous;  
      }  
      return e;  
  }

• 注意链表类对应的数据结构 Entry。如下：

  // 双向链表的节点所对应的数据结构。  
  // 包含3部分：上一节点，下一节点，当前节点值。  
  private static class Entry<E> {  
      // 当前节点所包含的值  
      E element;  
      // 下一个节点  
      Entry<E> next;  
      // 上一个节点  
      Entry<E> previous;  
   
      /**  
       * 链表节点的构造函数。  
       * 参数说明：  
       *   element  —— 节点所包含的数据  
       *   next      —— 下一个节点  
       *   previous —— 上一个节点  
       */ 
      Entry(E element, Entry<E> next, Entry<E> previous) {  
          this.element = element;  
          this.next = next;  
          this.previous = previous;  
      }  
  }

• LinkedList 是基于链表实现的，因此插入删除效率高，查找效率低（虽然有一个加速动作）。

• 要注意源码中还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。

Vector

简介

• Vector 也是基于数组实现的，是一个动态数组，其容量能自动增长。
• Vector 是 JDK1.0 引入了，它的很多实现方法都加入了同步语句，因此是线程安全的（其实也只是相对安全，有些时候还是要加入同步语句来保证线程的安全），可以用于多线程环境。
• Vector 实现了 Serializable 接口，因此它支持序列化，实现了 Cloneable 接口，能被克隆，实现了 RandomAccess 接口，支持快速随机访问。

源码特征

• Vector 有四个不同的构造方法
  • 无参构造方法的容量为默认值10
  • 仅包含容量的构造方法则将容量增长量（从源码中可以看出容量增长量的作用，第二点也会对容量增长量详细说）明置为0。
  • 指定 Vector “容量大小”和”增长系数”的构造函数。
  • 指定集合的 Vector 构造函数。

• 注意扩充容量的方法 ensureCapacityHelper：与 ArrayList 相同，Vector 在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就先看构造方法中传入的容量增长量参数 CapacityIncrement 是否为0，如果不为0，就设置新的容量为就容量加上容量增长量，如果为0，就设置新的容量为旧的容量的2倍，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后同样用 Arrays.copyof() 方法将元素拷贝到新的数组。

• 很多方法都加入了 synchronized 同步语句，来保证线程安全。

• 同样在查找给定元素索引值等的方法中，源码都将该元素的值分为 null 和不为 null 两种情况处理，Vector 中也允许元素为 null。
• 其他很多地方都与 ArrayList 实现大同小异，Vector 现在已经基本不再使用。

HashMap

简介

• HashMap 是基于哈希表实现的，每一个元素是一个 key-value 对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
• HashMap 是非线程安全的，只是用于单线程环境下，多线程环境下可以采用 concurrent 并发包下的 concurrentHashMap。
• HashMap 实现了 Serializable 接口，因此它支持序列化，实现了 Cloneable 接口，能被克隆。

源码特征

• 首先要清楚HashMap的存储结构，如下图所示：

  

  图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

• 首先看链表中节点的数据结构：

  // Entry是单向链表。  
  // 它是 “HashMap链式存储法”对应的链表。  
  // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  
  static class Entry<K,V> implements Map.Entry<K,V> {  
      final K key;  
      V value;  
      // 指向下一个节点  
      Entry<K,V> next;  
      final int hash;  
     
      // 构造函数。  
      // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"  
      Entry(int h, K k, V v, Entry<K,V> n) {  
          value = v;  
          next = n;  
          key = k;  
          hash = h;  
      }  
     
      public final K getKey() {  
          return key;  
      }  
     
      public final V getValue() {  
          return value;  
      }  
     
      public final V setValue(V newValue) {  
          V oldValue = value;  
          value = newValue;  
          return oldValue;  
      }  
     
      // 判断两个Entry是否相等  
      // 若两个Entry的“key”和“value”都相等，则返回true。  
      // 否则，返回false  
      public final boolean equals(Object o) {  
          if (!(o instanceof Map.Entry))  
              return false;  
          Map.Entry e = (Map.Entry)o;  
          Object k1 = getKey();  
          Object k2 = e.getKey();  
          if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
              Object v1 = getValue();  
              Object v2 = e.getValue();  
              if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                  return true;  
          }  
          return false;  
      }  
     
      // 实现hashCode()  
      public final int hashCode() {  
          return (key==null   ? 0 : key.hashCode()) ^  
                 (value==null ? 0 : value.hashCode());  
      }  
     
      public final String toString() {  
          return getKey() + "=" + getValue();  
      }  
     
      // 当向HashMap中添加元素时，绘调用recordAccess()。  
      // 这里不做任何处理  
      void recordAccess(HashMap<K,V> m) {  
      }  
     
      // 当从HashMap中删除元素时，绘调用recordRemoval()。  
      // 这里不做任何处理  
      void recordRemoval(HashMap<K,V> m) {  
      }  
  }

  它的结构元素除了 key、value、hash 外，还有 next ，next 指向下一个节点。另外，这里覆写了 equals 和 hashCode 方法来保证键值对的独一无二。

• HashMap共有四个构造方法。构造方法中提到了两个很重要的参数：初始容量和加载因子。这两个参数是影响 HashMap 性能的重要参数。

  • 容量表示哈希表中槽的数量（即哈希数组的长度），初始容量是创建哈希表时的容量（从构造函数中可以看出，如果不指明，则默认为16）。
    • 无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方。
  • 加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 操作（即扩容）。
    • 如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。

• HashMap 中 key 和 value 都允许为 null。

• 要重点分析下 HashMap 中用的最多的两个方法 put 和 get。先从比较简单的 get 方法着手，源码如下：

    // 获取key对应的value  
    public V get(Object key) {  
        if (key == null)  
            return getForNullKey();  
        // 获取key的hash值  
        int hash = hash(key.hashCode());  
        // 在“该hash值对应的链表”上查找“键值等于key”的元素  
        for (Entry<K,V> e = table[indexFor(hash, table.length)];  
             e != null;  
             e = e.next) {  
            Object k;  
  	//判断key是否相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
                return e.value;  
        }
  //没找到则返回null
        return null;  
    }  
     
    // 获取“key为null”的元素的值  
    // HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！  
    private V getForNullKey() {  
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
            if (e.key == null)  
                return e.value;  
        }  
        return null;  
    }

  • 首先，如果 key 为 null，则直接从哈希表的第一个位置 table[0] 对应的链表上查找。记住，key 为 null 的键值对永远都放在以 table[0] 为头结点的链表中，当然不一定是存放在头结点 table[0] 中。

  • 如果 key 不为 null，则先求的 key 的 hash 值，根据 hash 值找到在 table 中的索引，在该索引对应的单链表中查找是否有键值对的 key 与目标 key 相等，有就返回对应的 value，没有则返回 null。

  put方法稍微复杂些，代码如下：

    // 将“key-value”添加到HashMap中  
    public V put(K key, V value) {  
        // 若“key为null”，则将该键值对添加到table[0]中。  
        if (key == null)  
            return putForNullKey(value);  
        // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
     
        // 若“该key”对应的键值对不存在，则将“key-value”添加到table中  
        modCount++;
  //将key-value添加到table[i]处
        addEntry(hash, key, value, i);  
        return null;  
    }

  如果key为null，则将其添加到table[0]对应的链表中，putForNullKey的源码如下：

  // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置  
  private V putForNullKey(V value) {  
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
          if (e.key == null) {  
              V oldValue = e.value;  
              e.value = value;  
              e.recordAccess(this);  
              return oldValue;  
          }  
      }  
      // 如果没有存在key为null的键值对，则直接题阿见到table[0]处!  
      modCount++;  
      addEntry(0, null, value, 0);  
      return null;  
  }

  如果 key 不为 null，则同样先求出 key 的 hash 值，根据 hash 值得出在 table 中的索引，而后遍历对应的单链表，如果单链表中存在与目标 key 相等的键值对，则将新的 value 覆盖旧的 value，比将旧的 value 返回，如果找不到与目标 key 相等的键值对，或者该单链表为空，则将该键值对插入到改单链表的头结点位置（每次新插入的节点都是放在头结点的位置），该操作是有 addEntry 方法实现的，它的源码如下：

  // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。  
  void addEntry(int hash, K key, V value, int bucketIndex) {  
      // 保存“bucketIndex”位置的值到“e”中  
      Entry<K,V> e = table[bucketIndex];  
      // 设置“bucketIndex”位置的元素为“新Entry”，  
      // 设置“e”为“新Entry的下一个节点”  
      table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
      // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小  
      if (size++ >= threshold)  
          resize(2 * table.length);  
  }

  注意这里倒数第三行的构造方法，将 key-value 键值对赋给 table[bucketIndex]，并将其 next 指向元素 e，这便将 key-value 放到了头结点中，并将之前的头结点接在了它的后面。该方法也说明，每次 put 键值对的时候，总是将新的该键值对放在 table[bucketIndex] 处（即头结点处）。

  另外注意最后两行代码，每次加入键值对时，都要判断当前已用的槽的数目是否大于等于阀值（容量*加载因子），如果大于等于，则进行扩容，将容量扩为原来容量的2倍。

• 扩容 resize 方法：

  // 重新调整HashMap的大小，newCapacity是调整后的单位  
  void resize(int newCapacity) {  
      Entry[] oldTable = table;  
      int oldCapacity = oldTable.length;  
      if (oldCapacity == MAXIMUM_CAPACITY) {  
          threshold = Integer.MAX_VALUE;  
          return;  
      }  
     
      // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，  
      // 然后，将“新HashMap”赋值给“旧HashMap”。  
      Entry[] newTable = new Entry[newCapacity];  
      transfer(newTable);  
      table = newTable;  
      threshold = (int)(newCapacity * loadFactor);  
  }

  ​ 很明显，是新建了一个 HashMap 的底层数组，而后调用 transfer 方法，将就 HashMap 的全部元素添加到新的 HashMap 中（要重新计算元素在新的数组中的索引位置）。transfer 方法的源码如下：

  // 将HashMap中的全部元素都添加到newTable中  
  void transfer(Entry[] newTable) {  
      Entry[] src = table;  
      int newCapacity = newTable.length;  
      for (int j = 0; j < src.length; j++) {  
          Entry<K,V> e = src[j];  
          if (e != null) {  
              src[j] = null;  
              do {  
                  Entry<K,V> next = e.next;  
                  int i = indexFor(e.hash, newCapacity);  
                  e.next = newTable[i];  
                  newTable[i] = e;  
                  e = next;  
              } while (e != null);  
          }  
      }  
  }

  很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用 HashMap 的时，最好能提前预估下 HashMap 中元素的个数，这样有助于提高 HashMap 的性能。

• 注意 containsKey 方法和 containsValue 方法。前者直接可以通过 key 的哈希值将搜索范围定位到指定索引对应的链表，而后者要对哈希数组的每个链表进行搜索。

• 我们重点来分析下求 hash 值和索引值的方法，这两个方法便是 HashMap 设计的最为核心的部分，二者结合能保证哈希表中的元素尽可能均匀地散列。

  • 计算哈希值的方法如下：

    static int hash(int h) {
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

    它只是一个数学公式，JDK 这样设计对 hash 值的计算，自然有它的好处，至于为什么这样设计，我们这里不去追究，只要明白一点，用的位的操作使 hash 值的计算效率很高。

  • 由 hash 值找到对应索引的方法如下：

    static int indexFor(int h, int length) {
            return h & (length-1);
        }

    这个我们要重点说下，我们一般对哈希表的散列很自然地会想到用 hash 值对 length 取模（即除法散列法），Hashtable 中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap 中则通过 h&(length-1) 的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是 HashMap 对 Hashtable 的一个改进。

• 为什么哈希表的容量一定要是2的整数次幂?

  • length 为2的整数次幂的话，h&(length-1) 就相当于对 length 取模，这样便保证了散列的均匀，同时也提升了效率
  • length 为2的整数次幂的话，为偶数，这样 length-1 为奇数，奇数的最后一位是1，这样便保证了 h&(length-1) 的最后一位可能为0，也可能为1（这取决于 h 的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果 length 为奇数的话，很明显 length-1 为偶数，它的最后一位是0，这样 h&(length-1) 的最后一位肯定为0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间
  • 因此，length 取2的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。

Hashtable

简介

• Hashtable 同样是基于哈希表实现的，同样每个元素是一个 key-value 对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
• Hashtable 也是 JDK1.0 引入的类，是线程安全的，能用于多线程环境中。
• Hashtable 同样实现了 Serializable 接口，它支持序列化，实现了 Cloneable 接口，能被克隆。

源码特征

针对 Hashtable，我们同样给出几点比较重要的总结，但要结合与 HashMap 的比较来总结。

• 二者的存储结构和解决冲突的方法都是相同的。

• HashTable 在不指定容量的情况下的默认容量为11，而 HashMap 为16，Hashtable 不要求底层数组的容量一定要为2的整数次幂，而 HashMap 则要求一定为2的整数次幂。

• Hashtable 中 key 和 value 都不允许为 null，而 HashMap 中 key 和 value 都允许为 null（key 只能有一个为 null，而 value 则可以有多个为 null）。但是如果在 Hashtable 中有类似 put(null,null) 的操作，编译同样可以通过，因为 key 和 value 都是 Object 类型，但运行时会抛出 NullPointerException 异常，这是 JDK 的规范规定的。我们来看下 ContainsKey 方法和 ContainsValue 的源码：

   // 判断Hashtable是否包含“值(value)”  
    public synchronized boolean contains(Object value) {  
        //注意，Hashtable中的value不能是null，  
        // 若是null的话，抛出异常!  
        if (value == null) {  
            throw new NullPointerException();  
        }  
     
        // 从后向前遍历table数组中的元素(Entry)  
        // 对于每个Entry(单向链表)，逐个遍历，判断节点的值是否等于value  
        Entry tab[] = table;  
        for (int i = tab.length ; i-- > 0 ;) {  
            for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {  
                if (e.value.equals(value)) {  
                    return true;  
                }  
            }  
        }  
        return false;  
    }  
     
    public boolean containsValue(Object value) {  
        return contains(value);  
    }  
     
    // 判断Hashtable是否包含key  
    public synchronized boolean containsKey(Object key) {  
        Entry tab[] = table;  
  //计算hash值，直接用key的hashCode代替
        int hash = key.hashCode();    
        // 计算在数组中的索引值 
        int index = (hash & 0x7FFFFFFF) % tab.length;  
        // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素  
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
            if ((e.hash == hash) && e.key.equals(key)) {  
                return true;  
            }  
        }  
        return false;  
    }

  很明显，如果 value 为 null，会直接抛出 NullPointerException 异常，但源码中并没有对 key 是否为 null 判断，有点小不解！不过 NullPointerException 属于 RuntimeException 异常，是可以由 JVM 自动抛出的，也许对 key 的值在 JVM 中有所限制吧。

• Hashtable 扩容时，将容量变为原来的2倍加1，而 HashMap 扩容时，将容量变为原来的2倍。

• Hashtable 计算 hash 值，直接用 key 的 hashCode()，而 HashMap 重新计算了 key 的 hash 值，Hashtable 在求 hash 值对应的位置索引时，用取模运算，而 HashMap 在求位置索引时，则用与运算，且这里一般先用hash&0x7FFFFFFF 后，再对 length 取模，&0x7FFFFFFF 的目的是为了将负的hash值转化为正值，因为 hash值有可能为负数，而 &0x7FFFFFFF 后，只有符号外改变，而后面的位都不变。

TreeMap

简介

• TreeMap是基于红黑树实现的，这里只对红黑树做个简单的介绍，红黑树是一种特殊的二叉排序树，红黑树通过一些限制，使其不会出现二叉树排序树中极端的一边倒的情况，相对二叉排序树而言，这自然提高了查询的效率。

源码特征

• 存储结构：TreeMap的排序是基于对key的排序实现的，它的每一个Entry代表红黑树的一个节点，Entry的数据结构如下：

   static final class Entry<K,V> implements Map.Entry<K,V> {  
        // 键  
        K key;  
        // 值  
        V value;  
        // 左孩子  
        Entry<K,V> left = null;  
        // 右孩子  
        Entry<K,V> right = null;  
        // 父节点  
        Entry<K,V> parent;  
        // 当前节点颜色  
        boolean color = BLACK;  
     
        // 构造函数  
        Entry(K key, V value, Entry<K,V> parent) {  
            this.key = key;  
            this.value = value;  
            this.parent = parent;  
        }  
     
  。。。。。。
   }

• TreeMap一共有4个构造方法：

  • 无参构造方法

    public TreeMap() {  
        comparator = null;  
    }

    采用无参构造方法，不指定比较器，这时候，排序的实现要依赖 key.compareTo() 方法，因此 key 必须实现 Comparable 接口，并覆写其中的 compareTo 方法。

  • 带有比较器的构造方法

    public TreeMap(Comparator<? super K> comparator) {  
        this.comparator = comparator;  
    }

    采用带比较器的构造方法，这时候，排序依赖该比较器，key 可以不用实现 Comparable 接口。

  • 带 Map 的构造方法

    public TreeMap(Map<? extends K, ? extends V> m) {  
        comparator = null;  
        putAll(m);  
    }

    该构造方法同样不指定比较器，调用 putAll 方法将 Map 中的所有元素加入到 TreeMap 中。putAll 的源码如下：

    // 将map中的全部节点添加到TreeMap中  
    public void putAll(Map<? extends K, ? extends V> map) {  
        // 获取map的大小  
        int mapSize = map.size();  
        // 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value对”  
        if (size==0 && mapSize!=0 && map instanceof SortedMap) {  
            Comparator c = ((SortedMap)map).comparator();  
            // 如果TreeMap和map的比较器相等；  
            // 则将map的元素全部拷贝到TreeMap中，然后返回！  
            if (c == comparator || (c != null && c.equals(comparator))) {  
                ++modCount;  
                try {  
                    buildFromSorted(mapSize, map.entrySet().iterator(),  
                                null, null);  
                } catch (java.io.IOException cannotHappen) {  
                } catch (ClassNotFoundException cannotHappen) {  
                }  
                return;  
            }  
        }  
        // 调用AbstractMap中的putAll();  
        // AbstractMap中的putAll()又会调用到TreeMap的put()  
        super.putAll(map);  
    }

    显然，如果 Map 里的元素是排好序的，就调用 buildFromSorted 方法来拷贝 Map 中的元素，这在下一个构造方法中会重点提及，而如果 Map 中的元素不是排好序的，就调用 AbstractMap 的 putAll(map) 方法，该方法源码如下：

    public void putAll(Map<? extends K, ? extends V> m) {  
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())  
            put(e.getKey(), e.getValue());  
    }

    很明显它是将 Map 中的元素一个个 put（插入）到 TreeMap 中的，主要因为 Map 中的元素是无序存放的，因此要一个个插入到红黑树中，使其有序存放，并满足红黑树的性质。

  • 带有 SortedMap 的构造方法

    public TreeMap(SortedMap<K, ? extends V> m) {  
        comparator = m.comparator();  
        try {  
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);  
        } catch (java.io.IOException cannotHappen) {  
        } catch (ClassNotFoundException cannotHappen) {  
        }  
    }

    首先将比较器指定为 m 的比较器，这取决于生成 m 时调用构造方法是否传入了指定的构造器，而后调用 buildFromSorted 方法，将 SortedMap 中的元素插入到 TreeMap 中，由于 SortedMap 中的元素师有序的，实际上它是根据 SortedMap 创建的 TreeMap，将 SortedMap 中对应的元素添加到 TreeMap 中。

• 插入删除

  • 插入 put

    插入操作即对应 TreeMap 的 put 方法，put 操作实际上只需按照二叉排序树的插入步骤来操作即可，插入到指定位置后，再做调整，使其保持红黑树的特性。put 源码的实现：

          
    public V put(K key, V value) {  
        Entry<K,V> t = root;  
        // 若红黑树为空，则插入根节点  
        if (t == null) {  
        // TBD:  
        // 5045147: (coll) Adding null to an empty TreeSet should  
        // throw NullPointerException  
        //  
        // compare(key, key); // type check  
            root = new Entry<K,V>(key, value, null);  
            size = 1;  
            modCount++;  
            return null;  
        }  
        int cmp;  
        Entry<K,V> parent;  
        // split comparator and comparable paths  
        Comparator<? super K> cpr = comparator;  
        // 找出(key, value)在二叉排序树中的插入位置。  
        // 红黑树是以key来进行排序的，所以这里以key来进行查找。  
        if (cpr != null) {  
            do {  
                parent = t;  
                cmp = cpr.compare(key, t.key);  
                if (cmp < 0)  
                    t = t.left;  
                else if (cmp > 0)  
                    t = t.right;  
                else 
                    return t.setValue(value);  
            } while (t != null);  
        }  
        else {  
            if (key == null)  
                throw new NullPointerException();  
            Comparable<? super K> k = (Comparable<? super K>) key;  
            do {  
                parent = t;  
                cmp = k.compareTo(t.key);  
                if (cmp < 0)  
                    t = t.left;  
                else if (cmp > 0)  
                    t = t.right;  
                else 
                    return t.setValue(value);  
            } while (t != null);  
        }  
        // 为（key-value）新建节点  
        Entry<K,V> e = new Entry<K,V>(key, value, parent);  
        if (cmp < 0)  
            parent.left = e;  
        else 
            parent.right = e;  
        // 插入新的节点后，调用fixAfterInsertion调整红黑树。  
        fixAfterInsertion(e);  
        size++;  
        modCount++;  
        return null;  
    }

  • 删除 deleteEntry

    删除操作及对应 TreeMap 的 deleteEntry 方法，deleteEntry 方法同样也只需按照二叉排序树的操作步骤实现即可，删除指定节点后，再对树进行调整即可。deleteEntry 方法的实现源码如下：

    // 删除“红黑树的节点p”  
    private void deleteEntry(Entry<K,V> p) {  
        modCount++;  
        size--;  
        		
        if (p.left != null && p.right != null) {  
            Entry<K,V> s = successor (p);  
            p.key = s.key;  
            p.value = s.value;  
            p = s;  
        } 
          
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);  
         
        if (replacement != null) {  
            replacement.parent = p.parent;  
            if (p.parent == null)  
                root = replacement;  
            else if (p == p.parent.left)  
                p.parent.left  = replacement;  
            else 
                p.parent.right = replacement;  
         
            p.left = p.right = p.parent = null;  
         
            if (p.color == BLACK)  
                fixAfterDeletion(replacement);  
        } else if (p.parent == null) { 
            root = null;  
        } else {
            if (p.color == BLACK)  
                fixAfterDeletion(p);  
         
            if (p.parent != null) {  
                if (p == p.parent.left)  
                    p.parent.left = null;  
                else if (p == p.parent.right)  
                    p.parent.right = null;  
                p.parent = null;  
            }  
        }  
    }

TreeMap 和 HashMap 的比较

• TreeMap 是根据 key 进行排序的，它的排序和定位需要依赖比较器或覆写 Comparable 接口，也因此不需要 key 覆写 hashCode 方法和 equals 方法，就可以排除掉重复的 key，而 HashMap 的 key 则需要通过覆写 hashCode 方法和 equals 方法来确保没有重复的 key。

• TreeMap 的查询、插入、删除效率均没有 HashMap 高，一般只有要对 key 排序时才使用 TreeMap。

• TreeMap 的 key 不能为 null，而 HashMap 的 key 可以为 null。

• 注：对 TreeSet 和 HashSet 的源码不再进行剖析，二者分别是基于 TreeMap 和 HashMap 实现的，只是对应的节点中只有 key，而没有 value，因此对 TreeMap 和 HashMap 比较了解的话，对 TreeSet 和 HashSet 的理解就会非常容易。