Java学习总结：集合框架

泛型

泛型是JavaSE5.0引入的新特性，本质是参数化类型(与方法的形式参数比较，方法是参数化对象)。在类，接口和方法的定义过程中，所操作的数据类型通过传入的参数进行指定。

创建集合对象时可以直接指定放入集合中的元素类型，Java编译器可以根据此类型进行类型检查，可以减少代码在运行时出现的错误可能性

集合

集合(Collection)是用来管理一组对象的单一对象。集合内的对象被称之为元素(elements)。

集合可以处理很多种类型的对象，这些对象都有一个共同的父类Object。

数组与集合：

相同点：都是存储数据的容器，存储Object类型时，其实存储的都是对象的引用(地址)

不同点：数组可以存储基本数据类型，集合不可以;

数组的长度固定，对象数量未知时不适合使用，集合的长度可变，适用性比较广。

集合与数组之间的转换：

• 集合 —> 数组

1.返回object类型数组

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

2.指定泛型类型(常用)

 public <T> T[] toArray(T[] a) {
        if (a.length < size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
 }

可见当泛型数组长度小于集合元素个数时，得到的数组对象是新对象；

当我们指定的泛型数组长度不小于集合元素个数时，得到的数组对象是执行的泛型数组对象。

• 数组 —> 集合

java.util.Arrays包下的静态方法，返回的是原集合的视图，即不能对其进行增删元素，并且对集合的元素进行修改会影响数组对应的元素。

public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
}

两大父接口：Collection，Map

Collection

• List 接口(线性表)

List 是一个元素有序、且可重复的集合；

List集合中的每个元素都有其对应的顺序索引，从0开始。可以通过索引来访问指定位置的集合元素；

List 默认按元素的添加顺序设置元素的索引。

• ArrayList / LinkedList 实现类

ArrayList是实现了基于动态数组的数据结构,对象存储在连续的位置上

LinkedList基于双链表的数据结构，链表中的每个节点都包含了前一个和后一个元素的引用。

1、对于随机访问get和set，ArrayList绝对优于LinkedList，因为LinkedList要移动指针。

2、对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。

Vector 一个实现类(过时的)，和List用法差不多。Vector是线程安全的，ArrayList是线程不安全的。

取子列表时：

对子列表进行添加删除元素时会影响原列表

subList的底层源码中

构造器：

SubList(AbstractList<E> parent,
       int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
}

创建ArrayList.SubList 内部类实例时， parent 字段会持有外部类 ArrayList 对象的一个引用，只是添加了一定的偏移量而已。所以, 这个子 List 中的每一个元素所代表的引用, 其实就和原 List 中在相同索引处偏移 fromIndex 位置后的那个位置上的元素所代表的引用, 二者指向的是相同的对象。

包括在add方法中，modCount与原列表的相等：

public void add(int index, E e) {
       rangeCheckForAdd(index);
       checkForComodification();
       parent.add(parentOffset + index, e);
       this.modCount = parent.modCount;
       this.size++;
}

Queue(队列) 子接口

• Iterator(迭代器)接口

Collection接口中提供了获取迭代器对象的方法。

    List<String> list=new ArrayList<String>();
    Iterator<String> it=list.iterator();

集合在重写此方法时，利用了内部类Itr提供了迭代器的实现。

 private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

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

modCount是当前集合的版本号；

expectedModCount是当前迭代器的版本号，在迭代器实例化时初始化为modCount。

删除元素时：

Itr中的remove()方法同步了modCount和expectedModCount

ArrayList.add()或者ArrayList.remove()时，只更新了modCount的状态，每次修改(增、删)集合都会加1；

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
}

ArrayList类中的remove()方法只进行modCount++，导致modCount != expectedModCount，会报异常。

所以使用迭代器遍历集合时，不能通过集合的remove方法删除集合元素，应该使用迭代器自身提供的remove方法。

快速失败机制（fail-fast）：当多个线程对Collection进行操作时，若其中某一个线程通过Iterator遍历集合时，该集合的内容被其他线程所改变，则会抛出ConcurrentModificationException异常。java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）

Queue(队列) 子接口

队列遵循先进先出（FIFO first Input First Output）的原则；

特殊的线性表，队列限制对线性表的访问方式：队尾添加(offer)元素，队头取出（poll）元素。

实现类LinkedList也实现了该接口，因为Queue经常要进行添加和删除操作，而LinkedList在这方面效率比较高。

	Queue<String> qu=new LinkedList<String>(); 
	qu.offer("1");   //将一个对象添加到队尾，如果添加成功返回true
	qu.peek();       //查看队首的元素
	qu.poll();       //从队首删除并返回这个元素

