Java集合包

集合包是java中最经常使用的包，最经常使用的有Collection和Map接口的实现类，前者用于存放多个单对象，后者用于存放key-value形式的键值对。html

java集合包经常使用实现类结构图以下所示（I表示接口）java

 

 

 

 

 

 

 

1. List

线性表，有序集合，元素能够重复。程序员

1.1 ArrayList

动态数组，底层即数组，能够用来容纳任何对象，要求连续存放。ArrayList的重要成员是Object[] elementDate int Size表示有效元素的个数，数组的初始大小是10，扩容操做示意图以下，以前（上面）这块内存变成垃圾。 所以在初始化时尽可能指定初始容量，避免扩容产生的内存垃圾，影响性能。面试

public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}// 指定初始化大小

特色及使用注意

（1）foreach中可否对其基本类型元素值（包括数字、字符串、布尔）进行赋值改变？算法

 不能，高级For在JDK 5.0开始引入，用其迭代代码简洁，在foreach中修改的只是元素的副本，并不会改变原值（反编译以后可发现这一点），因此高级For循环能够用来遍历查询，不可修改当前取回的元素自己。swift

参考连接：foreach的一个“奇怪”现象—实现原理分析数组

可是对象类型的元素有所不一样，若是对对象数组进行遍历，则能够修改元素的状态，在每一轮循环中均可以拿到对象引用对其状态（成员变量、类变量）进行修改。缓存

（2）如何正确遍历并删除ArrayList元素值？安全

问题背景：给定字符串集合["a","b","b","c"]，删除其中元素"b"。数据结构

常见错误写法1：

