# Data Structure & Design ## HashMap HashMap 的两种遍历方式\ 第一种 ```java 　　Map map = new HashMap(); 　　Iterator iter = map.entrySet().iterator(); 　　while (iter.hasNext()) { 　　Map.Entry entry = (Map.Entry) iter.next(); 　　Object key = entry.getKey(); 　　Object val = entry.getValue(); 　　} ``` 效率高,以后一定要使用此种方式！ 第二种 ```java 　　Map map = new HashMap(); 　　Iterator iter = map.keySet().iterator(); 　　while (iter.hasNext()) { 　　Object key = iter.next(); 　　Object val = map.get(key); 　　} ``` 效率低,以后尽量少使用！ Map Traverse: ```java Map map = new HashMap(); // Keys for(String str : map.keySet()){ Integer value = map.get(str); } // Map.Entry for (Map.Entry e : map.entrySet()) System.out.println(e.getKey() + ": " + e.getValue()); ``` The Collection view methods allow a **Map** to be viewed as a Collection in these three ways: * **keySet** — the Set of keys contained in the **Map**. * **values** — The Collection of values contained in the **Map**. This Collection is not a Set, because multiple keys can map to the same value. * **entrySet** — the Set of key-value pairs contained in the **Map**. The Map interface provides a small nested interface called **Map.Entry**, the type of the elements in this Set. **Differences Between HashMap Vs HashSet In Java** ![](/files/-M63nRpHfDhAKuL7vvhK) ## Union Find (Disjoint Set) **并查集**: 一种用来解决集合查询合并的数据结构 支持O(1) find / O(1) union ### 并查集可以干什么? 1. 判断在不在同一个集合中。 * find 操作 2. 关于集合合并 * union 操作 ### 并查集的操作 1. 查询 Find (递归? 非递归?) 模板代码 ```java HashMap father = new HashMap(); int find(int x) { int parent = x; while (parent ! = father.get(parent)) { parent = father.get(parent); } return parent; } ``` 1. 合并 Union 老大哥之间合并\ 跟小弟没关系 ```java HashMap father = new HashMap(); void union(int x, int y) { int fa_x = find(x); int fa_y = find(y); if (fa_x != fa_y) { father.put(fa_x, fa_y); } } ``` ### 并查集完整模板 ```java class UnionFind { UnionFind() {} HashMap father = new HashMap(); int find(int x) { int parent = x; while (parent ! = father.get(parent)) { parent = father.get(parent); } return parent; } void union(int x, int y) { int fa_x = find(x); int fa_y = find(y); if (fa_x != fa_y) { father.put(fa_x, fa_y); } } } ``` ## Trie ## Linked List vs ArrayList `LinkedList` and `ArrayList` are two different implementations of the List interface. `LinkedList` implements it with a doubly-linked list. `ArrayList` implements it with a dynamically re-sizing array. `LinkedList` allows for **constant-time insertions or removals** using iterators, but only sequential access of elements. `ArrayList`, on the other hand, allow **fast random read access**, so you can grab any element in constant time. * [When to use LinkedList over ArrayList?](http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist) * [ArrayList vs LinkedList in Java](https://www.geeksforgeeks.org/arraylist-vs-linkedlist-java/) * [Difference between ArrayList and LinkedList ](https://www.javatpoint.com/difference-between-arraylist-and-linkedlist) | ArrayList | LinkedList | | ------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------- | | 1) ArrayList internally uses a **dynamic array** to store the elements. | LinkedList internally uses a **doubly linked list** to store the elements. | | 2) Manipulation with ArrayList is **slow** because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory. | Manipulation with LinkedList is **faster** than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory. | | 3) An ArrayList class can **act as a list** only because it implements List only. | LinkedList class can **act as a list and queue** both because it implements List and Deque interfaces. | | 4) ArrayList is **better for storing and accessing** data. | LinkedList is **better for manipulating** data. | ## Heap Heap A min-heap is a binary tree such that * the data contained in each node is less than (or equal to) the data in that node’s children. * the binary tree is complete A max-heap is a binary tree such that * the data contained in each node is greater than (or equal to) the data in that node’s children. * the binary tree is complete **Sift Up** ```java void siftup(int id) { while (parent(id) > -1) { int parentId = parent(id); if (comparesmall(heap.get(parentId), heap.get(id)) == true) { break; } else { swap(id, parentId); } id = parentId; } } ``` **Sift Down** ```java void siftdown(int id) { while (lson(id) < heap.size()) { int leftId = lson(id); int rightId = rson(id); int son; if (rightId >= heap.size() || (comparesmall(heap.get(leftId), heap.get(rightId)) == true)) { son = leftId; } else { son = rightId; } if (comparesmall(heap.get(id), heap.get(son)) == true) { break; } else { swap(id, son); } id = son; } } ``` ### Resources * [bubkoo.com 常见排序算法 - 堆排序 (Heap Sort)](http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/) * [Data Structures Heap, Heap Sort & Priority Queue](https://www.cs.bgu.ac.il/~ds122/wiki.files/Presentation09.pdf) * [Priority Queue Implementation](http://algorithms.tutorialhorizon.com/priority-queue-implementation/) * [CMU: Trees Heaps & Other Trees](https://www.cs.cmu.edu/~tcortina/15-121sp10/Unit06B.pdf) ## Stack ## Queue ## ArrayDeque / Deque **ArrayDeque** * It’s **not** **thread**-**safe** * **Null** elements are **not** **accepted** * Works significantly **faster** than the synchronized **Stack** * Is a **faster** **queue** than LinkedList due to the better locality of reference * Most operations have **amortized** **constant** **time** complexity * An Iterator returned by an ArrayDeque is fail-fast * ArrayDeque **automatically** **doubles** the **size** of an array when head and tail pointer meets each other while adding an element An **ArrayDeque** implementation can be used as a **Stack** (Last-In-First-Out) or a **Queue**(First-In-First-Out). **In Java Docs for ArrayDeque:** > This class is likely to be faster than [`Stack`](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html) when used as a stack, and faster than [`LinkedList`](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html) when used as a queue. #### **Deque** **Interface**: ## Arrays **java.util.Arrays** #### Methods 1.`static List asList(T… a)`: This method returns a fixed-size list backed by the specified array. ```java // Java program to demonstrate // Array.asList() method import java.util.Arrays; public class Main { public static void main(String[] args) { // Get the Array int intArr[] = { 10, 20, 15, 22, 35 }; // To convert the elements as List System.out.println("Integer Array as List: " + Arrays.asList(intArr)); } } ``` 1. `static int binarySearch(elementToBeSearched)`: These methods searches for the specified element in the array with the help of Binary Search algorithm. ```java // Java program to demonstrate // Array.binarySearch() method import java.util.Arrays; public class Main { public static void main(String[] args) { // Get the Array int intArr[] = { 10, 20, 15, 22, 35 }; Arrays.sort(intArr); int intKey = 22; System.out.println(intKey + " found at index = " + Arrays .binarySearch(intArr, intKey)); } } ``` 1. `copyOf(originalArray, newLength)`: This method copies the specified array, truncating or padding with the default value (if necessary) so the copy has the specified length. ```java // Java program to demonstrate // Array.copyOf() method import java.util.Arrays; public class Main { public static void main(String[] args) { // Get the Array int intArr[] = { 10, 20, 15, 22, 35 }; // To print the elements in one line System.out.println("Integer Array: " + Arrays.toString(intArr)); System.out.println("\nNew Arrays by copyOf:\n"); System.out.println("Integer Array: " + Arrays.toString( Arrays.copyOf(intArr, 10))); } } ``` 1. `fill(originalArray, fillValue)`: This method assigns this fillValue to each index of this array. ```java // Java program to demonstrate // Array.fill() method import java.util.Arrays; public class Main { public static void main(String[] args) { // Get the Arrays int intArr[] = { 10, 20, 15, 22, 35 }; int intKey = 22; Arrays.fill(intArr, intKey); // To fill the arrays System.out.println("Integer Array on filling: " + Arrays.toString(intArr)); } } ``` ## TreeSet / TreeMap ### TreeMap #### Default Sorting in TreeMap ```java @Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() { TreeMap map = new TreeMap<>(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); } ``` #### Custom Sorting in TreeMap ```java public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() { TreeMap map = new TreeMap<>(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); } ``` ### TreeSet **In this implementation, objects are sorted and stored in ascending order according to their natural order**. The \_TreeSet \_uses a self-balancing binary search tree, more specifically [a \_Red-Black \_tree](https://en.wikipedia.org/wiki/Red–black_tree). Operations like `add`, `remove` and `contains` (search) take `O(log n)` time while operations like printing n elements in sorted order require `O(n)` time. ```java Set treeSet = new TreeSet<>(); ``` Comparator ```java Set treeSet = new TreeSet<>(Comparator.comparing(String::length)); ``` Although **TreeSet** isn’t thread-safe, it can be synchronized externally using the `Collections.synchronizedSet()` wrapper: ```java Set syncTreeSet = Collections.synchronizedSet(treeSet); ``` TreeSet `add()` TreeSet `contains()` TreeSet `remove()` #### TreeSet & TreeMap The **TreeSet** internally depends on a backing **NavigableMap** which gets initialized with an instance of **TreeMap** when an instance of the **TreeSet** is created: ```java public TreeSet() { this(new TreeMap()); } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/data_structure.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.