java是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE, JavaME, JavaSE)的总称。本站提供基于Java框架struts,spring,hibernate等的桌面应用、web交互及移动终端的开发技巧与资料

保持永久学习的心态,将成就一个优秀的你,来 继续搞起java知识。

java之容器

先来一张容器的API框架图:

容器API:

1、Collection接口------定义了存储一组对象的方法,其子接口Set和List分别定义了存储的方式。

①、Set中的数据对象没有顺序且不可以重复。

②、List中的数据对象有顺序且可以重复。

2、Map接口定义了存储“键(key)---值(value)映射对”的方法。

Collection接口

  Collection结构可持有各自独立的对象。在J2SE中,Collection包括了List与Set,List是实现java.util.List接口的相关类,可依对象被放置至容器中的顺序来排列对象。Set是实现java.util.Set接口的相关类,不接受重复的对象,并可拥有一套排序规则。

1. List接口

(1) List接口是java.util.Colleciton接口的子接口,而Collection接口则是java.lang.Iterable的子接口。Iterable接口要求实现一个iterator()方法。

(2) Iterable接口要求实现它的类返回一个实现java.util.Iterator接口的对象,事实上在J2SE的API中找不到任何实现Iterator的类,因为Iterator会根据实际的容器数据结构来迭代元素,而容器的数据结构实现方式对外界是隐藏的,使用者不用知道这个结构,只需要知道Iterator的实现方法,就可以取出元素。

Collection接口继承了Iterator接口,定义了加入元素、删除元素、元素长度等方法。

package java.util;

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

Collection在删除元素及取得元素上的定义比较通用,List接口则又增加了根据索引取得对象的方法,这说明了List数据结构的特性,每个加入List中的元素是循序加入的,并可指定索引来存取元素。   

(3)ArrayList: ArrayList实现了List接口,使用数组结构实现List数据结构。数组的特性是可以利用索引来快速指定对象的位置,所以对于快速的随机取得对象来说,使用ArrayList可以得到较好的效率。但由于使用数组实现,若要从中间作删除或插入对象的动作,会需要移动后段的数组元素以重新调整索引顺序,所以速度上会慢得多。

(4) LinkedList:List默认是以对象加入(Add)容器的顺序来排列它们,List上的add()方法也可以指定位置插入对象。如果对象加入之后是为了取出,而不会常作删除或插入的动作,则用ArrayList效率会比较好。如果经常从容器中作插入或删除的动作,则用java.util.LinkedList会获得较好的效率。由于使用LinkedList使用链表,在进行插入或删除动作时有较好的效果,适合用来实现堆栈(Stack)与队列(Queue)。下面是利用LinkedList实现的一个先进先出的队列实例,当然也可以利用LinkedList来实现一个先进后出的堆栈类。

package onlyfun.caterpillar;

import java.util.*;

public class StringQueue
{
	private LinkedList<String> linkedList;

	public StringQueue()
	{
		linkedList = new LinkedList<String>();
	}

	public void put(String name)
	{
		linkedList.addFirst(name);
	}

	public String get()
	{
		return linkedList.removeLast();
	}

	public boolean isEmpty()
	{
		return linkedList.isEmpty();
	}
}

2. HashSet:java.util.HashSet实现了java.util.Set接口,Set接口一样继承了Collection接口。List容器中的对象允许重复,但Set容器中的对象不许重复,都是唯一的。加入Set容器中的对象都必须重新定义equals()方法,用作Set中对象的唯一识别。Set容器有自己的一套排序规则。

HashSet的排序规则是利用哈希法(Hash),所以加入HashSet容器的对象还必须重新定义hashCode()方法。HashSet根据哈希码来确定对象在容器中存储的位置,也可以根据哈希码来快速地找到容器中的对象。在定义类时最好总是重新定义equals()与hashCode()方法,以符合Java的设计规范。下面程序片段展示了如何使用HashSet。

package ysu.hxy;
import java.util.*;

