├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
|-HashSet
└TreeSet
Map
├Hashtable
├HashMap
└WeakHashMap
把稳:Map没有继续Collection接口,Map供应key到value的映射。ListLinkedList类LinkedList实现了List接口,许可null元素。此外LinkedList供应额外的get,remove,insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),行列步队(queue)或双向行列步队(deque)。把稳LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种办理方法是在创建List时布局一个同步的List:List list = Collections.synchronizedList(new LinkedList(…));
特点:寻址困难,插入和删除随意马虎。
ArrayList类ArrayList实现了可变大小的数组。它许可所有元素,包括null。ArrayList没有同步。size,isEmpty,get,set方法运行韶光为常数。但是add方法开销为分摊的常数,添加n个元素须要O(n)的韶光。其他的方法运行韶光为线性。每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并 没有定义。当须要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。和LinkedList一样,ArrayList也是非同步的(unsynchronized)。特点是:寻址随意马虎,插入和删除困难;Vector类Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的 Iterator是同一接口,但是,由于Vector是同步的,当一个Iterator被创建而且正在被利用,另一个线程改变了Vector的状态(例 如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该 非常。Stack 类Stack继续自Vector,实现一个后进先出的堆栈。Stack供应5个额外的方法使得 Vector得以被当作堆栈利用。基本的push和pop 方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。SetHashSet类它不许可涌现重复元素;不担保凑集中元素的顺序许可包含值为null的元素,但最多只能有一个null元素。HashSet的实现是不同步的。TreeSet类TreeSet类实现 Set 接口,该接口由 TreeMap 实例支持。此类担保排序后的 set 按照升序排列元素,根据利用的布局方法不同,可能会按照元素的自然顺序 进行排序,或按照在创建 set 时所供应的比较器进行排序。TreeSet描述的是Set的一种变体——可以实现排序等功能的凑集,它在将工具元素添加到凑集中时会自动按照某种比较规则将其插入到有序的工具序列中.HashSet是基于Hash算法实现的,其性能常日优于TreeSet,我们常日都该当利用HashSet,在我们须要排序的功能时,我门才利用TreeSet;Map接口Hashtable类Hashtable继续Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的工具都可作为key或者value。 添加数据利用put(key, value),取出数据利用get(key),这两个基本操作的韶光开销为常数。Hashtable 通过initial capacity和load factor两个参数调度性能。常日缺省的load factor 0.75较好地实现了韶光和空间的均衡。增大load factor可以节省空间但相应的查找韶光将增大,这会影响像get和put这样的操作。作为key的工具将通过打算其散列函数来确定与之对应的value的位置,因此任何作为key的工具都必须实现hashCode和equals方法。 Hashtable是同步的。HashMap类HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且许可null,即null value和null key。其迭代子操作韶光开销和HashMap 的容量成比例,因此,不要将HashMap的初始化容量设得过高,或者load factor过低。WeakHashMap类WeakHashMap是一种改进的HashMap,它对key实施“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。hashmap遍历的两种办法HashMap的遍历有两种常用的方法,那便是利用keyset及entryset来进行遍历方法一:Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
效率高,往后只管即便要利用此种办法!方法二:
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
效率低,往后只管即便少利用!HashMap的数据构造HashMap里面实现一个静态内部类Entry,其主要的属性有 key , value, next.数据value的值是元素的key的哈希值对数组长度取模得到。如下面第二幅图中,12%16=12,28%16=12,108%16=12,140%16=12。以是12、28、108以及140都存储在数组下标为12的位置。构造如图所示:
HashMap的存取实现
// 存储时:
int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value; <br/>
// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];
办理hash冲突的办法开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)再哈希法链地址法建立一个公共溢出区Java中hashmap的办理办法便是采取的链地址法。再散列rehash过程当哈希表的容量超过默认容量时,必须调度table的大小。当容量已经达到最大可能值时,那么该方法就将容量调度到Integer.MAX_VALUE返回,这时,须要创建一张新表,将原表的映射到新表中。