Java集合学习

Collection是List、Set、Queue的最基本接口
Iterator：迭代器可以通过迭代器遍历集合中的数据
Map：是映射表的基础接口

List一共实现三个类，分别是ArrayList、LinkedList、Vector

1.ArrayList
（1）排列有序、可重复
（2）底层使用数组
（3）速度快、增删慢，getter()和setter()方法快
（4）线程不安全
（5）扩容：当容量不够时，ArrayList是当前容量的1.5倍 +1
最常用的List实现类，内部通过数组实现，允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔。扩容机制：当数组大小不满足时需要增加存储能力，就要将已经有数据的数组复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动，代价比较高，所以它适合随机查找和遍历，不适合插入和删除。
2.Vector
（1）排列有序可重复
（2）底层使用数组
（3）速度快，增删慢
（4）线程安全，效率低
（5）扩容：当容量不够时默认扩容一倍容量
和ArrayList一样都是通过数组实现的，不同的是Vector支持线程同步，即某一刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但同步需要很高的花费，因此，访问Vector比访问ArrayList慢。
ps：线程同步：即当有一个线程在对内存进行操作时，其他线程都不可以对这个内存地址进行操作，直到该线程完成操作， 其他线程才能对该内存地址进行操作，而其他线程又处于等待状态，实现线程同步的方法有很多，临界区对象就是其中一种。java中通过synchronized进行同步的保证。
3.LinkedList
（1）排列有序，可重复
（2）底层使用双向循环链表数据结构
（3）查询速度慢，增删快，add()和remove()方法快
（4）线程不安全
LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法，专门用于操作表头和表尾，可以当做堆栈，队列和双向队列使用。

Set注重独一无二，用于存储无序不重复数据，对象相等的本质是对象的hashCode值（java依据对象的内存地址计算出此序号）判断的如果想让两个不同的对象视为相等的，就必须覆盖Object的hashCode方法和equals方法。
其下实现的类有：CopyOnWriteArraySet、HashSet、LinkedHashSet、TreeSet、ConcurrentSkipListSet
1.HaseSet
（1）排列无序，不可重复
（2）底层使用Hash表实现
（3）存取速度快
（4）内部是HashMap
哈希表中存放的是哈希值。HashSet存储元素的顺序并不是按照存入时的顺序，而是按照哈希值来存的，所以取数据也是按照哈希值取的。元素的哈希值是通过元素的hashcode方法来获取的
取值时的判断方法：HashSet首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals方法，如果为true就视为同一个元素。如果equals为false就不是同一个元素。
哈希值相同但equals为false的元素就是在同样的哈希值下顺延（可以认为相同元素放在一个哈希桶中）。一个hashCode位置上可以存放多个元素。
2.TreeSet
（1）排列有序，不可重复
（2）底层使用二叉树实现
（3）排序存储
（4）内部是TreeMap的SortedSet
使用二叉树的原理对新add()的对象按照指定的顺序排序（升序、降序）。
integer和String对象都可以进行默认的TreeSet排序，自定义类的对象必须实现Comparable接口，并且覆写相应的compareTo()函数才可以正常排序。
compare函数在返回负整数、零、正整数时分别代表该对象小于、等于、大于指定对象。
3.LinkedHashSet
（1）采用hash表存储，并用双向链表记录插入顺序
（2）内部是LinkedHashMap
继承于HashSet，底层使用LinkedHashMap来保存所有元素，相关操作与HashSet相同。
Map：实现了HashMap、ConcurrentMap、TreeMap、HashTable、LinkedHashMap等类
1.HashMap
（1）键不可重复，值可重复
（2）底层为哈希表
（3）线程不安全
（4）允许key为null，value也可以为null
根据键值的HashCode值存储数据，具有很快的访问速度
java7时 HashMap里面是一个数组，然后数组中每个元素是一个单向链表，每个实体是嵌套类Entry的实例，Entry包含key、value、hash值和用于单链表的next。
capacity：当前数组容量，始终保持2ⁿ，可以扩容，扩容后为当前的2倍
loadFactor：负载因子，默认为0.75
threshold：扩容的阈值，等于capacity * loadFactor
java8时 最大的不同就是利用了红黑树，当链表中的元素过了8个以后会将链表转换为红黑树，在进行查找时可以降低时间复杂度为O(logN)
2.HashTable
（1）键不可重复，值可重复
（2）底层哈希表
（3）线程安全
（4）key、value都不允许为null
3.TreeMap
（1）键不可重复，值可重复
（2）底层二叉树
实现了SortedMap接口，能够把保存的记录根据键排序，当用Iterator遍历时，得到的记录是排过序的。在使用时key必须实现Comparable接口或者在构造是传入自定义的Comparator。
4.ConcurrentHashMap
==Segment段 ==
整个 _ConcurrentHashMap_由一个个Segment组成，Segment代表“部分”或“一段”
线程安全（Segment继承ReentrantLock加锁）
Segment通过继承ReentrantLock来进行加锁，所以每次加锁的操作是锁住一个segment。
并行度（默认16）
concurrencyLevel：并行级别、并发数、Segment数。默认是16，初始化时可更改，但扩容要具体到每个segment。
5.LinkedHashMap
相当于LinkedList+HashMap，用HashMap操作数据结构，使用LinkedList维护插入的先后顺序。Iterator遍历时，得到的记录是先插入的。