while(names.peek()!=null){
	names.poll();
}

当对列为空时 peek()的返回值为null，所以当进行移除对首操作时，最好先用peek()方法查看对首是否为null

Deque(双端队列) 子接口

Deque是Queue的子接口，定义了所谓的”双端队列”，LinkedList实现了该接口;

可以从队列的两端分别可以入队（offer）和出队（poll）。

API：

offerLast(E e):表示从队尾进，相当于offer(E e)

pollFirst():表示从队首出，相当于poll()

offerFirst(E e):表示从队首进

pollLast():表示从队尾出。

peekFirst():查看队首，相当于peek()

peekLast():查看队尾。

Stack 栈

使用双端队列，来禁止队尾的操作，只对队首进行操作：

Deque<String>  stack = new LinkedList<String>();    //其实就是个双端队列

push(E e): 表示从栈的顶部进入栈内

E pop():表示从栈的顶部移除元素

List排序

1.实现Comparable接口自然排序

该接口提供了方法int compareTo(T t)，子类须重写此抽象方法定义排序规则。

在compareTo方法中：

升序： return 当前对象-形参对象

降序 ：return 形参对象-当前对象

比较规则（ 升序）

1.当前对象如果大于形参对象 返回>0的整数

2.当前对象如果小于形参对象。返回<0的整数

3.当前对象如果与形参对象相等 返回0

定义按照点距离y轴距离大小升序排序的规则：

public class Point implements Comparable<Point>{
	private int x;
	private int y;
	public int compareTo(Point o) {
		return this.x-o.x;
	}	
}

然后调用集合工具类Collections中的 static void sort(List<T> list)

2.Comparator比较器接口

自然排序在元素类型定义期间就已经确认比较规则。如果想重新定义比较规则时，可以使用比较器对象来重写设置比较规则。

Comparator接口提供了int compare(T t1,T t2)

在compare方法中(以下t1表示t1中的成员变量参加运算得到的结果)：

升序： return t1-t2；

降序： return t2-t1;

然后调用Collections.sort(List<T> list , Collection c)

也可以使用匿名内部类定义，按照点与原点的距离降序排序：

        Collections.sort(ps, new Comparator<Point>() {
		public int compare(Point o1, Point o2)  {
		    int dis1=o1.getX()*o1.getX()+o1.getY()*o1.getY();
		    int dis2=o2.getX()*o2.getX()+o2.getY()*o2.getY();
		    return dis2-dis1;
		}
	});

sort的最底层源码：

    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low, int high, int off,
                                  Comparator c) {
        int length = high - low;
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
    }

如果在重写compare(T t1,T t2)方法中return的是t1.成员变量-t2.成员变量,也就是升序排序时，底层使用的是mergeSort方法：

在两个嵌套的for循环中：第一次j=i=low，不满足j>low，&&短路运算符，跳出内层循环；

第二次j=i=low+1，满足j>low。如果dest[j-1]>dest[j]，则按照重写的compare规则返回的是>0的数则满足 c.compare(dest[j-1], dest[j])>0，也就是需要swap一下，达到升序目的。compare重写的作用体现于此。

Set 子接口

Set集合中的元素是无序的(取出的顺序与存入的顺序无关)

Set集合中的元素不能重复(即不能把同样的东西两次放入同一个Set容器中)

HashSet

HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取和查找性能。

1） 不能保证元素的排列顺序；

2)HashSet 不是线程安全的；

3)集合元素可以是null。

当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值决定该对象在 HashSet 中的存储位置。如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相等，hashSet 将会把它们存储在不同的位置。

LinkedHashSet

LinkedHashSet 是 HashSet 的子类。LinkedHashSet 集合根据元素的 hashCode 值来决定元素的存储位置，但它同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。LinkedHashSet 性能插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。LinkedHashSet 不允许集合元素重复。

TreeSet

TreeSet 是 SortedSet 接口的实现类，TreeSet集合是用来对元素进行排序的,同样他也可以保证元素的唯一。TreeSet 可以确保集合元素处于排序状态。TreeSet 支持两种排序方法：自然排序和定制排序。默认情况下，TreeSet 采用自然排序。

Map

Map是集合框架中的另一个父接口，用于保存具有映射关系的数据：key-value键值对（key可以看成是value的索引）。

1.key和value也必须是引用类型的数据；

2.作为key的对象在Map集合中不允许重复；

3.key可以为null。key和value之间存在单向一对一关系，通过指定的key总能找到唯一确定的value。

HashMap

