Java总结之容器家族--Collection

特点：  
1.增删改查操作都可以按照索引进行精确的控制，所以是元素的有序排列  
2.允许相同元素

public abstract class AbstractCollection<E> implements Collection<E>
public abstract class AbstractSequentialList<E> extends AbstractList<E> 
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

数组：定点添加，后面元素都要往后挪个位，O(n)-------双链表：耗时在找到那个定点，添加很快，综合O(n)
数组：定点删除，后面元素都要往前挪个位，O(n)-------双链表：耗时在找到那个定点，删除很快，综合O(n)
数组：定点查询，数组自带索引光环，O(1)      -------双链表：一个一个挨着找 O(n)
数组：定点修改，数组自带索引光环，O(1)      -------双链表：耗时在找到那个定点，修改很快，综合O(n)

随机访问、修改性能：Vector、ArrayList>LinkedList  
考虑到Vector、ArrayList添加或删除时：    
1.可能伴随扩容/缩容，  
2.当元素个数巨大时，可能造成大量空闲空间  
3.数组连续开辟空间，会造成储存空间的碎片化  
的这些问题，在大量添加或删除操作使用LinkedList是更好的选择

因为双链表：
1.双链表的添加/删除耗时在查找工作，而双链表查询时会查看索引在前半还是后半
来决定从头查询或从尾查询，从而最差情况只需size/2,而数组最差情况为size
2.链表不需要开辟连续空间，从而避免储存空间的碎片化  

另外在数据非常巨大的时候：
LinkedList基于双链表，需要new 巨大数量的节点(Node),
Vector、ArrayList只是开辟空间，所以更好一些，所以根据需求酌情处理

Vector类对集合的元素操作时都加了synchronized，保证线程安全。但使得效率下降：如

    public synchronized boolean add(E e) {
        modCount++;
        add(e, elementData, elementCount);
        return true;
    }

所谓同步：即当一个Iterator被正在被使用，另一个线程对Vector添加或删除元素，这时调用Iterator的方法时将抛出异常
public synchronized void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final Object[] es = elementData;
        final int size = elementCount;
        for (int i = 0; modCount == expectedModCount && i < size; i++)
            es[i] = operator.apply(elementAt(es, i));
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        modCount++;
    }

可以看到很多关于修改的方法当:modCount != expectedModCount时都会扔一个ConcurrentModificationException异常
也就是期望的修改次数与真实的修改次数不一致时

确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合
互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。
无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。

private transient HashMap<E,Object> map;

public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

    public TreeSet() {
        this(new TreeMap<>());
    }

        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("赵");
        hashSet.add("钱");
        hashSet.add("孙");
        hashSet.add("李");

        //按照哈希的顺序:hashCode()，equals(Object obj)
        System.out.println(hashSet);//[钱, 赵, 孙, 李]

        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("赵");
        linkedHashSet.add("钱");
        linkedHashSet.add("孙");
        linkedHashSet.add("李");
        //基于链表实现了插入的顺序
        System.out.println(linkedHashSet);//[赵, 钱, 孙, 李]

        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("赵");
        treeSet.add("钱");
        treeSet.add("孙");
        treeSet.add("李");
        //按照compareTo()的排序
        System.out.println(treeSet);//[孙, 李, 赵, 钱]