public static void remove(List<String> list) 
	{
		for (int i = 0; i < list.size(); i++) 
		{
			String s = list.get(i);
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}
// 错误的缘由：这种最普通的循环写法执行后会发现第二个“b”的字符串没有删掉。

常见错误写法2：

public static void remove(List<String> list) 
	{
		for (String s : list)
		{
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}
// 使用加强的for循环 在循环过程当中从List中删除元素之后，继续循环List时会报ConcurrentModificationException，但删除以后立刻就跳出的也不会出现异常

思考及对策

为什么和出现错误1，怎么解决？

public boolean remove(Object o) {
		if (o == null) {
			for (int index = 0; index < size; index++)
				if (elementData[index] == null) {
					fastRemove(index);
					return true;
				}
		} else {
			for (int index = 0; index < size; index++)
				if (o.equals(elementData[index])) {
					fastRemove(index);
					return true;
				}
		}
		return false;
	}

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; // Let gc do its work
    }

能够看到会执行System.arraycopy方法，致使删除元素时涉及到数组元素的移动。针对错误写法1，在遍历第一个字符串b时由于符合删除条件，因此将该元素从数组中删除，而且将后一个元素移动（也就是第二个字符串b）至当前位置，致使下一次循环遍历时后一个字符串b并无遍历到，因此没法删除。针对这种状况能够倒序删除的方式来避免：

public static void remove(ArrayList<String> list) 
	{
		for (int i = list.size() - 1; i >= 0; i--) 
		{
			String s = list.get(i);
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}

为什么会出现错误2怎么解决？

final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}

这里会作迭代器内部修改次数检查，由于上面的remove(Object)方法修改了modCount的值，因此才会报出并发修改异常。要避免这种状况的出现则在使用迭代器迭代时（显示或for-each的隐式）不要使用ArrayList的remove，改成用Iterator的remove便可：

public static void remove(List<String> list) 
		{
		Iterator<String> it = list.iterator();
		while (it.hasNext()) 
		{
			String s = it.next();
			if (s.equals("b")) 
			{
				it.remove();
			}
		}
}

部分参考：ArrayList循环遍历并删除元素的常见陷阱; 如何正确遍历删除List中的元素，你会吗？

（3）ArrayList非线程安全，如何解决？

Collections给出了解决方案，提供了synchronizedCollection方法，该方法返回一个线程安全容器。

*Java中经常使用的集合框架中的实现类HashSet、TreeSet、ArrayList、ArrayDeque、LinkedList、HashMap、TreeMap都是线程不安全的，若是有多个线程同时访问它们，且同时有多个线程修改他们的时候，将会出现如读脏数据等错误。Collections给出了解决方案，提供了synchronizedCollection方法来实现线程安全，该方法返回一个线程安全容器。

（4）contains方法contains()方法是经过将传入的实际参数和集合中已有的元素进行equals()比较来实现的，Object类中的equals()方法比较的是两个对象的地址，所以须要根据实际须要重写equals()方法。

1.2 LinkedList、Vector、Stack

ArrayList和LinkedList是List(线性表)的两种典型实现：基于数组和基于双向链表的线性表。通常而言，因为数组以一块连续内存区来保存全部的数组元素，因此数组在随机访问时性能最好，全部的内部以数组做为底层实现的集合在随机访问时性能都比较好；而内部以链表做为底层实现的集合在执行插入、删除操做时有较好的性能。但整体来讲，ArrayList的性能要更好，所以大部分使用时都应该考虑使用ArrayList。

• 若是须要遍历List集合元素，对于ArrayList和Vector（也是以数组形式存储集合元素的一种集合类型）集合，应该使用随机访问方法（get）来遍历集合元素；对于LinkedList集合，则应该采用迭代器（Iterator）来遍历集合元素。
• 若是须要常常执行插入、删除操做来改变包含大量数据的List集合的大小，能够考虑使用LinkedList集合。使用ArrayList和Vector集合可能须要常常从新分配内部数组的大小，效果较差。
• 若是有多个线程须要同时访问List集合的元素，开发者能够考虑使用Collections将集合包装成线程安全的集合。

Vector是基于synchronized机制实现的线程安全的ArrayList，但在插入元素容量扩充时机制略有不一样，经过传入的capacityIncrement来控制容量的扩充。

Stack继承自Vector，在此基础上实现了栈的弹出以及压入和弹出操做，push、pop、peek（只返回，不出栈）

2. Map

键值对、键惟1、值不惟一

2.1 HashMap

底层实现

JDK7实现，数组+链表；JDK8实现，数组+红黑树。

可参考：JDK7与JDK8中HashMap的实现

存储过程

当程序试图将一个 key-value 对放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：若是两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。若是这两个 Entry 的 key 经过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。若是这两个 Entry 的 key 经过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 造成 Entry 链，并且新添加的 Entry 位于 Entry 链的头部。流程图以下所示：

读取实现

若是 HashMap 的每一个 bucket 里只有一个 Entry 时，HashMap 能够根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的状况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每一个 Entry，直到找到想搜索的 Entry 为止——若是刚好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最先放入该 bucket 中），那系统必须循环到最后才能找到该元素，时间复杂度取决于链表的长度，为 O(n)。为了下降这部分的开销，在 Java8 中当链表中的元素超过了 8 个且数组容量大于64之后会将链表转换为红黑树（Hollis-HashMap中傻傻分不清楚的那些概念、郭霖：面试必问的HashMap，你真的了解吗？），在这些位置进行查找的时候能够下降时间复杂度为 O(logN)。

HashMap 在底层将 key-value 当成一个总体进行处理，这个总体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存全部的 key-value 对，当须要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当须要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。

性能选项

实际容量（capacity）:大于initial capacity最小的2的n次方，如10<16

初始容量（initial capacity）：能够经过HashMap的构造函数指定

size:变量保存了该 HashMap 中所包含的 key-value 对的数量

threshold：该变量包含了 HashMap 能容纳的 key-value 对的极限，它的值等于 HashMap 的容量乘以负载因子（load factor）

负载因子（load factor）：决定了Hash表的最大填满程度

当建立 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子能够减小 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增长查询数据的时间开销，而查询是最频繁的的操做（HashMap 的 get() 与 put() 方法都要用到查询）；减少负载因子会提升数据查询的性能，但会增长 Hash 表所占用的内存空间。掌握了上面知识以后，咱们能够在建立 HashMap 时根据实际须要适当地调整 load factor 的值；若是程序比较关心空间开销、内存比较紧张，能够适当地增长负载因子；若是程序比较关心时间开销，内存比较宽裕则能够适当的减小负载因子。一般状况下，程序员无需改变负载因子的值。

2.2 TreeMap

采用红黑树的数据结构来管理key-value对（红黑树的每一个节点就是一个key-value对）

存储key-value对须要根据key排序，排序方式与TreeSet相同（两种排序方式）。

判断两个key相等的标准是：经过compareTo()返回0即认为这两个key相等。

对于自定义类做为key的状况，最好作到：两个key经过equals()方法比较返回true时，compareTo()方法也返回0。

两种排序的比较器：

java.lang.Comparable，TreeMap使用无参构造函数，那么容纳的对象必须实现Comparable接口。

public int compareTo(T o);

java.util.Comparator，TreeSet在构造时使用Comparator做为构造函数的参数。（两种排序方式同时存在时，该方式优先权更高）

int compare(T o1, T o2);

2.3 LinkedHashMap

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，HashMap+LinkedList，即它既使用HashMap操做数据结构，又使用LinkedList维护插入元素的前后顺序，经过维护一个运行于全部条目的双向链表，LinkedHashMap保证了元素迭代的顺序。该迭代顺序能够是插入顺序或者是访问顺序。

能够经过LinkedHashMap实现LRU算法缓存。构造参数accessOrder为true则全部的Entry按照访问的顺序排列，为false则全部的Entry按照插入的顺序排列，若是设置为true，每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向链表最头的那个数据就是要淘汰的数据。

public class LRUCache extends LinkedHashMap
{
    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        return size() > maxElements;
    }

    private static final long serialVersionUID = 1L;
    protected int maxElements;
}