HashMap的底层基于数组和链表来。它是通过计算散列码来决定存储的位置，所以有相当快的查询速度。

当向HashMap中添加元素时，先通过key的hash值经过一系列的运算算出所在数组中的位置，如果此位置上已经有元素了，那么再通过equals方法与此位置上的单向链表内的元素一一比较，如果有相同的key,就会替换原有的key-value,如果没有，添加在此单向链表中；如果此位置上没有元素，就直接存储在此位置上对应单向链表的头节点上。

hash冲突：因为HashMap主要是通过key的hashCode来计算hash值的，只要hashCode相同计算出来的hash值就一样，所以如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的。

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);      //计算key的hash值
        int i = indexFor(hash, table.length);     //计算key在数组中的位置
        for (Entry<K,V> 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;
        }
 } 

重写equals()与hashCode():

object类中默认的实现方式是：return this == obj，就是说，只有this 和 obj引用同一个对象，才会返回true。而我们往往需要用equals来判断 2个对象是否等价，而非验证他们的唯一性。这样我们在实现自己的类时，就要重写equals()。

若两个对象equals(Object obj)返回true，则hashCode()有必要也返回相同的int数。

若两个对象equals(Object obj)返回false，则hashCode()不一定返回不同的int数。

若两个对象hashCode()返回相同int数，则equals(Object obj)不一定返回true。

若两个对象hashCode()返回不同int数，则equals(Object obj)一定返回false。

同一对象在执行期间若已经存储在集合中，则不能修改影响hashCode值的相关信息，否则会导致内存泄露问题。

重写hashCode方法时让重要的字段都参入散列运算，每一个重要字段都会产生一个hash值，为最终的hash值做出贡献（影响）

装载因子及其HashMap优化：

1.capacity:容量，hash表里bucket(桶)的数量，也就是散列数组大小

2.initial capacity:初始容量，创建hash表时，初始bucket的数量，默认构建容量为16，也可以使用特定容量。

3.size：大小，当前散列表中存储数据的数量

4.load factor:加载因子，默认值0.75也就是75%，当向散列表增加数据时，如果size/capacity的值大于loadfactor。则发生扩容并 且重新散列(rebash)

性能优化：加载因子较小时，散列查找性能会提高，但是也浪费了散列桶空间容量。0.75是性能和空间相对平衡结果。在创建散列表时指定合理容量，减少rehash能提供性能ashMap优化。

HashTable

HashMap与HashTable对比：

1.Hashtable 是一个古老的 Map 实现类，不建议使用；

2.Hashtable 是一个线程安全的 Map 实现，但 HashMap 是线程不安全的；

3.Hashtable 不允许使用 null 作为 key 和 value，而 HashMap 可以；

4.HashSet 集合不能保证元素的顺序的顺序，Hashtable 、HashMap 也不能保证其中 key-value 对的顺序。

LinkedHashMap

LinkedHashMap 是 HashMap 的子类

LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key-Value 对的插入顺序一致

LinkedHashMap类中没有直接获取Iterator迭代器的方法，需要转化为set来遍历

Map<String, String> map = new LinkedHashMap<>();
Set<Entry<String,String>> set=map.entrySet();

LinkedHashMap的节点Entry<K,V>继承自HashMap.Node<K,V>，在其基础上扩展了一下。改成了一个双向链表。

TreeMap

1.TreeMap 存储 Key-Value对时，需要根据 Key 对 key-value 对进行排序。

2.TreeMap 可以保证所有的 Key-Value 对处于有序状态。

3.TreeMap 的 Key 的排序以及构造器：

自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException；构造器TreeMap()

定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口。构造器TreeMap(Comparator c)

 

Properties

Properties 类是 Hashtable 的子类，该对象用于处理属性文件；

由于属性文件里的 key、value都是字符串类型，所以 properties 里的 Key 和 Value 都是字符串类型的。

my.properties文件：

url=jdbc:mysql://localhost:3306/test
username=root
password=root
driver=com.mysql.jdbc.driver

public class PropertiesDemo01 {
	public static void main(String[] args) throws Exception {
		Properties prop=new Properties();
		InputStream is=PropertiesDemo01.class.getClassLoader().
                        getResourceAsStream("my.properties");  //使用流读取文件内的数据
		prop.load(is);   //将流内的信息封装到prop对象内
		//通过key获取相关的value值
		String url=prop.getProperty("url");
		String user=prop.getProperty("username");
		String pwd=prop.getProperty("password");
		String dri=prop.getProperty("driver");
		System.out.println(url+" "+user+" "+pwd+" "+dri);
	}
}