集合详解
1.1HashSet
HashSet是Set接口的一个子类，主要的特点是：里面不能存放重复元素，而且采用散列的存储方法，所以没有顺序。这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致。
代码实例：HashSetDemo
package edu.sjtu.erplab.collection; import java.util.HashSet;
import java.util.Iterator;
import java.util.Set; public class HashSetDemo { public static void main(String[] args) {
Set<String> set=new HashSet<String>(); set.add("a");
set.add("b");
set.add("c");
set.add("c");
set.add("d"); //使用Iterator输出集合
Iterator<String> iter=set.iterator();
while(iter.hasNext())
{
System.out.print(iter.next()+" ");
}
System.out.println();
//使用For Each输出结合
for(String e:set)
{
System.out.print(e+" ");
}
System.out.println(); //使用toString输出集合
System.out.println(set);
}
}
b c d a
b c d a
[b, c, d, a]
代码实例：SetTest
package edu.sjtu.erplab.collection; import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set; public class SetTest { public static void main(String[] args) throws FileNotFoundException {
Set<String> words=new HashSet<String>(); //通过输入流代开文献
//方法1:这个方法不需要抛出异常
InputStream inStream=SetTest.class.getResourceAsStream("Alice.txt"); //方法2：这个方法需要抛出异常
//InputStream inStream = new FileInputStream("D:\\Documents\\workspace\\JAVAStudy\\src\\edu\\sjtu\\erplab\\collection\\Alice.txt");
Scanner in=new Scanner(inStream);
while(in.hasNext())
{
words.add(in.next());
} Iterator<String> iter=words.iterator(); for(int i=0;i<5;i++)
{
if(iter.hasNext())
System.out.println(iter.next());
} System.out.println(words.size()); }
}
1.2ArrayList
ArrayList是List的子类，它和HashSet想法，允许存放重复元素，因此有序。集合中元素被访问的顺序取决于集合的类型。如果对ArrayList进行访问，迭代器将从索引0开始，每迭代一次，索引值加1。然而，如果访问HashSet中的元素，每个元素将会按照某种随机的次序出现。虽然可以确定在迭代过程中能够遍历到集合中的所有元素，但却无法预知元素被访问的次序。
代码实例：ArrayListDemo
复制代码
package edu.sjtu.erplab.collection; import java.util.ArrayList;
import java.util.Iterator;
import java.util.List; public class ArrayListDemo {
public static void main(String[] args) {
List<String> arrList=new ArrayList<String>(); arrList.add("a");
arrList.add("b");
arrList.add("c");
arrList.add("c");
arrList.add("d"); //使用Iterator输出集合
Iterator<String> iter=arrList.iterator();
while(iter.hasNext())
{
System.out.print(iter.next()+" ");
}
System.out.println();
//使用For Each输出结合
for(String e:arrList)
{
System.out.print(e+" ");
}
System.out.println(); //使用toString输出集合
System.out.println(arrList);
}
}
复制代码
1.3LinkedList
LinkedList 和ArrayList都是List的子类，都是有序，有索引，可重复的。他的特点是一种可以在任何位置进行高效地插入和删除操作的有序序列。
LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用.
LinkedList的构造函数如下:
1. public LinkedList(): ——生成空的链表
2. public LinkedList(Collection col): 复制构造函数
1、获取链表的第一个和最后一个元素
import java.util.LinkedList;
public class LinkedListTest{
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println("链表的第一个元素是 : " + lList.getFirst());
System.out.println("链表最后一个元素是 : " + lList.getLast());
}
}
2、获取链表元素
for (String str: lList) {
System.out.println(str);
}
3、从链表生成子表
List subl = lList.subList(1, 4);
System.out.println(subl);
lst.remove(2);
System.out.println(lst);
System.out.println(lList);
4、添加元素：添加单个元素
如果不指定索引的话，元素将被添加到链表的最后.
public boolean add(Object element)
public boolean add(int index, Object element)
也可以把链表当初栈或者队列来处理:
public boolean addFirst(Object element)
public boolean addLast(Object element)
addLast()方法和不带索引的add()方法实现的效果一样.
import java.util.LinkedList;
public class LinkedListTest{
public static void main(String[] a) {
LinkedList list = new LinkedList();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.addFirst("X");
list.addLast("Z");
System.out.println(list);
}
}
5、删除元素
public Object removeFirst()
public Object removeLast()
import java.util.LinkedList; public class MainClass {
public static void main(String[] a) { LinkedList list = new LinkedList();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.removeFirst();
list.removeLast();
System.out.println(list);
}
}
6、使用链表实现栈效果
import java.util.LinkedList;
public class MainClass {
public static void main(String[] args) {
StackL stack = new StackL();
for (int i = 0; i < 10; i++)
stack.push(i);
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
class StackL {
private LinkedList list = new LinkedList();
public void push(Object v) {
list.addFirst(v);
}
public Object top() {
return list.getFirst();
}
public Object pop() {
return list.removeFirst();
}
}
7、使用链表来实现队列效果
import java.util.LinkedList;
public class MainClass {
public static void main(String[] args) {
Queue queue = new Queue();
for (int i = 0; i < 10; i++)
queue.put(Integer.toString(i));
while (!queue.isEmpty())
System.out.println(queue.get());
}
}
class Queue {
private LinkedList list = new LinkedList();
public void put(Object v) {
list.addFirst(v);
}
public Object get() {
return list.removeLast();
}
public boolean isEmpty() {
return list.isEmpty();
}
}
8、将LinkedList转换成ArrayList
ArrayList<String> arrayList = new ArrayList<String>(linkedList);
for (String s : arrayList) {
System.out.println("s = " + s);
}
9、删掉所有元素：清空LinkedList
lList.clear();
10、删除列表的首位元素
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
//元素在删除的时候，仍然可以获取到元素
Object object = lList.removeFirst();
System.out.println(object + " has been removed");
System.out.println(lList);
object = lList.removeLast();
System.out.println(object + " has been removed");
System.out.println(lList);
}
}
11、根据范围删除列表元素
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
lList.subList(2, 5).clear();
System.out.println(lList);
}
}
12、删除链表的特定元素
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
System.out.println(lList.remove("2"));//删除元素值=2的元素
System.out.println(lList);
Object obj = lList.remove(2); //删除第二个元素
System.out.println(obj + " 已经从链表删除");
System.out.println(lList);
}
}
13、将LinkedList转换为数组，数组长度为0
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> theList = new LinkedList<String>();
theList.add("A");
theList.add("B");
theList.add("C");
theList.add("D");
String[] my = theList.toArray(new String[0]);
for (int i = 0; i < my.length; i++) {
System.out.println(my[i]);
}
}
}
14、将LinkedList转换为数组，数组长度为链表长度
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> theList = new LinkedList<String>();
theList.add("A");
theList.add("B");
theList.add("C");
theList.add("D");
String[] my = theList.toArray(new String[theList.size()]);
for (int i = 0; i < my.length; i++) {
System.out.println(my[i]);
}
}
}
15、将LinkedList转换成ArrayList
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
LinkedList<String> myQueue = new LinkedList<String>();
myQueue.add("A");
myQueue.add("B");
myQueue.add("C");
myQueue.add("D");
List<String> myList = new ArrayList<String>(myQueue);
for (Object theFruit : myList)
System.out.println(theFruit);
}
}
16、实现栈
import java.util.Collections;
import java.util.LinkedList;
public class Main {
public static void main(String[] argv) throws Exception {
LinkedList stack = new LinkedList();
Object object = "";
stack.addFirst(object);
Object o = stack.getFirst();
stack = (LinkedList) Collections.synchronizedList(stack);
}
}
17、实现队列
import java.util.LinkedList;
public class Main {
public static void main(String[] argv) throws Exception {
LinkedList queue = new LinkedList();
Object object = "";
// Add to end of queue
queue.add(object);
// Get head of queue
Object o = queue.removeFirst();
}
}
18 、同步方法
import java.util.Collections;
import java.util.LinkedList;
public class Main {
public static void main(String[] argv) throws Exception {
LinkedList queue = new LinkedList();
Object object = "";
queue.add(object);
Object o = queue.removeFirst();
queue = (LinkedList) Collections.synchronizedList(queue);
}
}
19、查找元素位置
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
lList.add("2");
System.out.println(lList.indexOf("2"));
System.out.println(lList.lastIndexOf("2"));
}
}
20、替换元素
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
System.out.println(lList);
lList.set(3, "Replaced");//使用set方法替换元素，方法的第一个参数是元素索引，后一个是替换值
System.out.println(lList);
}
}
21、链表添加对象
import java.util.LinkedList;
class Address {
private String name;
private String street;
private String city;
private String state;
private String code;
Address(String n, String s, String c, String st, String cd) {
name = n;
street = s;
city = c;
state = st;
code = cd;
}
public String toString() {
return name + " " + street + " " + city + " " + state + " " + code;
}
} class MailList {
public static void main(String args[]) {
LinkedList<Address> ml = new LinkedList<Address>();
ml.add(new Address("A", "11 Ave", "U", "IL", "11111"));
ml.add(new Address("R", "11 Lane", "M", "IL", "22222"));
ml.add(new Address("T", "8 St", "C", "IL", "33333"));
for (Address element : ml)
System.out.println(element + "\n");
}
}
22、确认链表是否存在特定元素
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
if (lList.contains("4")) {
System.out.println("LinkedList contains 4");
} else {
System.out.println("LinkedList does not contain 4");
}
}
}
23、根据链表元素生成对象数组
Object[] objArray = lList.toArray();
for (Object obj: objArray) {
System.out.println(obj);
}
24、链表多线程
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
class PrepareProduction implements Runnable {
private final List<String> queue;
PrepareProduction(List<String> q) {
queue = q;
}
public void run() {
queue.add("1");
queue.add("done");
}
}
class DoProduction implements Runnable {
private final List<String> queue;
DoProduction(List<String> q) {
queue = q;
}
public void run() {
String value = queue.remove(0);
while (!value.equals("*")) {
System.out.println(value);
value = queue.remove(0);
}
}
}
public class Main {
public static void main(String[] args) throws Exception {
List q = Collections.synchronizedList(new LinkedList<String>());
Thread p1 = new Thread(new PrepareProduction(q));
Thread c1 = new Thread(new DoProduction(q));
p1.start();
c1.start();
p1.join();
c1.join();
}
}
25、优先级链表（来自JBOSS）
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException; public class BasicPriorityLinkedList { protected LinkedList[] linkedLists;
protected int priorities;
protected int size; public BasicPriorityLinkedList(int priorities) {
this.priorities = priorities;
initDeques();
}
public void addFirst(Object obj, int priority) {
linkedLists[priority].addFirst(obj);
size++;
}
public void addLast(Object obj, int priority) {
linkedLists[priority].addLast(obj);
size++;
}
public Object removeFirst() {
Object obj = null;
for (int i = priorities - 1; i >= 0; i--) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.removeFirst();
break;
}
}
if (obj != null) {
size--;
}
return obj;
}
public Object removeLast() {
Object obj = null;
for (int i = 0; i < priorities; i++) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.removeLast();
}
if (obj != null) {
break;
}
}
if (obj != null) {
size--;
}
return obj;
} public Object peekFirst() {
Object obj = null;
for (int i = priorities - 1; i >= 0; i--) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.getFirst();
}
if (obj != null) {
break;
}
}
return obj;
} public List getAll() {
List all = new ArrayList();
for (int i = priorities - 1; i >= 0; i--) {
LinkedList deque = linkedLists[i];
all.addAll(deque);
}
return all;
} public void clear() {
initDeques();
} public int size() {
return size;
} public boolean isEmpty() {
return size == 0;
} public ListIterator iterator() {
return new PriorityLinkedListIterator(linkedLists);
} protected void initDeques() {
linkedLists = new LinkedList[priorities];
for (int i = 0; i < priorities; i++) {
linkedLists[i] = new LinkedList();
}
size = 0;
} class PriorityLinkedListIterator implements ListIterator {
private LinkedList[] lists;
private int index;
private ListIterator currentIter;
PriorityLinkedListIterator(LinkedList[] lists) {
this.lists = lists;
index = lists.length - 1;
currentIter = lists[index].listIterator();
} public void add(Object arg0) {
throw new UnsupportedOperationException();
} public boolean hasNext() {
if (currentIter.hasNext()) {
return true;
}
while (index >= 0) {
if (index == 0 || currentIter.hasNext()) {
break;
}
index--;
currentIter = lists[index].listIterator();
}
return currentIter.hasNext();
} public boolean hasPrevious() {
throw new UnsupportedOperationException();
} public Object next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return currentIter.next();
} public int nextIndex() {
throw new UnsupportedOperationException();
} public Object previous() {
throw new UnsupportedOperationException();
} public int previousIndex() {
throw new UnsupportedOperationException();
} public void remove() {
currentIter.remove();
size--;
} public void set(Object obj) {
throw new UnsupportedOperationException();
}
} }
26、生成list的帮助类（来自google）
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Lists {
private Lists() { }
public static <E> ArrayList<E> newArrayList() {
return new ArrayList<E>();
}
public static <E> ArrayList<E> newArrayListWithCapacity(int initialCapacity) {
return new ArrayList<E>(initialCapacity);
}
public static <E> ArrayList<E> newArrayList(E... elements) {
ArrayList<E> set = newArrayList();
Collections.addAll(set, elements);
return set;
}
public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
ArrayList<E> list = newArrayList();
for(E e : elements) {
list.add(e);
}
return list;
}
public static <E> LinkedList<E> newLinkedList() {
return new LinkedList<E>();
}
}
代码实例：LinkedListTest
package edu.sjtu.erplab.collection; import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator; public class LinkedListTest { public static void main(String[] args) { List<String> a=new ArrayList<String>();
a.add("a");
a.add("b");
a.add("c");
System.out.println(a); List<String> b=new ArrayList<String>();
b.add("d");
b.add("e");
b.add("f");
b.add("g");
System.out.println(b); //ListIterator在Iterator基础上添加了add(),previous()和hasPrevious()方法
ListIterator<String> aIter=a.listIterator();
//普通的Iterator只有三个方法，hasNext()，next()和remove()
Iterator<String> bIter=b.iterator(); //b归并入a当中，间隔交叉得插入b中的元素
while(bIter.hasNext())
{
if(aIter.hasNext())
aIter.next();
aIter.add(bIter.next());
}
System.out.println(a); //在b中每隔两个元素删除一个
bIter=b.iterator(); while(bIter.hasNext())
{
bIter.next();
if(bIter.hasNext())
{
bIter.next();//remove跟next是成对出现的，remove总是删除前序
bIter.remove();
}
}
System.out.println(b); //删除a中所有的b中的元素
a.removeAll(b);
System.out.println(a);
}
}
参考之前的一篇博客：Hashmap实现原理
package edu.sjtu.erplab.collection;
import java.util.WeakHashMap;
public class WeekHashMapDemo {
public static void main(String[] args) {
int size = 100;
if (args.length > 0) {
size = Integer.parseInt(args[0]);
}
Key[] keys = new Key[size];
WeakHashMap<Key, Value> whm = new WeakHashMap<Key, Value>();
for (int i = 0; i < size; i++) {
Key k = new Key(Integer.toString(i));
Value v = new Value(Integer.toString(i));
if (i % 3 == 0) {
keys[i] = k;//强引用
}
whm.put(k, v);//所有键值放入WeakHashMap中
}
System.out.println(whm);
System.out.println(whm.size());
System.gc();
try {
// 把处理器的时间让给垃圾回收器进行垃圾回收
Thread.sleep(4000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(whm);
System.out.println(whm.size());
}
}
class Key {
String id;
public Key(String id) {
this.id = id;
}
public String toString() {
return id;
}
public int hashCode() {
return id.hashCode();
}
public boolean equals(Object r) {
return (r instanceof Key) && id.equals(((Key) r).id);
}
public void finalize() {
System.out.println("Finalizing Key " + id);
}
}
class Value {
String id;
public Value(String id) {
this.id = id;
}
public String toString() {
return id;
}
public void finalize() {
System.out.println("Finalizing Value " + id);
}
}
输出结果
{50=50, 54=54, 53=53, 52=52, 51=51, 46=46, 47=47, 44=44, 45=45, 48=48, 49=49, 61=61, 60=60, 63=63, 62=62, 65=65, 64=64, 55=55, 56=56, 57=57, 58=58, 59=59, 76=76, 75=75, 74=74, 73=73, 72=72, 71=71, 70=70, 68=68, 69=69, 66=66, 67=67, 85=85, 84=84, 87=87, 86=86, 81=81, 80=80, 83=83, 82=82, 77=77, 78=78, 79=79, 89=89, 88=88, 10=10, 90=90, 91=91, 92=92, 93=93, 94=94, 95=95, 96=96, 97=97, 98=98, 99=99, 20=20, 21=21, 12=12, 11=11, 14=14, 13=13, 16=16, 15=15, 18=18, 17=17, 19=19, 8=8, 9=9, 31=31, 4=4, 32=32, 5=5, 6=6, 30=30, 7=7, 0=0, 1=1, 2=2, 3=3, 29=29, 28=28, 27=27, 26=26, 25=25, 24=24, 23=23, 22=22, 40=40, 41=41, 42=42, 43=43, 38=38, 37=37, 39=39, 34=34, 33=33, 36=36, 35=35}
Finalizing Key 98
Finalizing Key 97
Finalizing Key 95
Finalizing Key 94
Finalizing Key 92
Finalizing Key 91
Finalizing Key 89
Finalizing Key 88
Finalizing Key 86
Finalizing Key 85
Finalizing Key 83
Finalizing Key 82
Finalizing Key 80
Finalizing Key 79
Finalizing Key 77
Finalizing Key 76
Finalizing Key 74
Finalizing Key 73
Finalizing Key 71
Finalizing Key 70
Finalizing Key 68
Finalizing Key 67
Finalizing Key 65
Finalizing Key 64
Finalizing Key 62
Finalizing Key 61
Finalizing Key 59
Finalizing Key 58
Finalizing Key 56
Finalizing Key 55
Finalizing Key 53
Finalizing Key 52
Finalizing Key 50
Finalizing Key 49
Finalizing Key 47
Finalizing Key 46
Finalizing Key 44
Finalizing Key 43
Finalizing Key 41
Finalizing Key 40
Finalizing Key 38
Finalizing Key 37
Finalizing Key 35
Finalizing Key 34
Finalizing Key 32
Finalizing Key 31
Finalizing Key 29
Finalizing Key 28
Finalizing Key 26
Finalizing Key 25
Finalizing Key 23
Finalizing Key 22
Finalizing Key 20
Finalizing Key 19
Finalizing Key 17
Finalizing Key 16
Finalizing Key 14
Finalizing Key 13
Finalizing Key 11
Finalizing Key 10
Finalizing Key 8
Finalizing Key 7
Finalizing Key 5
Finalizing Key 4
Finalizing Key 2
Finalizing Key 1
{54=54, 51=51, 45=45, 48=48, 60=60, 63=63, 57=57, 75=75, 72=72, 69=69, 66=66, 84=84, 87=87, 81=81, 78=78, 90=90, 93=93, 96=96, 99=99, 21=21, 12=12, 15=15, 18=18, 9=9, 6=6, 30=30, 0=0, 3=3, 27=27, 24=24, 42=42, 39=39, 33=33, 36=36}