集合排序：JAVA集合类学习（笔记）

1. 类图：

2. 集合类说明：
1) COLLECTION
一、 LIST
1> ARRAYLIST(线程不安全):    内部实现就是Object数组，使用了JAVA泛型，构造函数默认数组长度为10。
(1)  如果通过构造函数，来获取到新的arrayList对象，则数组长度计算方法：
Java代码
// Allow 10% room for growth  
int capacity = (int) Math.min((size*110L)/100, Integer.MAX_VALUE); 

// Allow 10% room for growth
int capacity = (int) Math.min((size*110L)/100, Integer.MAX_VALUE);
capacity变量就是目前数组的可用长度，设计上预留了10%用作后续的增长，所以每次
(2)  如果是add()方法加入，则新的可用长度计算方法如下：
int newCapacity = (oldCapacity * 3)/2 + 1;
(3) 通过clone()方法，则不会修改长度；

2>LINKEDLIST(线程不安全):  内部实现通过内部类Entry实现了对象链：
Java代码
Class Entry{      
E element;  
        Entry<E> next;  
    Entry<E> previous;  
…  
}  

Class Entry{
E element;
    Entry<E> next;
Entry<E> previous;
…
}   
2） VECTOR(线程安全):  內部的实现与arrayList有点类似，都用了数组，但是两者的区别如下：
(1) vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用arraylist效率比较高。
(2) 如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据，用vector有一定的优势。
(3) 如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)n为总长度，这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。
        Vector 在对elementData进行处理的方法，都加了synchronized，实现线程同
步。
1>STACK(线程安全)： Stack继承自Vector，实现了栈的功能，同时是线程安全的。
二、 SET
1>HASHSET(线程不安全):
内部是用HashMap来实现的，所以它实现了键值的对应
Java代码
private transient HashMap<E,Object> map; 

private transient HashMap<E,Object> map;看看它的添加方法：
Java代码
public boolean add(E o) {  
      return map.put(o, PRESENT)==null;  
} 

public boolean add(E o) {
  return map.put(o, PRESENT)==null;
}其中PRESENT变量是
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
    它是一个final且静态的变量，它用来在添加的时候，作为value出现，而map是key唯一的，所以在添加HashSet时，加入的对象都是作为 HashMap的Key保存，同时必定唯一。
2>TREESET
内部是用SortedMap来实现的，所以它实现了键值的对应
Java代码
private transient SortedMap<E,Object> m; 

private transient SortedMap<E,Object> m;实现方式与HashSet类似，但是它有新的方法

3. MAP
2) HASHMAP
    实现了键值对应关系，同事map中不会存在null值，当add时 KEY值为null，则会为该value添加默认的key值，
Java代码
/** 
* Value representing null keys inside tables. 
*/ 
ic final Object NULL_KEY = new Object(); 

    /**
     * Value representing null keys inside tables.
     */
static final Object NULL_KEY = new Object();

但是我想如果同时插入两个key为空的VALUE值，那不是前一个值被冲掉了么。
实验了一下：
Java代码
Map map = new HashMap();  
map.put(null, 11111);  
System.out.println("before:" + map.get(null));  
map.put(null, 22222);  
System.out.println("after:" + map.get(null));  
果然打印结果为：  
before:11111 
after:22222 

Map map = new HashMap();
map.put(null, 11111);
System.out.println("before:" + map.get(null));
map.put(null, 22222);
System.out.println("after:" + map.get(null));
果然打印结果为：
before:11111
after:22222
保存值的实现方案是，用内部类
Java代码
transient Entry[] table;   
 
static class Entry<K,V> implements Map.Entry<K,V> {  
        final K key;  
        V value;  
        final int hash;  
Entry<K,V> next;  
 
   …  
} 

transient Entry[] table;

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        final int hash;
Entry<K,V> next;

   …
}
     通过计算计算当前值的hashcode来确定值在table[]中的位置，然后保存。
2> SORTEDMAP：
    定义了排序的接口
3> TREEMAP
基本实现与hashMap差不多，只是其内部类实现方式不同，它是通过排序决定插入值的位置，同时也是通过对象数组实现。