常用数据结构：大小堆栈有序Map

大小堆：PriorityQueue 优先队列

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); // 默认小顶堆，默认初始容量11

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
    @Override
    public int compare(Integer var1, Integer var2){
        return var2 - var1;
    }
}); // 大顶堆

或者jdk1.8起用reverseOrder
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Comparator.reverseOrder());  // 大顶堆

Comparator升降序：以int为例，返回var1 - var2视作默认值，就是从小到大(ascend升序)；
返回var2 - var1视作反序值，就是从大到小(descend降序)
Comparable的compareTo方法：大于被比较数时返回1，小于时返回-1，等于时返回0
所以如果Comparator中参数实现了compareTo，return var1.compareTo(var2)即升序，return var2.compareTo(var1)为降序

public final class Integer extends Number implements Comparable<Integer> {
    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }
    public static int compare(int x, int y) {
            return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }
}

Queue

Queue接口定义了一系列方法，几个常见的实现是

Queue
—— AbstractQueue
———— PriorityQueue
—— BlockingQueue 阻塞队列
———— BlockingDeque
—————— BlockingDeque
—— Deque 双端队列
———— BlockingDeque
———— LinkedList

其中

———— BlockingDeque
———— Deque
—————— LinkedBlockingDeque

———— PriorityQueue
———— BlockingDeque
—————— PriorityBlockingQueue

Queue中定义的方法如下：

public interface Queue<E> extends Collection<E> {
    boolean add(E var1);
    boolean offer(E var1);
    E remove();
    E poll();
    E element();
    E peek();
}

add 添加一个元素添加成功返回true，如果队列已满，则抛出IllegalStateException
offer 添加一个元素添加成功返回true，如果队列已满，则返回false
remove 返回并删除队头元素非空则返回队头元素，空则抛出NoSuchElementException
element 返回队头元素非空则返回队头元素，空则抛出NoSuchElementException
poll 返回并删除队头元素非空则返回队头元素，空则返回null
peak 返回队头元素非空则返回队头元素，空则返回null

添加方法是添加到队尾

举例，AbstractQueue中add的实现如下：

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

BlockingQueue中，多出的常用方法：

put 添加一个元素 void，如无空间，阻塞等待到有空间时再执行，中断时抛InterruptedException
take 返回并删除队头元素如无元素，阻塞等待直到有元素可取时再执行，中断时抛InterruptedException

Deque中，多出的常用方法：

所有方法都加上First和Last尾缀，比如addFirst、addLast

举例，LinkedBlockingDeque中add的实现如下：

public boolean add(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
    if (!offerLast(e))
        throw new IllegalStateException("Deque full");
}

public boolean offerLast(E e) {
    if (e == null) throw new NullPointerException();
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        return linkLast(node);
    } finally {
        lock.unlock();
    }
}

栈：Stack

Stack 栈 extends Vector extends AbstractList implements List

后进先出，常用方法：

push 添加一个元素，调的就是addElement
addElement 添加一个元素
pop 弹出栈顶元素，调的就是removeElementAt(len - 1)，空栈会报EmptyStackException
peek 返回栈顶元素，调的就是elementAt(len - 1)，空栈会报EmptyStackException(这是和Queue的区别)
search 返回从栈顶开始数，该元素的位置，从1开始计数，如果无此元素返回-1

Vector是线程安全的，所以Stack也是线程安全的

TreeMap 有序映射 TreeSet 有序集合

TreeMap extends AbstractSet implements NavigableSet extends SortedMap extends Map，

基于红黑树实现
构造参数传入Comparator，默认对key从小到大排列(ascend，升序)，可用Comparator.reverseOrder()逆序
HashMap寻址时间是O(1)，TreeMap寻址时间复杂度是O(log n)

TreeSet extends AbstractSet implements NavigableSet extends SortedSet extends Set

基于TreeMap实现
构造参数传入Comparator，默认对值从小到大排列，可用Comparator.reverseOrder()逆序

注意和LinkedHashMap区别，LinkedHashMap是按put时序排序的

Collection及Iterable

Collection extends Iterable Iterable的iterator()方法返回一个Iterator

public interface Iterable<T> {
    Iterator<T> iterator();
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
}

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");  // 子类实现，如内部类ArrayList.Itr
    }
}

循环里remove操作需慎重

foreach循环里调remove会报ConcurrentModificationException，报错在checkForComodification，因为modCount状态不正确
fori循环不会报错，但是fori每个元素都调remove时，会发现还剩最后一个元素

其他常用操作

Array与List

// 快速构造List，但返回的是Arrays的静态内部类ArrayList，大小已确定，不支持增删操作
List<Integer> arrList = Arrays.asList(3, 1, 2);

// 快速初始化List，需要引入espresso，见的不多
List<Integer> arrList = ImmutableList.of(3, 1, 2);

// 快速初始化List，匿名内部类，此时不能省略右部<>内类型
ArrayList<Integer> arrList = new ArrayList<Integer>(){
    {add(3);}
};

// array转ArrayList，但是int[]强转不了ArrayList<Integer>
Integer[] arr = new Integer[]{3， 1， 2};
ArrayList<Integer> arrayList = new ArrayList<>(Arrays.asList(arr));

// ArrayList转array，接收一个T[]参数，随便new一个数组就行
ArrayList<Integer> arrayList = new ArrayList<>();
Integer[] arr = arrayList.toArray(new Integer[]{});

Arrays.sort(T[], Comparator)，用的是归并和双轴快排

Collections.sort(List list, Comparator)，用归并或Timsort，可通过System.setProperty设置，Timsort是一种归并+插入混合排序

HashMap

hash算法：元素的key在Node<K,V>[] table表中下标地址为(n - 1) & hash， hash算法：(h = key.hashCode()) ^ (h »> 16) 每次扩容成2n

ConcurrentHashMap

是否接受null：

HashMap可以用null作为key和value，但是Hashtable的kv都不能为null，会报空指针；
TreeMap不能存null key，可以存null值
HashSet可以存null，注意使用时的拆箱
List类可以重复存放null

HashMap遍历：

// 只需遍历key或者value：
map.keySet()
map.values()
// 遍历KV：
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println("key = " + entry.getKey() + " value = " + entry.getValue());
}
// 有删除操作时用迭代器：
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
    Map.Entry<Integer, Integer> entry = entries.next();
    System.out.println("key = " + entry.getKey() + " value = " + entry.getValue());
}
// lambda表达式：
map.forEach((k, v) -> System.out.println("key: " + k + " value:" + v));

线程安全相关

通过synchronized关键字给方法加上内置锁来实现线程安全的常见类：

方法级别：Vector, Stack, HashTable, StringBuffer
Object级别：Timer, TimeTask, Collections.synchronizedCollection 原子类Atomic，基于UNSAFE/CAS实现
AtomicInteger, AtomicLong, AtomicIntegerArray, AtomicReference等基于ReentrantLock
BlockingQueue, BlockingDeque, ThreadPoolExecutor, CopyOnWriteArrayList, CopyOnWriteArraySet 分段锁
ConcurrentHashMap, ConcurrentSkipListMap, ConcurrentSkipListSet

https://blog.csdn.net/fdl123456/article/details/103884164

Java算法常用的数据结构：堆、栈、有序映射(更新中)

java基础、算法基础