java数据结构小结


数组

int a[];a=new int[10];
int[] b;
int []d=new int[10];
int c[]={1,2,3,4,5}

以上写法都是正确的。

List

LinkedList

LinkedList实现了List接口,允许null元素。运行在头部和尾部插入,可以用来维护栈、队列或双向队列。
LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:

List list = Collections.synchronizedList(new LinkedList(...));

ArrayList

ArrayList实现了可变大小的数组。它允许null非同步 ,基本类似于C++里的vector,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

Vector

Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。

若是没有线程要求,尽量使用ArrayList。Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%

Stack

Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set

Set是一种不包含重复的元素的Collection,最多只允许一个null元素。
所以要小心set中出现可变对象,都是不同步的,多线程都不安全。

HashSet

不能保证元素排序顺序,类似于HashMap

TreeSet

类比C++,红黑树实现。

Map

HashTable

Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。Hashtable是同步的。

HashMap

HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key。

WeakHashMap

WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。

本文地址: http://www.dzglalala.cn/2016/10/18/Java数据结构/