Java集合

Java集合框架：是一种工具类，就像是一个容器可以存储任意数量的具有共同属性的对象。

Java集合中成员很丰富，常用的集合有ArrayList，HashMap，HashSet等。线程安全的有Vector，HashTable。线程不安全的有LinkedList，TreeMap，ArrayList，HashMap等等。

集合中用到的数据结构有以下几种：

数组：最常用的数据结构之一。数组的特点是长度固定，可以用下标索引，并且所有的元素的类型都是一致的。使用时尽量把数组封装在一个类里，防止数据被错误的操作弄乱。

链表：是一种由多个节点组成的数据结构，并且每个节点包含有数据以及指向下一个节点的引用，在双向链表里，还会有一个指向前一个节点的引用。例如，可以用单向链表和双向链表来实现堆栈和队列，因为链表的两端都是可以进行插入和删除的动作的。当然，也会有在链表的中间频繁插入和删除节点的场景。

树：是一种由节点组成的数据结构，每个节点都包含数据元素，并且有一个或多个子节点，每个子节点指向一个父节点可以表示层级关系或者数据元素的顺序关系。如果树的每个子节点最多有两个叶子节点，那么这种树被称为二叉树。二叉树是一种非常常用的树形结构， 因为它的这种结构使得节点的插入和删除都非常高效。树的边表示从一个节点到另外一个节点的快捷路径。

堆栈：只允许对最后插入的元素进行操作（也就是后进先出，Last In First Out – LIFO）。如果你移除了栈顶的元素，那么你可以操作倒数第二个元素，依次类推。这种后进先出的方式是通过仅有的peek(),push()和pop()这几个方法的强制性限制达到的。这种结构在很多场景下都非常实用，例如解析像(4+2)*3这样的数学表达式，把源码中的方法和异常按照他们出现的顺序放到堆栈中，检查你的代码看看小括号和花括号是不是匹配的，等等。

队列：和堆栈有些相似，不同之处在于在队列里第一个插入的元素也是第一个被删除的元素（即是先进先出）。这种先进先出的结构是通过只提供peek()，offer()和poll()这几个方法来访问数据进行限制来达到的。例如，排队等待公交车，银行或者超市里的等待列队等等，都是可以用队列来表示。

Java集合框架图

[图片上传失败...(image-4b8b54-1530872801038)]

Collection interface

如上图所示，Collection接口是最基本的集合接口，它不提供直接的实现，Java SDK提供的类都是继承自Collection的“子接口”如List，Set和Queue。Collection所代表的是一种规则，它所包含的元素都必须遵循一条或者多条规则。如有些允许出现重复元素而有些则不允许重复、有些必须要按照顺序插入而有些则是散列，有些支持排序但是有些则不支持等等。

List

List接口是Collection接口下的子接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

ArrayList

ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作（扩容1.5倍）。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

ArrayList擅长于随机访问。同时ArrayList是非同步的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

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

LinkedList

LinkedList同样实现List接口，与ArrayList不同的是，LinkedList是基于双向链表实现的，可以在任何位置进行高效地插入和移除操作。但是LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = Collections.synchronizedList(new LinkedList(…));

Vector

与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

Stack

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set

Set接口继承了Collection接口。Set集合中不能包含重复的元素，每个元素必须是唯一的。你只需将元素加入set中，重复的元素会自动移除。有三种常见的Set实现——HashSet, TreeSet和LinkedHashSet。如果你需要一个访问快速的Set，你应该使用HashSet；当你需要一个排序的Set，你应该使用TreeSet；当你需要记录下插入时的顺序时，你应该使用LinedHashSet。

HashSet

HashSet是是基于 HashMap 实现的，底层采用 HashMap 来保存元素,所以它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。add()、remove()以及contains()等方法都是复杂度为O(1)的方法。由于HashMap中key不可重复，所以HashSet元素不可重复。可以存储null元素，是线程不安全的。

TreeSet

TreeSet是一个有序集，基于TreeMap实现，是线程不安全的。

TreeSet底层采用TreeMap存储，构造器启动时新建TreeMap。TreeSet存储元素实际为TreeMap存储的键值对为<key,PRESENT>的key;，PRESENT为固定对象：private static final Object PRESENT = new Object().

TreeSet支持两种两种排序方式，通过不同构造器调用实现

自然排序：

public TreeSet() {    // 新建TreeMap，自然排序    this(new TreeMap
    
     ());}
    

Comparator排序：

