Java基础—集合

数组与集合区别

数组不是面向对象的，存放基本数据类型与对象，大小需固定且不可改变；集合弥补了数组的缺点，存放的都是对象的引用，而并非对象本身，且集合类容量动态改变。数组无法判断其中有多少元素，只可以通过length属性获取其长度，集合的size()方法可以确切知道元素的个数，集合有多种实现方式和不同适用场合，不像数组仅采用顺序表方式，且集合以类的形式存在，具有封装、继承、多态等类的特性，通过简单的方法和属性即可实现各种复杂操作，大大提高了软件的开发效率。

Java集合

Collection与Map是集合框架的根接口，Java中所有的集合都是继承或实现这两个接口。

Collection子接口有Set和List，其中Set的实现类有：HashSet、LinkedHashSet，Set子接口SortSet接口实现类有TreeSet；List接口实现类有：LinkedList、Vector、ArrayList，Collection接口中还有个Queue接口，其实现类有PriorityQueue。
Map实现类有：HashMap、TreeMap、LinkedHashMap、HashTable等。

List集合

有序列表，允许存放重复的元素
实现类：

ArrayList：数组实现，查询快，增删慢，轻量级，线程不安全，效率高
LinkList：双向链表实现，增删快，查询慢，线程不安全，效率高
Vector：数组实现，重量级，线程安全（使用少），效率低

ArrayList

底层是Object数组，对ArrayList的所有操作底层都是基于数组的，所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点；与LinkList相比，用法上没有什么区别，但是功能上存在一定区别；

ArrayList线程安全性：对ArrayList进行添加元素操作的时候是分两个步骤进行的，第一步即先在Object[size]的位置上存放需要添加的元素，第二步即将size值加一，因此此过程在多线程的环境下是不能够保证具有原子性的，所以ArrayList是线程不安全的；

多线程下使用ArrayList保证线程安全解决方案：1.使用synchronized关键字；2.用用Collection类中的静态方法synchronizedList(),对ArrayList进行调用即可；

未显示指定ArrayList数组长度时，则默认缺省值未10，ArrayList中的对象数组的最大数组容量为Integer.MAX_VALUE-8;

ArrayList的扩容机制：1.首先调用ArrayList.ensureCapacityInternal(size+1)来获取如果元素添加成功后ArrayList中最小容量minCapacity的值；2.调用ArrayList.ensureExplicitCapacity(minCapacity)来确定未来确保添加元素成功是否许愿对ArrayList进行扩容，用minCapacity与当前ArrayList属性长度的大小来判断；3.当minCapacity大于当前ArrayList属性长度时，调用ArrayList.grow(miniCapacity)进行扩容，扩容时首先将当前ArrayList属性长度扩大1.5倍，然后与minCapaCity进行比较，直至当前ArrayList属性长度大于minCapaCity。

LinkList

采用双向循环链表实现，可以用LinkList来实现栈（stack），队列（queue），双向队列（double-ended queue）。

Set集合

扩展了Collection接口，无序集合，不允许存放重复元素，允许使用null元素。

实现类：

HashSet：equals返回true，hashCode返回相同的整数；哈希表，存储的元素是无序的；
LinkHashSet：维护着一个运行于所有条目的双重链接列表，存储元素是有序的；
TreeSet：一个有序集合，提供有序的Set集合；

HashSet

内部实现了Set接口，底层是包装了一个HashMap来实现的，采用HashCode算法来存取集合中的元素，因此具有比较好的读取以及查找性能。

特征：不仅不能保证元素的插入顺序，而且元素在以后的顺序中也可能改变（因为HashSet存储对象是按照Hash算法来决定对象存储的位置）；是线程不安全的；元素值可以为null；

HashSet保证元素唯一性：通过Hash算法来保证，每次存储数据时，先根据hashCode()方法计算出数据在散列表存储中的位置，然后根据equal()方法来判断当前表中是否有已经存在了该元素，equal()相同，则已存在，不需要继续存储，不同则不存在，需要存储。

因此在重写对象中的equal()方法时，相应的hashCode()方法也要重写，，重写前后hashCode返回的hash码相等（即保证存在同一位置）。所有参与计算hashCode（）返回值的关键属性，都应用于作为equals（）比较的标准。

结论：hashCode相等的元素，equal不一定相等，equal相等的元素，hashCode一定相等。重写equal与hashCode方法时要满足这两个条件。

LinkHashSet:

底层数据结构是链表和哈希表。存取规则FIFO（先入先出规则），插入有序，唯一。

LinkHashSet底层数据结构的链表保证了元素之间的有序性，哈希表保证了元素间的唯一性。

TreeSet:

继承AbstractSet抽象类，实现NavigableSet，Cloneable，Serializable接口。TreeSet是基于TreeMap实现的，元素支持两种排序方式：自然排序OR根据提供的Comparator比较器进行排序。

TreeSet底层数据结构是红黑树，具有唯一，有序的特性。保证元素唯一性：通过调取CompareTo()来比较的返回值是否为0来决定是否是重复元素。

TreeSet是依靠TreeMap来实现的。
TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口，在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。

**Comparable和Comparator **
Comparable 接口以提供自然排序顺序。对于那些没有自然顺序的类、或者当您想要一个不同于自然顺序的顺序时，可以实现 Comparator 接口来定义您自己的排序函数。可以将Comparator传递给Collections.sort或Arrays.sort。

**Comparator接口 **
当一个类并未实现Comparable，或者不喜欢缺省的Comaparable行为。可以实现Comparator接口，直接实现Comparator的compare接口完成自定义比较类。
如：Arrays.sort(results, new Comparator() 数组排序 RepDataQueryExecutor
如：Collections.sort(lst,new Comparator()

集中Set的比较：

HashSet外部无序地遍历成员。成员可为任意Object子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。
TreeSet外部有序地遍历成员。附加实现了SortedSet, 支持子集等要求顺序的操作成员要求实现Comparable接口，或者使用Comparator构造
TreeSet成员一般为同一类型。
LinkedHashSet外部按成员的插入顺序遍历成员。
成员与HashSet成员类似。HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。HashSet的元素存放顺序和我们添加进去时候的顺序没有任何关系，而LinkedHashSet 则保持元素的添加顺序。TreeSet则是对我们的Set中的元素进行排序存放。
一般来说，当您要从集合中以有序的方式抽取元素时，TreeSet 实现就会有用处。为了能顺利进行，添加到 TreeSet 的元素必须是可排序的。而您同样需要对添加到TreeSet中的类对象实现 Comparable 接口的支持。一般说来，先把元素添加到 HashSet，再把集合转换为 TreeSet 来进行有序遍历会更快。

各种Set集合性能分析：

HashSet和TreeSet是Set集合中用得最多的I集合。HashSet总是比TreeSet集合性能好，因为HashSet不需要额维护元素的顺序。
LinkedHashSet需要用额外的链表维护元素的插入顺序，因此在插入时性能比HashSet低，但在迭代访问（遍历）时性能更高。因为插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。
EnumSet元素是所有Set元素中性能最好的，但是它只能保存Enum类型的元素

Map

集合框架的第二类接口树。提供了一组键值的映射。其中存储的每个对象都有一个相应的关键字(key)，关键字决定了对象在Map中的存储位置。关键字应该是唯一的，每个key 只能映射一个value。

实现类：

HashMap：键值对，key不能重复，但是value可以重复；key的实现就是HashSet；value对应着放；允许null的键或值；无序的；线程不安全的；
Hashtable：线程安全的，不允许null的键或值；无序的；
TreeMap：对key排好序的Map; key 就是TreeSet, value对应每个key; key要实现Comparable接口或TreeMap有自己的构造器；有序的；
LinkedHashMap：此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有序的。
Properties:：key和value都是String类型，用来读配置文件；

HashMap

Map 主要用于存储键(key)值(value)对，根据键得到值，因此键不允许重复,但允许值重复。是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。
HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。

HashMap实现原理—散列
Hash哈希算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系。散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中地址。当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子0.75，当散列表中已经有75%位置已经放满，那么将进行再散列。
负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。

何时需重写equals？
当一个类有自己特有的“逻辑相等”概念（不同于对象身份的概念）；
Object类仅仅提供了一个对引用的比较，如果两个引用不是同一个那就返回false，这是无法满足大多数对象比较的需要的，所以要覆盖；
使用操作符检查实参是否为指向对象的引用”
使用instanceof操作符检查实参是否为正确的类型
把实参转换到正确的类型；
对于该类中每一个“关键”域，检查实参中的域与当前对象中对应的域值是否匹配。对于既不是float也不是double类型的基本类型的域，可以使用操作符进行比较；对于对象引用类型的域，可以递归地调用所引用的对象的equals方法，对于float和double类型的域，先转换成int或long类型的值，然后使用==操作符比较；
当你编写完成了equals方法之后，应该问自己三个问题：它是否是对称的、传递的、一致的？如果答案是否定的，那么请找到这些特性未能满足的原因，再修改equals方法的代码

equals()和hashCode()同时覆写
尤其强调当一个对象被当作键值（或索引）来使用的时候要重写这两个方法；
覆写equals后，两个不同实例可能在逻辑上相等，但是根据Object.hashCode方法却产生不同的散列码，违反“相等的对象必须具有相等的散列码”。
导致，当你用其中的一个作为键保存到hashMap、hasoTable或hashSet中，再以“相等的”找另一个作为键值去查找他们的时候，则根本找不到
不同类型的hashCode取值
如果该域是布尔型的，计算（f？0：1）
如果是char,short,byte或int，计算(int)f
如果是long类型，计算（int）(f^(f>>>32))
如果是float类型，计算Float.floatToIntBits（f）
如果是double类型，计算Dobule.doubleToLongBits(f)
如果该域是一个对象引用，递归调用hashCode
如果该域是一个数组，则把每个元素当做单独的域来处理，对每个重要的元素计算一个散列码（hash码）。

Map集合比较：

HashMap的存入顺序和输出顺序无关。
LinkedHashMap 则保留了键值对的存入顺序。
TreeMap则是对Map中的元素进行排序。
因为HashMap和LinkedHashMap 存储数据的速度比直接使用TreeMap 要快，存取效率要高。
当完成了所有的元素的存放后，我们再对整个的Map中的元素进行排序。这样可以提高整个程序的运行的效率，缩短执行时间。
注意：TreeMap中是根据键（Key）进行排序的。而如果我们要使用TreeMap来进行正常的排序的话，Key 中存放的对象必须实现Comparable 接口。

Hashtable是线程安全的，HashMap不是线程安全的。
HashMap效率较高，Hashtable效率较低。
如果对同步性或与遗留代码的兼容性没有任何要求，建议使用HashMap。查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized关键字，而HashMap的源码中则没有。
Hashtable不允许null值，HashMap允许null值（key和value都允许）
父类不同：Hashtable的父类是Dictionary，HashMap的父类是AbstractMap

总结

TreeSet, LinkedHashSet and HashSet 的区别

TreeSet, LinkedHashSet and HashSet 在java中都是实现Set的数据结构，TreeSet的主要功能用于排序LinkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)HashSet只是通用的存储数据的集合。

相同点：

Duplicates elements: 因为三者都实现Set interface，所以三者都不包含duplicate elements。
Thread safety: 三者都不是线程安全的，如果要使用线程安全可以Collections.synchronizedSet()。

不同点：

Performance and Speed: HashSet插入数据最快，其次LinkHashSet，最慢的是TreeSet因为内部实现排序。

HashMap和Hashtable的区别：

HashMap和Hashtable都是java的集合类，都可以用来存放java对象，这是他们的相同点：

历史原因：Hashtable是基于陈旧的Dictionary类的，HashMap是java 1.2引进的Map接口的一个现实。
同步性：Hashtable是同步的，这个类中的一些方法保证了Hashtable中的对象是线程安全的，而HashMap则是异步的，因此HashMap中的对象并不是线程安全的，因为同步的要求会影响执行的效率，所以如果你不需要线程安全的结合那么使用HashMap是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销，从而提高效率，我们一般所编写的程序都是异步的，但如果是服务器端的代码除外。
值：HashMap可以让你将空值作为一个表的条目的key或value，Hashtable是不能放入空值（null）的。

ArrayList和Vector的区别：

ArrayList与Vector都是java的集合类，都是用来存放java对象，这是他们的相同点。

同步性：Vector是同步的，这个类的一些方法保证了Vector中的对象的线程安全的，而ArrayList则是异步的，因此ArrayList中的对象并不是线程安全的，因为同步要求会影响执行的效率，所以你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带来的不必要的性能开销。
数据增长：从内部实现的机制来讲，ArrayList和Vector都是使用数组（Array）来控制集合中的对象，当你向两种类型中增加元素的时候，如果元素的数目超过了内部数组目前的长度他们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%，所以最后你获得的这个集合所占的空间总是比你实际需要的要大，所以如果你要在集合中保存大量的数据，那么使用Vector有一些优势，因为你可以通过设置集合的初始大小来避免不必要的资源开销。

因此，如果要求线程安全，使用Vector，Hashtable；如果不要求线程安全，使用ArrayList，LinkedList，HashMap；如果要求键值对，则使用HashMap，Hashtable；如果数据量很大，又要求线程安全考虑Vector。

arraylist和linkedlist联系与区别：

ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

HashMap与TreeMap联系与区别：

HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。
在Map 中插入、删除和定位元素，HashMap是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。
两个map中的元素一样，但顺序不一样，导致hashCode()不一样。
同样做测试：在HashMap中，同样的值的map,顺序不同，equals时，false;而在treeMap中，同样的值的map,顺序不同,equals时，true，说明，treeMap在equals()时是整理了顺序了的。

目录CONTENT