看一段set的簡(jiǎn)單應(yīng)用代碼
Set<String> set = new HashSet<String>();
String a = "1",b = "2",c = "1",d = "3",e = "2";
set.add(a);
set.add(b);
set.add(c);
set.add(d);
set.add(e);
Iterator it = set.iterator();
while(it.hasNext()){
String s = (String)it.next();
System.out.print(s+",");
}
System.out.println("一共有對(duì)象："+set.size()+"個(gè)"); //打印結(jié)果是：3,2,1,一共有對(duì)象：3個(gè)
我們都知道Set是一種最簡(jiǎn)單的集合，對(duì)象的排序無(wú)特定的規(guī)則，集合里面存放的是對(duì)象的引用，所以沒(méi)有重復(fù)的對(duì)象，在上面的代碼中，程序創(chuàng)建了a、b、c、d、e五個(gè)變量，其中a和c，b和e所引用的字符串是一致的，然后向set添加了這5個(gè)變量。打印出來(lái)的size()只有3個(gè)，實(shí)際上向集合加入的只有3個(gè)對(duì)象，在執(zhí)行Set的add()方法時(shí)已經(jīng)進(jìn)行了判斷這個(gè)對(duì)象是否存在于集合，如果對(duì)象已經(jīng)存在則不繼續(xù)執(zhí)行。
Set的接口有兩個(gè)實(shí)現(xiàn)類(lèi)，HashSet和TreeSet，HashSet是按照哈希算法來(lái)進(jìn)行存取集合中的對(duì)象，存取速度比較快，TreeSet類(lèi)顯示了SortedSet接口，具有排序功能
HashSet
HashSet是按照哈希算法來(lái)存取集合中的對(duì)象，具有很好的存取和查找性能，當(dāng)向集合中加入一個(gè)對(duì)象時(shí)，HashSet會(huì)調(diào)用對(duì)象的hashCode()方法來(lái)獲取哈希碼，然后根據(jù)這個(gè)哈希嗎來(lái)計(jì)算對(duì)象在集合中的存放位置。
在Object類(lèi)中定義了hashCode()和equal()，equal()是按照內(nèi)存地址比較對(duì)象是否相同，如果object1.equal(object1)w為true時(shí)，則表明了object1和object2變量實(shí)際上引用了同一個(gè)對(duì)象，那么object1和object2的哈希碼也是肯定相同。
稍微的看看HashSet的源碼
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<E,Object>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
}
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
}
我們會(huì)發(fā)現(xiàn)我們調(diào)用Set的add()方法其實(shí)是返回一個(gè)transient HashMap.put(e, PRESENT)，再跟進(jìn)HashMap的put(K key, V value)方法進(jìn)行查看,可以看到int hash = hash(key.hashCode());使用了set.add(key)的key做了一個(gè)哈希處理得到一個(gè)哈希碼，然后再將Entry做了一個(gè)遍歷，使用equal()方法對(duì)講原有的對(duì)象和新添加的對(duì)象進(jìn)行了一個(gè)比較，如果出現(xiàn)了true的情況，就直接返回一個(gè)oldValue，如果在遍歷對(duì)比的過(guò)程中沒(méi)有出現(xiàn)ture的情況，則繼續(xù)一下的步驟modCount++，將對(duì)象總數(shù)自加，并且繼續(xù)執(zhí)行addEntry()的操作，下面涉及HashMap的操作就不繼續(xù)。
實(shí)際上HashSet的底層實(shí)現(xiàn)是基于HashMap，所以在此處涉及到Hash算法不展開(kāi)，詳細(xì)可以見(jiàn)另一篇《
java數(shù)據(jù)結(jié)構(gòu)-HashMap》
TreeSet
TreeSet類(lèi)是實(shí)現(xiàn)了SortedSet接口，所以能夠?qū)现械膶?duì)象進(jìn)行排序
Set iset = new TreeSet();
iset.add(new Integer(1));
iset.add(new Integer(10));
iset.add(new Integer(5));
iset.add(new Integer(8));
iset.add("2");
Iterator it2 = iset.iterator();
while(it2.hasNext()){
Integer s = (Integer)it2.next();
System.out.print(s+",");
}
System.out.println("一共有對(duì)象："+iset.size()+"個(gè)");//打印出來(lái)的結(jié)果：1,2,5,8,10,一共有對(duì)象：5個(gè)
當(dāng)TreeSet向集合加入一個(gè)對(duì)象時(shí)，會(huì)把它插入到有序的對(duì)象序列中，TreeSet包括了兩種排序方式，自然排序和客戶(hù)化排序，在默認(rèn)的情況下使用自然排序。
自然排序
在jdk類(lèi)庫(kù)中，有部分類(lèi)實(shí)現(xiàn)了Comparable接口，如Integer，Double等等，Comparable接口有一個(gè)compareTo()方法可以進(jìn)行比較，TreeSet調(diào)用對(duì)象的compareTo()方法比較集合中對(duì)象的大小，然后進(jìn)行升序排序。如Integer：
public final class Integer extends Number implements Comparable<Integer> {
public int compareTo(Integer anotherInteger) {
int thisVal = this.value;
int anotherVal = anotherInteger.value;
return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
}
}
基于Comparable的屬性，使用自然排序時(shí)，只能向TreeSet集合中加入同類(lèi)型的對(duì)象，并且這些對(duì)象的類(lèi)必須實(shí)現(xiàn)了Comparable的接口，以下我們嘗試向TreeSet集合加入兩個(gè)不同類(lèi)型的對(duì)象，會(huì)發(fā)現(xiàn)拋出ClassCastException
Set iset = new TreeSet();
iset.add(new Integer(1));
iset.add(new Integer(8));
iset.add("2");
Exception in thread "main" java.lang.ClassCastException: java.lang.Integer
我們?cè)俅蜷_(kāi)TreeSet的源碼進(jìn)行查看
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
}
NavigableMap為接口，實(shí)現(xiàn)類(lèi)為T(mén)reeMap
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key); //此處如果類(lèi)別不相同可能拋出ClassCastException
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
}
首先判斷原始集合是否存在，如果不存在則直接創(chuàng)建，無(wú)需比較。
如果原始集合存在的話，先去取出Comparator對(duì)象，然后遍歷原始集合t，使用parent為臨時(shí)比較值，逐個(gè)使用compare(key, t.key)方法與添加對(duì)象key進(jìn)行比較，決定元素排在集合的left或right。
客戶(hù)端排序
客戶(hù)端排序時(shí)因?yàn)閖ava.util.Comparator<Type>接口提供了具體的排序方式，<Type>指定了被比較對(duì)象的類(lèi)型，Comparator有個(gè)compare(Type x,Type y)的方法，用于比較兩個(gè)對(duì)象的大小。
public class NameComparator implements Comparator<Name>{
public int compare(Name n1,Name n2){
if(n1.getName().compareTo(n2.getName())>0) return -1;
if(n1.getName().compareTo(n2.getName())<0) return 1;
return 0;
}
public static void main(String[] args) {
Set<Name> set = new TreeSet<Name>(new NameComparator());
Name n1 = new Name("ray");
Name n2 = new Name("tom");
Name n3 = new Name("jame");
set.add(n1);
set.add(n2);
set.add(n3);
Iterator it = set.iterator();
while(it.hasNext()){
Name s = (Name)it.next();
System.out.print(s.getName()+",");
}
System.out.println("一共有對(duì)象："+set.size()+"個(gè)");
}
}//打印結(jié)果是：tom,ray,jame,一共有對(duì)象：3個(gè)
道理與自然排序其實(shí)相同，都是通過(guò)實(shí)現(xiàn)Comparator接口，就不細(xì)說(shuō)了,可能有些說(shuō)得不對(duì)的地方，歡迎指正
----------------------------------------
by 陳于喆
QQ:34174409
Mail: dongbule@163.com