public TreeSet(Comparator
     comparator) {    // 新建TreeMap，传入自定义比较器comparator    this(new TreeMap<>(comparator));}

TreeSet支持正向/反向迭代器遍历和foreach遍历

// 顺序TreeSet：迭代器实现Iterator iter = set.iterator();while (iter.hasNext()) {    System.out.println(iter.next());    }// 顺序遍历TreeSet：foreach实现for (Integer i : set) {    System.out.println(i);}// 逆序遍历TreeSet：反向迭代器实现Iterator iter1 = set.descendingIterator();while (iter1.hasNext()) {    System.out.println(iter1.next());}

LinkedHashSet

LinkedHashSet介于HashSet和TreeSet之间。哈希表和链接列表实现。基本方法的复杂度为O(1)。

LinkedHashSet 是 Set 的一个具体实现，其维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。

LinkedHashSet 继承于 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现的一样。

如果我们需要迭代的顺序为插入顺序或者访问顺序，那么 LinkedHashSet 是需要你首先考虑的。

LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，因为继承于 HashSet，所有的方法操作上又与 HashSet 相同，因此 LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。

package java.util;public class LinkedHashSet
    
         extends HashSet
     
          implements Set
      
       , Cloneable, java.io.Serializable {    private static final long serialVersionUID = -2851667679971038690L;    /**     * 构造一个带有指定初始容量和加载因子的空链表哈希set。     *     * 底层会调用父类的构造方法，构造一个有指定初始容量和加载因子的LinkedHashMap实例。     * @param initialCapacity 初始容量。     * @param loadFactor 加载因子。     */    public LinkedHashSet(int initialCapacity, float loadFactor) {        super(initialCapacity, loadFactor, true);    }    /**      * 构造一个指定初始容量和默认加载因子0.75的新链表哈希set。      *      * 底层会调用父类的构造方法，构造一个指定初始容量和默认加载因子0.75的LinkedHashMap实例。      * @param initialCapacity 初始容量。      */      public LinkedHashSet(int initialCapacity) {        super(initialCapacity, .75f, true);    }    /**      * 构造一个默认初始容量16和加载因子0.75的新链表哈希set。      *      * 底层会调用父类的构造方法，构造一个默认初始容量16和加载因子0.75的LinkedHashMap实例。      */      public LinkedHashSet() {        super(16, .75f, true);    }    /**      * 构造一个与指定collection中的元素相同的新链表哈希set。      *       * 底层会调用父类的构造方法，构造一个足以包含指定collection      * 中所有元素的初始容量和加载因子为0.75的LinkedHashMap实例。      * @param c 其中的元素将存放在此set中的collection。      */      public LinkedHashSet(Collection
        c) {        super(Math.max(2*c.size(), 11), .75f, true);        addAll(c);    }        @Override    public Spliterator
       
         spliterator() {        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);    }}
       
      
     
    

通过观察我们可以发现:

Hash Map的前三个构造函数，即访问权限为public类型的构造函数均是以HashMap作为实现。而以LinkedHashMap作为实现的构造函数的访问权限是默认访问权限，即包内访问权限。

即：在java编程中，通过new创建的HashSet对象均是以HashMap作为实现基础。只有在jdk中java.util包内的源代码才可能创建以LinkedHashMap作为实现的HashSet(LinkedHashSet就是通过封装一个以LinkedHashMap为实现的HashSet来实现的)。

只有包含三个参数的构造函数才是采用的LinkedHashMap作为实现。

Map

Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。key可以为空，但是只允许出现一个null。它的主要实现类有HashMap、HashTable、LinkedHashMap、TreeMap。

HashMap

HashMap 是 Map 的一个实现类，它代表的是一种键值对的数据存储形式。

大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。

HashMap最多只允许一条记录的键为null，允许多条记录的值为null。遇到key为null的时候，调用putForNullKey方法进行处理，而对value没有处理。不保证有序(比如插入的顺序)、也不保证序不随时间变化。

jdk 8 之前，其内部是由数组+链表来实现的，而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。

HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

hash数组的默认大小是16，而且大小一定是2的指数

HashTable

Hashtable和HashMap一样也是散列表，存储元素也是键值对，底层实现是一个Entry数组+链表。Hashtable继承于Dictionary类（Dictionary类声明了操作键值对的接口方法），实现Map接口（定义键值对接口）。HashTable是线程安全的，它的大部分类都被synchronized关键字修饰。key和value都不可为null。

hash数组默认大小是11，扩充方式是old*2+1

LinkedHashMap

