Java常用集合总结

基本数据类型包装类（如Integer，Boolean）：为了方便操作基本数据类型值，将其封装成了对象，在对象中定义了属性和行为，丰富了该数据的操作。

集合容易因为内部的数据结构不同，有多种具体的容易。不断的向上抽取，就形成了集合框架。

框架的顶层就是Collection接口。

Collection继承自Iterable接口，Iterable接口只有一个方法就是：Iterator iterator(); 就是获取迭代器。

Iterator的remove方法：必须先调用iterator.next()方法，否则会报异常，具体参见API文档。它删除的是iterator.next()获取的对象。

注意 Iterator也是一个接口;具体的集合实现Iterable接口中的iterator方法，取决于集合自己，一般是自己定义一个内部类去实现Iterator接口。这个要搞清楚。

关于循环迭代器：最好用for循环，这样的话，循环完了，it就消失了。如for(Iterator it = coll.iterator; it.hasNext(););

Map 跟Map.Entry都是接口。

List跟Set都是接口。

List：有序，列表允许有重复的元素！如果列表允许有null元素（具体的类实现），则可以存在多个null。

1.ArrayList：内部是可变长度数组数据结构，是不同步的。效率比Vector高。查询的速度快。替代了Vector。数组长度可变的原理：创建新数组，把旧数据复制到新的数组。50%延长。

2.LinkedList：List的链表实现，也是不同步的，增删速度非常快。虽然也是List有索引的属性，但是查找的时候还是得从头一个个的找。

3.Vector：内部是可变长度数组数据结构。Vector是同步的，是线程安全的。100%延长。

数组增删元素，数据顺延，速度慢，不如链表，但是查询速度快。

Set：无序，元素不允许重复！如果允许null，至多存在一个null。取出方式只有Iterator。

1.HashSet：由哈希表（实际上是一个HashMap）支持。不同步。内部有一个数组，每次存元素的时候，先根据哈希算法算出元素位置的index（内部算法：index = hash &(length -1)，因为length的值总为2的n次方，所以结果总是在length范围内。因为hashMap的容量是取传大于入容量的2的n次方的最小值，默认容量是16，而且默认扩容是size*2，所以length总是2的n次方），然后存入，查找的时候类似，所以速度非常快。

哈希表底层实现还是数组，但是进行了优化。

哈希表存值的时候，如果算出来的哈希值相同（hashCode方法），再判断里面的内容是否相同（equals方法）。

如果都相同的解决方式，也不唯一，比如往后顺延，或者串联（在下面挂一个）。对于HashSet，如果equals也相同，则认为是重复的，不再存。

注意：关于new两个对象，比如new Student("zhaosi", 24);两个对象的hashCode不相同，而且对于同一个对象，每次运行的hashCode也是不相同的（不重写hashCode方法的前提下）。

集合中的contains方法调用的还是对象的equals方法。

LinkedHashSet:HashSet的子类。具有可预知迭代顺序的Set接口的哈希表和链表的实现。怎么存，怎么取。

2.TreeSet：按照元素的自然顺序进行排序，或者根据创建set时提供的Comparator进行排序，具体取决于使用的构造方法。比较结果返回0表示两个对象相等，不存。

Map：不继承任何接口。map中的key唯一，而且每个key最多只能映射到一个value。

取出map中的所有元素：

1.通过keySet方法获取map中所有键的Set集合，再通过Set 的迭代器获取到每一个键，再对每一个键获取其对应的值。

2.通过entrySet方法，拿到映射关系，然后通过迭代器取出值。

为什么map取出来的key跟Map.Entry都是set集合，因为set集合的元素是唯一的，而map集合的key也是唯一的。

Map.Entry是一个接口。

Map常用的子类：

|--HashTable：内部结构是哈希表，是同步的。不允许null键和null值。

子类：Properties----用来存储键值队型的配置文件的信息，可以和IO技术相结合。

|--HashMap：内部结构是哈希表，不同步的，允许使用null值和null

键。

|---LinkedHashMap:具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。是不同步的。

|--TreeMap: 内部结构是二叉树，不是同步的。可以对Map集合中的键进行排序。是有序的，对键的自然顺序或者是传入比较器进行排序。类似于TreeSet。

Comparable：接口，只有一个方法 int compareTo（T o）;。 比较此对象与指定对象的顺序。（注意是此对象，就是实现该接口的对象）。实现此接口的类，称作类的自然排序。

Comparator：接口，有两个方法；

int compare（T o1, T o2）;比较用来排序的两个参数。

boolean equals(Object obj); 只是某个其他对象是否“等于”此Comparator。对于TreeSet想有序，直接返回1，想逆序，直接返回-1；

如果不要按照对象中具备的自然顺序排序，或者对象中不具备自然排序，可以用Comparator。

二叉树的数据结构：每一个树的节点记录着父节点的引用，左分支的引用，右分枝的引用，如果有的话。