Stack ArrayList LinkedList HashMap HashSet Queue
添加元素 push add, addAll add, addAll put add offer
删除元素 pop remove remove remove remove poll
查看第一个元素 peek peek
查看指定元素 get get get
修改元素 set set replace,put
大小 size size size size size size
判断元素是否存在 search contains contains containsKey,containsValue contains
是否为空 empty isEmpty isEmpty isEmpty
线程安全 是 否 否 否 否

初始化：

1
2
3
4
5
6
7
Stack<Object> var=new Stack<>();
ArrayList<Object> var=new ArrayList<>();
LinkedList<Object> var=new LinkedList<>();
HashSet<Object> var=new HashSet<>();

Queue<Object> var=new LinkedList<>();
HashMap<Key,Value> var=new HashMap<>();

Stack

1
search(Object)//查找元素所在位置，栈顶为1，不存在则返回-1

List

ArrayList

1
2
3
4
5
6
7
add(value)//末尾添加元素
add(index,value)//指定位置添加元素
addAll(index,collection)//添加集合的所有元素到index（可省略）之后
remove(index)//删除元素,参数可以是元素，也可以是索引
get(index)//访问元素
set(index,value)//修改元素
size()//大小

LinkedList

同ArrayList

Vector

线程安全的ArrayList

Map

HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
HashMap<Key, Value> Sites = new HashMap<Key, Value>();
Sites.put(Key,Value);//添加元素
Sites.get(Key);//获取Key对应的Value
Sites.remove(Key);//删除元素
Sites.clear();//删除所有键值对
Sites.size();//计算元素数量
Sites.getOrDefault(Key,defaultvalue);//如果map中有key，就返回他的value，没有key，就返回defaultvalue
//遍历
for (Integer i : Sites.keySet()) {
    System.out.println("key: " + i + " value: " + Sites.get(i));
}

for(String value: Sites.values()) {
    System.out.print(value + ", ");
}

LinkedHashMap

  • HashMap+双向链表
  • 头部是最久远的节点，尾部是最新的节点
  • 布尔变量accessOrder决定get和put函数调用后是否把节点放在尾部，具体实现在afterNodeAccess函数里
1
2
3
4
//按顺序遍历
for(Entry<String,Integer> entry:seqMap.entrySet()){
	System.out.println(entry.getKey()+" "+entry.getValue());
}

支持两种顺序插入顺序 、 访问顺序

  1. 插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序
  2. 访问顺序：所谓访问指的是get/put操作，对一个键执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
1
2
//设置按照访问顺序排序，accessOrder设为true
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);

实现LRU:最久没访问的放在队头，最近访问的放在队尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

HashTable

线程安全，弃用了

TreeMap

默认按照key排序

1
2
3
4
5
6
7
8
9
10
11
12
TreeMap<Integer, String> treeMap = new TreeMap<>();//创建
TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());//指定排序方式，倒序
//基本操作和hashmap一样

treeMap.firstKey();//返回该TreeMap的第一个（最小的）映射的key
treeMap.lastKey();//返回该TreeMap的最后一个（最大的）映射的key
treeMap.subMap(fromKey,toKey);//返回该TreeMap中指定范围的映射集合（大于等于fromKey，小于toKey）

//迭代
for (Map.Entry entry : treeMap.entrySet()) {
      System.out.println(entry);
}

Set

HashSet

源码实现是HashMap的一个实例

1
2
3
4
5
HashSet<String> sites = new HashSet<String>();
sites.add("Google");//添加元素
sites.contains("Taobao");//是否包含元素
sites.remove("Taobao");//删除元素
sites.size();//大小

LinkedHashSet

源码实现是LinkedHashMap的一个实例

TreeSet

源码实现是TreeMap的一个实例

有序唯一

Queue

PriorityQueue

默认小顶堆。myPQ第一个是最小的那个数。

1
2
3
Queue<Integer> myPQ = new PriorityQueue<>();
myPQ.offer(1);//插入元素
myPQ.poll();//取出队列头元素

创建自定义优先级：创建一个Comparator对象并重写compare方法，返回负数表示前者更优先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
class Untitled {
	public static void main(String[] args) {
		Queue<Integer> myPQ = new PriorityQueue<>(newCp);
		myPQ.offer(3);
		myPQ.offer(2);
		myPQ.offer(1);
		myPQ.offer(4);
		System.out.println(myPQ.poll());
		System.out.println(myPQ.poll());
		System.out.println(myPQ.poll());
		System.out.println(myPQ.poll());
	}
	public static Comparator<Integer> newCp = new Comparator<Integer>(){
        @Override
        public int compare(Integer c1, Integer c2) {
            return (int)(c2-c1);
        }
    };
	   
}

Deque

双端队列，更多参考这里

1
2
3
4
5
6
7
8
9
Deque<Integer> path=new LinkedList<>();
Deque<Integer> path=new ArrayDeque<>();

offerFirst(E e);//在队列前面添加元素，并返回是否添加成功
offerLast(E e);//在队列末尾添加元素，并返回是否添加成功
pollFirst();//删除第一个元素，并返回删除元素的值
pollLast();//删除最后一个元素，并返回删除元素的值
getFirst();//获取第一个元素
getLast();//获取最后一个元素

Collections

reverse

1
Collections.reverse();//反转

sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//重写sorts函数的比较函数
Comparator<Integer> cmp=new Comparator<Integer>(){
    @Override
    public int compare(Integer a, Integer b){
        return b-a;
    }
};
//返回值为负代表当前对象位置要排在前

//对于String
Comparator<String> myCmp=new Comparator<String>(){
        @Override
        public int compare(String a,String b){
            return a.compareTo(b);
    }
};
//compareTo函数，当前值小于参数值，返回负数

集合转换

数组和List

1

Queue和List

1
2
3
Deque<Integer> path=new ArrayDeque<>();
//queue->list,直接放到构造参数里
ArrayList<Integer> tmp=new ArrayList<>(path);