LinkedHashMap继承自HashMap实现了Map接口。基本实现同HashMap一样（底层基于数组+链表+红黑树实现），不同之处在于LinkedHashMap保证了迭代的有序性。其内部维护了一个双向链表，解决了 HashMap不能随时保持遍历顺序和插入顺序一致的问题。

除此之外，LinkedHashMap对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。

在实现上，LinkedHashMap很多方法直接继承自HashMap，仅为维护双向链表覆写了部分方法。

默认情况下，LinkedHashMap的迭代顺序是按照插入节点的顺序。也可以通过改变accessOrder参数的值，使得其遍历顺序按照访问顺序输出。

TreeMap

TreeMap继承自AbstractMap抽象类，并实现了SortedMap接口，如下图所示：

[图片上传失败...(image-fd7a40-1530872801038)]

TreeMap集合是基于红黑树（Red-Black tree）的 NavigableMap实现。该集合最重要的特点就是可排序，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

关于集合的常见问题

List和Map的区别

都是Java常用的容器，都是接口。不同的是List存储的是单列的集合，Map存储的是key-value键值对的集合。List中允许出现重复元素，Map中不允许key重复。List集合是有序的（储存有序），Map集合是无序的（存储无序）

Set中的元素不能重复，如何实现？

Set大多都用的Map接口的实现类来实现的（HashSet基于HashMap实现，TreeSet基于TreeMap实现，LinkedHashSet基于LinkedHashMap实现）

在HashMap中通过如下实现来保证key值唯一

// 1. 如果key 相等  if (p.hash == hash &&    ((k = p.key) == key || (key != null && key.equals(k))))    e = p;// 2. 修改对应的value   if (e != null) { // existing mapping for key        V oldValue = e.value;        if (!onlyIfAbsent || oldValue == null)            e.value = value;        afterNodeAccess(e);        return oldValue;   }

添加元素的时候，如果key(也对应的Set集合的元素)相等，那么则修改value值。而在Set集合中，value值仅仅是一个Object对象罢了(该对象对Set本身而言是无用的)。

也就是说：Set集合如果添加的元素相同时，是根本没有插入的(仅修改了一个无用的value值)。从源码(HashMap)中也看出来，==和equals()方法都有使用！

Vector和ArrayList

相同点：

这两个类都实现了List接口，他们都是有序的集合（储存有序），底层都用数组实现。可以通过索引来获取某个元素。允许元素重复和出现null值。ArrayList和Vector的迭代器实现都是fail-fast的。

不同点：

vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用arraylist效率比较高。

扩容时，arraylist扩容1.5倍，vector扩容2倍（或者扩容指定的大小）

ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动等内存操作，所以索引数据快插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

Aarraylist和Linkedlist

ArrayList是基于数组实现的，LinkedList基于双向链表实现的。

ArrayList它支持以下标位置进行索引出对应的元素(随机访问)，而LinkedList则需要遍历整个链表来获取对应的元素。因此一般来说ArrayList的访问速度是要比LinkedList要快的

ArrayList由于是数组，对于删除和修改而言消耗是比较大(复制和移动数组实现)，LinkedList是双向链表删除和修改只需要修改对应的指针即可，消耗是很小的。因此一般来说LinkedList的增删速度是要比ArrayList要快的

LinkedList比ArrayList消耗更多的内存，因为LinkedList中的每个节点存储了前后节点的引用。

对于增加/删除元素操作

如果增删都是在末尾来操作（每次调用的都是remove()和add()），此时ArrayList就不需要移动和复制数组来进行操作了。如果数据量有百万级的时，速度是会比LinkedList要快的。

如果删除操作的位置是在中间。由于LinkedList的消耗主要是在遍历上，ArrayList的消耗主要是在移动和复制上(底层调用的是arraycopy()方法，是native方法)。

LinkedList的遍历速度是要慢于ArrayList的复制移动速度的如果数据量有百万级的时，还是ArrayList要快。

哪些集合类提供对元素的随机访问？

ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。

Enumeration和Iterator接口的区别

Enumeration的速度是Iterator的两倍，也使用更少的内存。Enumeration是非常基础的，也满足了基础的需要。但是，与Enumeration相比，Iterator更加安全，因为当一个集合正在被遍历的时候，它会阻止其它线程去修改集合。

Iterator的方法名比Enumeration更科学

Iterator有fail-fast机制，比Enumeration更安全Iterator能够删除元素，Enumeration并不能删除元素

Iterater和ListIterator之间有什么区别？

我们可以使用Iterator来遍历Set和List集合，而ListIterator只能遍历List。

Iterator只可以向前遍历，而LIstIterator可以双向遍历。ListIterator从Iterator接口继承，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

