Java温故知新 - 集合类 - JAVA

一、常用集合类实现

1.ArrayDeque/LinkedList：双端队列的数组和链表实现

2.HashSet/Map：散列表

3.TreeSet/Map：红黑树

实际上，TreeSet在内部使用了TreeMap，当添加新元素时，会向TreeMap放入一个空Object作为值。

3.1 在实现Comparable和Comparator的compare方法时，正数表示：该对象或参数1对象大。

因此，用参数2对象的域值减去参数1的对于域将会产生倒序。
建议：compare()==0时equals()==true

3.2 向TreeSet放入未实现Comparable接口的类会在运行时产生ClassCaseException。

3.3 若构造TreeSet时，传入了自定义的Comparator，则比较时将会以Comparator的compare方法为准。
源码参见：TreeMap的put方法。

[java]
public class TreeSetTest {

public static void main(String[] args) {

TreeSet setById = new TreeSet();

// 1.Exception if Item not implement Comparable interface
// Exception in thread "main" java.lang.ClassCastException: Item cannot be cast to java.lang.Comparable

setById.add(new Item(1, "level 9"));
setById.add(new Item(2, "level 2"));
setById.add(new Item(3, "level 5"));

System.out.println(setById);

// 2.Use comparator

TreeSet setByDesc = new TreeSet(
new Comparator() {
@Override
public int compare(Item o1, Item o2) {
return o1.desc.compareTo(o2.desc);
}
});
setByDesc.addAll(setById);

System.out.println(setByDesc);
}

}

class Item implements Comparable {

int id;
String desc;

Item(int id, String desc) {
this.id = id;
this.desc = desc;
}

@Override
public int compareTo(Item o) {
return id - o.id;
}

@Override
public String toString() {
return "Item [id=" + id + ", desc=" + desc + "]";
}

}

public class TreeSetTest {

public static void main(String[] args) {

TreeSet setById = new TreeSet();

// 1.Exception if Item not implement Comparable interface
// Exception in thread "main" java.lang.ClassCastException: Item cannot be cast to java.lang.Comparable

setById.add(new Item(1, "level 9"));
setById.add(new Item(2, "level 2"));
setById.add(new Item(3, "level 5"));

System.out.println(setById);

// 2.Use comparator

TreeSet setByDesc = new TreeSet(
new Comparator() {
@Override
public int compare(Item o1, Item o2) {
return o1.desc.compareTo(o2.desc);
}
});
setByDesc.addAll(setById);

System.out.println(setByDesc);
}

}

class Item implements Comparable {

int id;
String desc;

Item(int id, String desc) {
this.id = id;
this.desc = desc;
}

@Override
public int compareTo(Item o) {
return id - o.id;
}

@Override
public String toString() {
return "Item [id=" + id + ", desc=" + desc + "]";
}

}

4.ProrityQueue：优先级队列（堆）

5.LinkedHashSet/Map：记录插入顺序（LRU）

[java]
public class LRUTest {

public static void main(String[] args) {
Map lruMap = new LinkedHashMap() {
private static final long serialVersionUID = 1L;

@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 3;
}
};
lruMap.put(new Item(1, "111"), 1);
lruMap.put(new Item(2, "222"), 2);
lruMap.put(new Item(3, "333"), 3);

lruMap.put(new Item(4, "444"), 4);
System.out.println(lruMap);

lruMa

Java温故知新 - 集合类 (一)