2.4 Hashtable

Hashtable 是遗留类，不少映射的经常使用功能与 HashMap 相似，不一样的是它承自 Dictionary 类，而且是线程安全的，任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，由于 ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不须要线程安全的场合能够用 HashMap 替换，须要线程安全的场合能够用 ConcurrentHashMap 替换。

3. Set

无序、元素不可重复

3.1 HashSet

HashSet的底层实现用到HashMap，HashSet操做的就是HashMap。（Java源码就是先实现HashMap、TreeMap，而后包装一个value为null的Map集合来实现Set集合的）

存储过程

两个对象的equals()方法返回true，可是hashCode值不相等，这时HashSet会把这两个对象存储在Hash表的不一样位置，两个对象都可以添加成功，但这会与Set集合的规则相冲突。(这就是不重写相应hashCode()方法的后果，也可阅读参考：为何重写equals方法，必定要重写HashCode方法？)

因此阿里Java规范这样写道：

HashSet如何判断对象是不是相同

两个对象经过equals()方法比较相等，而且两个对象的hashCode方法的返回值也相等。

所以须要注意：

当把一个对象放入HashSet中时，若是须要重写此对象对应类的equals()方法，则同时须要重写其hashCode()方法。具体规则是：若是两个对象经过equals()方法比较返回true时，则它们的hashCode值也应该相等（Object规范：相等的对象必须具备相等的hashcode）。

3.2 TreeSet

底层是TreeMap，集合中的元素处于排序状态。采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方式：天然排序（默认状况）和定制排序。

当把一个对象添加到TreeSet中时，TreeSet会调用该对象的compareTo(Object obj)方法与容器中的其它对象比较大小，而后根据红黑树结构找到它的存储位置。若是compareTo(Object obj)返回0，意味着两个对象相同将没法添加到TreeSet集合中。

3.3 LinkedHashSet

LikedHashSet是HashSet的子类，它也是根据元素的HashCode值进来决定元素的存储位置，但它可以同时使用链表来维护元素的添加次序，使得元素能以插入顺序保存。

附：阿里Java规范-集合

List／Set／Map判断对象相同方式的区别

import java.util.*;

class A {
    @Override
    public int hashCode() {
        return UUID.randomUUID().hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

public class Main {

    public static void main(String[] args) throws Exception {
        List<A> list = new ArrayList<>();
        A a1 = new A();
        A a2 = new A();
        list.add(a1);
        // list contains()方法是经过将传入的实际参数和集合中已有的元素进行equals()比较来实现的
        System.out.println(list.contains(a2));
        Map<A, Object> map = new HashMap<>();
        map.put(a1, null);
        System.out.println(map.containsKey(a2));
        Set<A> set = new HashSet<>();
        set.add(a1);
        System.out.println(set.contains(a2));
    }
}
// output:
true
false
false

那么HashSet是如何判断对象是不是相同的呢？

两个对象经过equals()方法比较相等，而且两个对象的hashCode方法的返回值也相等。

所以须要注意：

当把一个对象放入HashSet中时，若是须要重写此对象对应类的equals()方法，则同时须要重写其hashCode()方法。具体规则是：若是两个对象经过equals()方法比较返回true时，则它们的hashCode值也应该相等（Object规范：相等的对象必须具备相等的hashcode）。

Map与Set相似，List稍有不一样，其contains()方法是经过将传入的实际参数和集合中已有的元素进行equals()比较来实现的，Object类中的equals()方法比较的是两个对象的地址，所以须要根据实际须要重写equals()方法。