java的数据结构

数据结构

Array数组

和C/C++以及其他语言一样，Java中的数组有差不多一样的语法。只是Java中除了8中基本类型，数组也是作为对象处理的，所以创建对象时也需要使用new关键字。和大多数编程语言一样，数组一旦创建，大小便不可改变。

Java中有一个Arrays类，专门用来操作array。

Arrays中拥有一组static函数，

- equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等。

- fill()：将值填入array中。

- sort()：用来对array进行排序。

- binarySearch()：在排好序的array中寻找元素。

- System.arraycopy()：array的复制。

Array是Java中随机访问一连串对象最有效率的数据结构，但很不灵活，大小固定，且不知道里面有多少元素。为此JDK已经为我们提供了一系列相应的类来实现功能强大且更灵活的基本数据结构。这些类均在java.util包中。其继承结构如下：

Collection

List

LinkedList

ArrayList

Vector

Stack

1）  Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe)，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此,ArrayList的性能比Vector好。

2） 当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%的大小，这样,ArrayList就有利于节约内存空间。

ArrayList的内部实现是基于内部数组Object[],所以从概念上讲,它更象数组，但LinkedList的内部实现是基于一组连接的记录，所以，它更象一个链表结构，所以，它们在性能上有很大的差别：

从上面的分析可知,在ArrayList的前面或中间插入数据时,你必须将其后的所有数据相应的后移,这样必然要花费较多时间，所以,当你的操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能； 而访问链表中的某个元素时,就必须从链表的一端开始沿着连接方向一个一个元素地去查找,直到找到所需的元素为止，所以,当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。

Set

SortedSet

Queue

Map

HashTable

HashMap

WeakHashMap

Hashtable和HashMap它们的性能方面的比较类似 Vector和ArrayList，比如Hashtable的方法是同步的,而HashMap的不是。

List

List是一个接口，不能实例化，需要实例化一个ArrayList或者LinkedList。

ArrayList里面的内部实现，是通过一定的增长规则动态复制增加数组长度来实现动态增加元素的。如果在大数据量的情况下，在某一个位置随机插入或者删除元素，就会产生性能问题。LinkedList可以解决这类问题，但LinkedList在通过下标取元素的时候，需要遍历整个链表节点匹配，数据量大的情况下，效率不高。Vector是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。Stack是Java实现了一个堆栈，先进后出结构。

遍历时删除问题

使用增强for循环遍历List(所有实现子类ArrayList,Stack等)元素对其中元素进行删除，会抛出java.util.ConcurrentModificationException的异常。若使用下面这种方式：

for(int i = 0;i < list.size();i++){

list.remove(i);

}

则会删除下标为偶数的元素，因为每次删除后，后面的元素的下标全部减1，相当于元素位置全部左移一位，再次删除时，会跳过一个元素进行删除。这是非常不好的。如果非得要这样删除，可以倒着来：

for(int i = list.size()-1 ;i >= 0 ;i--){

list.remove(i);

}

或者新建一个要删除的List，最后一起删除。list.removeAll(deleteList);

Set

Set接口继承Collection接口，最大的特点是集合中的元素都是唯一的，没有重复。它有两个子类，HashSet和TreeSet。

HashSet

不允许出现重复元素；

不保证集合中元素的顺序。哈希算法来的~

允许包含值为null的元素，但最多只能有一个null元素。

HashSet

不允许出现重复元素；

不保证集合中元素的顺序。哈希算法来的~

允许包含值为null的元素，但最多只能有一个null元素。

Map

Map接口，没有继承Collection接口，它是独立的一个接口。它使用key-value的键值对存储数据。常用的两个子类是HashMap和TreeMap。

- HashMap：Map基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor，以调整容器的性能。

- LinkedHashMap： 类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一点。而在迭代访问时发而更快，因为它使用链表维护内部次序。

- TreeMap ： 基于红黑树数据结构的实现。查看“键”或“键值对”时，它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在 于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。

- WeakHashMao ：弱键(weak key)Map，Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”，则此“键”可以被垃圾收集器回收。

- IdentifyHashMap： : 使用==代替equals()对“键”作比较的hash map。专为解决特殊问题而设计。