public class HashSetDemo
{
	public static void main(String[] args) 
	{
		Set<String> set = new HashSet<String>();
		
		set.add("sssssssss");
		set.add("ttttttt");
		set.add("gggggggg");

		//故意加入重复的对象 
        set.add("gggggggg");

		//使用Iterator显示对象
		Iterator iterator = set.iterator();
		while(iterator.hasNext())
			System.out.print(iterator.next()+ " ");
		System.out.println();

		set.remove("gggggggg");

		for(String name:set)
		{
			System.out.print(name+" ");
		}
		System.out.println();
	}
}

3.TreeSet:TreeSet实现Set接口与java.util.SortedSet接口,SortedSet提供相关的方法让您有序地取出对应位置的对象,像first()、last()等方法。TreeSet是J2SE中唯一实现SortedSet接口的类,它使用红黑树结构来对加入的对象进行排序。

package ysu.hxy;
import java.util.*;

public class TreeSetDemo
{
	public static void main(String[] args) 
	{
		Set<String> set = new TreeSet<String>();

		set.add("justin");
		set.add("caterpillar");
		set.add("momor");

		for(String name: set)
			 System.out.print(name+ " ");
		System.out.println();
	}
}

输出结果是:caterpillar justin momor。TreeSet默认的排序是依字典顺序来进行的。如果对对象有自己的一套排列顺序,要定义一个实现java.util.Comparator接口的对象,要实现接口中的compare()方法, compare()方法必须返回整数值。如果对象顺序相同则返回0,返回正整数表示compare()方法中传入的第一个对象大于第二个对象,反之则返回负整数。举个实际例子,假设想要改变TreeSet依字典顺序排列加入的对象为相反的顺序,可以如下自定义一个实现Comparator接口的类。

package ysu.hxy;
import java.util.Comparator;

public class CustomComparator<T> implements Comparator<T>
{
	public int compare(T o1,T o2)
	{
		if(((T)o1).equals(o2))
			return 0;
		return ((Comparable<T>)o1).compareTo((T)o2)*-1;
	}
}

在此自定义的Comparator中,两个对象顺序相同会返回0,而为了便于比较,Comparator传入的对象必须实现Comparable接口(例如String对象就有实现Comparable接口)。乘以-1表示以字典顺序反序进行排列。用以下代码来使用自定义的排序方式,在建构TreeSet实例时一并指定自定义的Comparator。

package ysu.hxy;
import java.util.*;

public class TreeSetDemo2
{
	public static void main(String[] args) 
	{
		//自定义Comparator
		Comparator<String> comparator = new CustomComparator<String>();
		Set<String> set = new TreeSet<String>(comparator);

		set.add("justin");
		set.add("caterpillar");
		set.add("momor");

		for(String name:set)
			System.out.print(name + " ");

		System.out.println();
	}
}

输出结果与上面的输出结果正好相反:momor justin caterpillar。

二 Map类:

实现java.util.Map接口的对象会将键(Key)映射至值(Value),值指的是存入Map容器的对象。在将对象存入Map对象时,需要同时给定一个键,要取回对象时可以指定键,这样就可以取得与键对应的对象值。Map中的每一个键都是唯一的,不能有重复的键,Map拥有自己的排序机制。1. HashMap

HashMap是基于哈希表的Map接口的非同步实现(Hashtable跟HashMap很像,唯一的区别是Hashtalbe中的方法是线程安全的,也就是同步的)。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。

可以看出,Entry就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。

从上面的源代码中可以看出:当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

addEntry(hash, key, value, i)方法根据计算出的hash值,将key-value对放在数组table的 i 索引处。addEntry 是HashMap 提供的一个包访问权限的方法当系统决定存储HashMap中的key-value对时,完全没有考虑Entry中的value,仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value 随之保存在那里即可。

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中是这样做的:调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。

static int indexFor(int h, int length) {
    return h & (length-1);
}

当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

  从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。  归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

因为水平有限,难免有疏忽或者不准确的地方,希望大家能够直接指出来,我会及时改正。一切为了知识的分享。

后续会有更多的精彩的内容分享给大家。