Java中的集合类

参考：参考文章
最近有时间，所以想系统的学习下java中的集合，所以参考了一些文章，这里暂时引用一下总体框架图:


这个图是总体的框架图，主要是两个接口Collection和Map都继承接口Iterator(Iterable),为了实现可以使用迭代器。Collection和Map类似平级关系。
1、这里我先学习下ArrayList和LinkedList：
ArrayList先从源码的注释看起，讲述ArrayList的特性；
》允许添加的元素为NULL
》size、get、set、isEmpty、iterator、listIterator操作都是常量时间，add是均摊时间，其他的操作都是线性时间，但是常数因子是小LlinkedList
》非同步，如果多个线程读取，至少一个线程进行结构上的修改（add、remove、显式修改数组大小），需要同步，可以使用Collections.synchronizedList(list)把其包装为同步对象。
》快速失败：如果使用迭代器列表后（Iterator iteratoList=arrayList.iterator();）这一步初始化创建new Itr时，就已经把赋值expectModCount=modCount，如果在遍历结束之前，对原始list进行任何结构上的修改，都将会抛出ConcurrentModificationException异常，这是因为使用next时，都会先检查（checkForComodification()检查modCount记录结构别修改的次数是否与迭代前的期望一样）是否已经发生结构上的修改。（除非使用iterator或者listiterator自带方法add和remove因为自带方法实现了expectedModCount = ArrayList.this.modCount;两者值相等）。但这个特性只能用于测试程序中的bug，而不能验证程序的正确性。这个值没有进行同步或可见性操作因此也是不一定可靠：修改后也可能没有即时发现，真正防止修改应该是对那些操作加锁。
下面进入源码：
ArrayList继承了抽象类AbstractList，实现了接口list、cloneable(通过源码发现，使用的应该是浅克隆，如果数据元素是对象，则并没有进行clone)等。
ArrayList底层实现是一个object数组，当创建一个对象时，如果没有指定大小，那么默认数组大小为0(指向空数组)，当添加一个元素后，使用默认值10来作为初始大小。
容量增长最终是通过grow()方法来增长，在1.7中是newCapacity = oldCapacity + (oldCapacity >> 1);（8+4；9+4 ）即小于等于1.5倍.
通过两个内部类Itr、ListItr来实现迭代。
LinkedList先从源码的注释看起，讲述LinkedList的特性；
》继承了抽象类AbstractSequenceList，实现了接口List、Deque、Cloneable（浅克隆）等。允许添加元素为NULL
》双向链表操作，插入特定下标位置元素，需要从头或者尾部开始遍历。
》非同步的，如果是多个线程访问和至少一个线程进行结构上修改，则需要同步。同步最好在创建的时候就进行同步，比如Collections.synchronizedList(new LinkedList())包装成同步对象。
》同样在使用iterator和listinterator方法的时候，如果已创建了迭代对象，指向原来的对象且值expectedModCount值被赋予LinkedList域modCount，那么在迭代结束期间如果有线程对LinkedList对象结构上进行了修改，那么也会抛出ConcurrentModificationException异常，即即时失败。
下面进入源码：
继承了抽象类AbstractSequenceList，实现了接口List、Deque、Cloneable（浅克隆）等。
底层实现是通过内部Node类来实现双向链表结构，first指向链表头节点，last指向链表尾节点。
同样是通过内部类ListItr继承接口Iterator来实现迭代功能。
可以被用作栈或者队列
ArrayList与LinkedList的相同与区别：
相同点：
都是线程不安全的、继承了接口list、serializable、cloneable接口，可以进行迭代访问，同时支持快速失败。
区别：
它们之间的区别主要是它们的底层实现原理不同造成的：
AllayList因为底层是数组来实现的，因此在查找元素的时候，是十分快速的，当然这个优点也变成了其缺点，当要插入（删除）元素的时候，就需要移动后面的元素，同时当插入数量查过现有的容量时会以接近1.5倍的因子扩容，同时要复制数组，因此开销比较大。如果没有指定大小，默认数组大小为10。
LinkedList因为底层实现是利用双向链表来实现，所以对于查找某个元素，是从就近的头或者尾节点开始遍历，相对来说，查找速率比较慢，但是对于插入和删除元素的时候，由于不需要移动元素，只需要修改指针，因此速度比较快。由于使用链表，默认为空，只有添加元素才会出现元素节点。
2、学习下HashSet和TreeSet：
从HashSet源码的注释看起，讲述HashSet的特性：
》实现了Set接口，底层是实现是HashMap，不保证有序，且添加元素可以为NULL
》基础操作add、remove、size、contains常量时间，迭代时间是HashSet的size+HashMap的capacity（因此初始化时capacity不能太大或太小）。
》非同步的，如果多个线程并发访问，至少一个线程进行修改，则必须进行同步：Collections.synchronizedSet(new HashSet());
》同样支持快速失败，性质与上面集合一样。
下面进入源码
HashSet继承了AbstractSet，实现了接口Set、Cloneable（浅克隆）等，内部是以HashMap作为底层存储结构，因此很多方法都是调用map的方法。
HashSet默认无参构造方法调用HashMap的构造方法（初始大小16，参数因子是0.75）,HashSet的值是作为底层HashMap的Key，因此这也是不允许重复的，同时value是一个空的Object对象。如果使用add添加重复数据是会返回false（失败）。而它也是无序（准确说不保证顺序），位置可能会变或者根据不能预测位置。
从TreeSet的源码的注释看起，讲述TreeSet的特性：
》实现了基于TreeMap的NavigableSet接口，元素的排序是根据他们的自然排序或者实现的比较器接口进行排序。
》add、remove、contains方法操作时间是logn
》由于Set接口规范是按照equals方法来比较的，如果按照Set接口规范，就要与equals方法一致。但TreeSet实例使用它的compareTo方法执行所有元素比较，所以如果比较的方法实现中出现了相等就认为相等（比如两个不同对象只有属性年龄一样，如果比较方法是按照年龄来比较，那么相等就会返回0）。按照Set的方法相等就不能插入，所以要修改，比如相等就返回1，而不是0。
》非同步，并发访问修改可以使用包装：Collections.synchronizedSortedSet(new TreeSet())
》快速失败，一其他集合一样特性。
下面进入源码
TreeSet继承了AbstractSet，实现了接口NavigableSet（并没有直接实现Set），Cloneable（浅克隆）
TreeSet的底层实现是treeMap，方法跟多也是直接调用原本方法，同样是使用Map所以也是值作为map的key来使用，而value是一个占位的object对象。TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0。
如果我们将两个对象的equals方法总是返回true，则这两个对象的compareTo方法返回应该返回0。插入的元素不能是NULL，否则无法比较，抛出空指针异常。
相同点：
元素不可重复，非同步，但都可以使用类库包装成线程安全类。都支持快速失败。
不同点：
底层数据结构不一样：HashSet底层结构是HashMap，TreeSet底层实现是treeMap
add、remove、contains操作中HashSet时间复杂度为常量，而TreeSet需要logn
HashSet的数据是无序的，TreeSet中的数据是排好序的
保证唯一性不同：HashSet的唯一性是通过HashCode和equals方法来保证；Treeset则是通过实现comparable或者利用comparator来比较，返回0则表示相等（则属于向重复元素，适当的修改可以实现插入重复元素）
HashSet可以插入一个NULL，但TreeSet不允许
根据特性可以看出如果需要排好序的结构，且不是很频繁变化的可以使用TreeSet。但最常用的就是hashSet，通常性能优于TreeSet。
3、学习下HashMap与TreeMap
HashMap从源码注释看起，讲述HashMap的特性
》基于Hash Table实现,允许key和value值为NULL。与Hashtable大致上相等，除了在非同步和允许为null。不保证有序，随着时间变化，不保证顺序不会变
》基本操作get和put时间为常量时间，迭代遍历集合需要花费代价：Map的capacity加上map的size
》HashMap主要有两个重要参数：capacity和load factor。capacity是HashMap的创建时桶的数量，load factor是权重因子，当前容量乘以权重因子值小于需要扩充的数量时，进行扩容，并且是原来的容量的两倍。
》load factor默认值是0.75，这是一个在时间和空间的平衡，如果值过高，则会造成时间上浪费，如果值过低，则会造成重新进行hash计算分配造成时间上的开销。
》如果有很多元素需要放进去，如果是按照系统自动增长的来扩容，则不如一开始创建一个满足的容量来进行放入原来效率好
》非同步，如果有多个线程进行访问和至少一个线程进行修改，则需要进行同步，可以使用类库工具类来进行包装：Collections.synchronizedMap(new HashMap())
》使用Iterator进行迭代时，支持快速失败，当遍历对象一旦被创建，如果期间有结构上的修改则会抛出异常:ConcurrentModificationException,但如果使用Iterator自带的方法remove的方法除外
》快速失败只能被用于来发现bug，不能被用于正确的程序
下面进入源码
HashMap继承了抽象类AbstractMap，实现了Map接口和cloneable（浅克隆）接口等。
默认初始容量是16，权重因子是0.75,内部元素是内部类Entry数组，Entry包含K、V、hash值和Next对象指针。
当key值为字符串，并且hashSeed不为0时（默认为0），会调用sun.misc.Hashing.stringHash32((String) k)来计算hash值，否则则会调用对象自己的hashcode方法基础上进行hash计算，key如果为NULL，则hash值永远为0。
容量必须是2的n次方，
get方法如果参数key为NULL，则会进行专门查找（hash值为0；table[0]）,返回NULL有两种情况，要么值为NULL，要么HashMap的size为0；
put方法如果传入的参数key已经存在，那么再次放入将会把原来的值给替换，同时返回原来的value。如果不存在则会返回NULL（或者key不存在或者key对应的原来的值为NULL）
如果如果扩容，则最终通过transfer来进行扩容，重新计算hash值，并进行分配位置。
TreeMap从源码注释看起，讲述TreeMap的特性：
》TreeMap是基于红黑树的算法实现，并且排序标准是根据comparable（实现改接口的方法compareTo（参数为1个））或comparator（实现方法compare（两个比较的参数））的接口实现来进行排序具体使用详情参考。
》该集合可以实现在logn的时间里完成containsKey、put、remove、get操作
》集合的顺序是依靠tree map来进行维护的，不论是否显示实现比较接口，如果要正确实现Map接口，那么就需要保持比较器实现与equlas方法一致，这是因为Map是依靠equals方法来实现比较相等，而sorted map判断比较则是根据compareTo或者compare方法来实现的，sorted map这种实现对于排序Map来说是很符合的规范，只不过是违背了Map的规范
》非同步的，如果多个线程都并发访问和至少一个线程进行结构上的修改，则都需要进行额外的同步，同步可以通过类库进行包装：Collections.synchronizedSortedMap(new TreeMap())
》快速失败 当进行迭代的时候，一旦迭代对象（复制一份）被创建，在迭代结束期间，如果集合有任何结构上的修改，都会对抛出异常ConcurrentModificationException，除了使用iterator自带的remove方法。
》同样快速失败只能用于去寻找bug，并不能用于真正的正确代码。
》Map.Entry返回的都是当前时间的快照，不能使用Map.setValue来进行改变映射，但可以使用put进行改变映射。
下面进入源码
TreeMap继承了抽象类AbstractMap，实现了接口NavigableMap、cloneable（浅克隆）等。
内部有一个比较器comparator，如果参数有则可以直接用，没有则用户实现comparable接口也可以。
内部通过实现类Entry（实现接口Map.Entry）来来作为树的节点包含K key; V value;Entry