Java中HashMap的key值要是为类对象则该类需要满足什么条件？

需要同时重写该类的hashCode()方法和它的equals()方法。

从源码可以得知，在插入元素的时候是先算出该对象的hashCode。如果hashcode相等话的。那么表明该对象是存储在同一个位置上的。

如果调用equals()方法，两个key相同，则替换元素如果调用equals()方法，两个key不相同，则说明该hashCode仅仅是碰巧相同，此时是散列冲突，将新增的元素放在桶子上

重写了equals()方法，就要重写hashCode()的方法。因为equals()认定了这两个对象相同，而同一个对象调用hashCode()方法时，是应该返回相同的值的！

HashSet与HashMap

HashSet 实现了 Set 接口，它不允许集合中有重复的值，当我们提到 HashSet 时，第一件事情就是在将对象存储在 HashSet 之前，要先确保对象重写 equals()和 hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。

public boolean add(Object o)方法用来在 Set 中添加元素，当元素值重复时则会立即返回 false，如果成功添加的话会返回 true。

HashMap 实现了 Map 接口，Map 接口对键值对进行映射。Map 中不允许重复的键。Map 接口有两个基本的实现，HashMap 和 TreeMap。TreeMap 保存了对象的排列次序，而 HashMap 则不能。HashMap 允许键和值为 null。HashMap 是非 synchronized 的，但 collection 框架提供方法能保证 HashMap synchronized，这样多个线程同时访问 HashMap 时，能保证只有一个线程更改 Map。

public Object put(Object Key,Object value)方法用来将元素添加到 map 中。

HashMap	HashSet
HashMap实现了Map接口	HashSet实现了Set接口
HashMap储存键值对	HashSet仅仅存储对象
使用put()方法将元素放入map中	使用add()方法将元素放入set中
HashMap中使用键对象来计算hashcode值	HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false

hashtable与hashmap

相同点：

储存结构和实现基本相同，都是是实现的Map接口

不同点：

HashTable是同步的，HashMap是非同步的，需要同步的时候可以ConcurrentHashMap方法

HashMap允许为null，HashTable不允许为null

继承不同，HashMap继承的是AbstractMap，HashTable继承的是Dictionary

HashMap提供对key的Set进行遍历，因此它是fail-fast的，但HashTable提供对key的Enumeration进行遍历，它不支持fail-fast。

HashTable是一个遗留类，如果需要保证线程安全推荐使用CocurrentHashMap

HashMap与TreeMap

HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。HashMap中元素的排列顺序是不固定的）。

在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项，因为该树总处于平衡状态。

集合框架中的泛型有什么优点？

Java1.5引入了泛型，所有的集合接口和实现都大量地使用它。泛型允许我们为集合提供一个可以容纳的对象类型，因此，如果你添加其它类型的任何元素，它会在编译时报错。这避免了在运行时出现ClassCastException，因为你将会在编译时得到报错信息。泛型也使得代码整洁，我们不需要使用显式转换和instanceOf操作符。它也给运行时带来好处，因为不会产生类型检查的字节码指令。

comparable 和 comparator的不同之处？

comparable接口实际上是出自java.lang包

它有一个 compareTo(Object obj)方法来将objects排序comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法来将objects排序

如何保证一个集合线程安全？

Vector, Hashtable, Properties 和 Stack 都是同步的类，所以它们都线程安全的，可以被使用在多线程环境中

使用Collections.synchronizedList(list)) 方法，可以保证list类是线程安全的使用java.util.Collections.synchronizedSet()方法可以保证set类是线程安全的。

TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。

TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。

Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

什么是Java优先级队列？

Java PriorityQueue是一个数据结构，它是Java集合框架的一部分。 它是一个队列的实现，其中元素的顺序将根据每个元素的优先级来决定。 实例化PriorityQueue时，可以在构造函数中提供比较器。 该比较器将决定PriorityQueue集合实例中元素的排序顺序。

Java hashCode（）和equals（）方法。

equals（）方法用于确定两个Java对象的相等性。 当我们有一个自定义类时，我们需要重写equals（）方法并提供一个实现，以便它可以用来找到它的两个实例之间的相等性。 通过Java规范，equals（）和hashCode（）之间有一个契约。 它说，“如果两个对象相等，即obj1.equals（obj2）为true，那么obj1.hashCode（）和obj2.hashCode（）必须返回相同的整数”

无论何时我们选择重写equals（），我们都必须重写hashCode（）方法。 hashCode（）用于计算位置存储区和key。