# Data Structure & Design

## HashMap

HashMap 的两种遍历方式 第一种
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();
}

Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}

Map Traverse:
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.
• 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 ## Union Find (Disjoint Set)

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

### 并查集的操作

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

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. 1.
合并 Union

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);
}
}

### 并查集完整模板

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

`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.
 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
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
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;
}
}

## ArrayDeque / Deque

ArrayDeque
• 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` when used as a stack, and faster than `LinkedList` when used as a queue.

## Arrays

java.util.Arrays

#### Methods

1.`static List asList(T… a)`: This method returns a fixed-size list backed by the specified array.
// 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. 1.
`static int binarySearch(elementToBeSearched)`: These methods searches for the specified element in the array with the help of Binary Search algorithm.
// 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. 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 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. 1.
`fill(originalArray, fillValue)`: This method assigns this fillValue to each index of this array.
// 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

@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

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

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.
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.
Set<String> treeSet = new TreeSet<>();
Comparator
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:
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:
public TreeSet() {
this(new TreeMap<E,Object>());
}