Summary

Data Structure

1.Linear Data Structure

(1) Queue : O(1) offer/ O(1) poll /O(1) peek ==>BFS

(2) Stack : O(1) push / O(1) pop /O(1) peek ==>Non-recursive DFS

(3) Hash : O(1) Insert / O(1) Find / O(1) Delete ==> Hash Table / Hash Map / Hash Set 的区别是什么？

There are several differences between HashMap and Hashtable in Java:

1. Hashtableissynchronized, whereasHashMapis not. This makesHashMapbetter for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.

2. Hashtabledoes not allownullkeys or values.HashMapallows onenullkey and any number ofnullvalues.

3. One of HashMap's subclasses isLinkedHashMap,(LRU Cache) so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out theHashMapfor aLinkedHashMap. This wouldn't be as easy if you were usingHashtable.

Since synchronization is not an issue for you, I'd recommendHashMap. If synchronization becomes an issue, you may also look atConcurrentHashMaporCollections.synchronizedMap(map).

Note: What is java thread synchronized-- When we start two or more threads within a program, there may be a situation when multiple threads try to access the same resource and finally they can produce unforeseen result due to concurrency issues. For example, if multiple threads try to write within a same file then they may corrupt the data because one of the threads can override data or while one thread is opening the same file at the same time another thread might be closing the same file.

So there is a need to synchronize the action of multiple threads and make sure that only one thread can access the resource at a given point in time. This is implemented using a concept called monitors. Each object in Java is associated with a monitor, which a thread can lock or unlock. Only one thread at a time may hold a lock on a monitor.

Java programming language provides a very handy way of creating threads and synchronizing their task by using synchronized blocks. You keep shared resources within this block. Following is the general form of the synchronized statement

2. Tree Data Structure

(1) Heap : O(log N) Add / O(log N) Remove / O(1) Min or Max

基本操作：130.

(2) Priority Queue

如果不提供Comparator的话，优先队列中元素默认按自然顺序排列，也就是数字默认是小的在队列头，字符串则按字典序排列。

如果想实现按照自己的意愿进行优先级排列的队列的话，需要实现Comparator接口。

实际上是一个堆（不指定Comparator时默认为最小堆） 队列既可以根据元素的自然顺序来排序，也可以根据 Comparator来设置排序规则。 队列的头是按指定排序方式的最小元素。如果多个元素都是最小值，则头是其中一个元素。 新建对象的时候可以指定一个初始容量，其容量会自动增加。

注意1：该队列是用数组实现，但是数组大小可以动态增加，容量无限。

注意2：队列的实现不是同步的。不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue实例。保证线程安全可以使用PriorityBlockingQueue 类。

注意3：不允许使用 null 元素。

注意4：插入方法（offer()、poll()、remove() 、add() 方法）时间复杂度为O(log(n)) ； remove(Object) 和 contains(Object) 时间复杂度为O(n)； 检索方法（peek、element 和 size）时间复杂度为常量。

注意5：方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。（原因可参考PriorityQueue的内部实现） 如果需要按顺序遍历，可用Arrays.sort(pq.toArray())。

注意6：可以在构造函数中指定如何排序。如： PriorityQueue() 使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。 PriorityQueue(int initialCapacity) 使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。 PriorityQueue(int initialCapacity, Comparator<? super E> comparator) 使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。

注意7：此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。

PriorityQueue对元素采用的是堆排序，头是按指定排序方式的最小元素。堆排序只能保证根是最大（最小），整个堆并不是有序的。 方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的。

示例：自己指定比较器进行排序(Descending)

Queue<Integer> pq = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
                    public int compare(Integer i1, Integer i2) {
                        return i2 -i1;
                    }
                });
                
//Another one:
Queue<Integer> pq = new PriorityQueue<Integer>((a,b) -> {return a-b;});

HashTable 工作原理：

Hashtable中有一个内部类Entry，用来保存单元数据，我们用来构建哈希表的每一个数据是Entry的一个实例。假设我们保存下面一组数据，第一列作为key,第二列作为value。

Hashtable内部用一个Entry数组table，来保存所有的数据。

当我们插入一个新的Entry对象时，即用Hashtable的put(key, value)方法。 在put方法里： 计算key的hash值 计算index值，作为数组table的下标，即table[index] 哈希表中根据key的索引值index，创建了多个bucket，所有index值一样的Entry对象，构造成一个链接表存放在同一个bucket里。既然是一个链接表，根据数据结构知识，自然我们的Entry对象需要有一个指向下一个对象的指针，即Entry对象需要有这些属性：key，value，next。

put方法的整个流程为：

1.判断value是否为空，为空则抛出异常；

2.计算key的hash值，并根据hash值获得key在table数组中的位置index，如果table[index]元素不为空，则进行迭代，如果遇到相同的key，则直接替换，并返回旧value；

3.否则，我们可以将其插入到table[index]位置。

通过一个实际的例子来演示一下这个过程：

假设我们现在Hashtable的容量为5，已经存在了(5,5)，(13,13)，(16,16)，(17,17)，(21,21)这5个键值对，目前他们在Hashtable中的位置如下：

现在，我们插入一个新的键值对，put(16,22)，假设key=16的索引为1.但现在索引1的位置有两个Entry了，所以程序会对链表进行迭代。迭代的过程中，发现其中有一个Entry的key和我们要插入的键值对的key相同，所以现在会做的工作就是将newValue=22替换oldValue=16，然后返回oldValue=16.

然后我们现在再插入一个，put(33,33)，key=33的索引为3，并且在链表中也不存在key=33的Entry，所以将该节点插入链表的第一个位置。

Hashtable与HashMap的简单比较

1.HashTable基于Dictionary类，而HashMap是基于AbstractMap。Dictionary是任何可将键映射到相应值的类的抽象父类，而AbstractMap是基于Map接口的实现，它以最大限度地减少实现此接口所需的工作。

2.HashMap的key和value都允许为null，而Hashtable的key和value都不允许为null。HashMap遇到key为null的时候，调用putForNullKey方法进行处理，而对value没有处理；Hashtable遇到null，直接返回NullPointerException。

3.Hashtable方法是同步，而HashMap则不是。我们可以看一下源码，Hashtable中的几乎所有的public的方法都是synchronized的，而有些方法也是在内部通过synchronized代码块来实现。所以有人一般都建议如果是涉及到多线程同步时采用HashTable，没有涉及就采用HashMap，但是在Collections类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的Map对象，并把它作为一个封装的对象来返回。

https://blog.csdn.net/Alexshi5/article/details/79659631