# Data Structure & Design

## HashMap

<https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html>

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<String, Integer> map = new HashMap();
// Keys
for(String str : map.keySet()){
    Integer value = map.get(str);
}

// Map.Entry
for (Map.Entry<K, V> 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**.&#x20;
* **values** — The Collection of values contained in the **Map**. This Collection is not a Set, because multiple keys can map to the same value.&#x20;
* **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**

<https://javaconceptoftheday.com/differences-between-hashmap-vs-hashset-in-java/>

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2Fbcc42c254edfcb83cb730b91cac0f56efe2a1ad3.png?generation=1588144785785204\&alt=media)

## Union Find (Disjoint Set)

**并查集**: 一种用来解决集合查询合并的数据结构 支持O(1) find / O(1) union

### 并查集可以干什么?

1. 判断在不在同一个集合中。
   * find 操作
2. 关于集合合并
   * union 操作

### 并查集的操作

1. 查询 Find (递归? 非递归?)

模板代码

```java
HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

int find(int x) {
    int parent = x;
    while (parent ! = father.get(parent)) {
        parent = father.get(parent);
    }
    return parent;
}
```

1. 合并 Union

老大哥之间合并\
跟小弟没关系

```java
HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

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<Integer, Integer> father = new HashMap<Integer, Integer>();
    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<E>` allows for **constant-time insertions or removals** using iterators, but only sequential access of elements.

`ArrayList<E>`, 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/)&#x20;
* [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**&#x20;
* **Null** elements are **not** **accepted**&#x20;
* Works significantly **faster** than the synchronized **Stack**&#x20;
* Is a **faster** **queue** than LinkedList due to the better locality of reference&#x20;
* Most operations have **amortized** **constant** **time** complexity&#x20;
* An Iterator returned by an ArrayDeque is fail-fast&#x20;
* 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**:

<https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html>

## Arrays

**java.util.Arrays**

<https://www.geeksforgeeks.org/array-class-in-java/>

#### 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

<https://www.baeldung.com/java-treemap>

#### Default Sorting in TreeMap

```java
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
    TreeMap<Integer, String> 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<Integer, String> 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

<https://www.baeldung.com/java-tree-set>

**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%E2%80%93black_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<String> treeSet = new TreeSet<>();
```

Comparator

```java
Set<String> 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<String> 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<E,Object>());
}
```