Data Structure & Design
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

并查集: 一种用来解决集合查询合并的数据结构 支持O(1) find / O(1) union
- 1.判断在不在同一个集合中。
- find 操作
- 2.关于集合合并
- union 操作
- 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.合并 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);
}
}
}
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
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
- 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 thanStack
when used as a stack, and faster thanLinkedList
when used as a queue.
java.util.Arrays
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.
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.
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.
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));
}
}
@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());
}
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());
}
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()
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>());
}
Last modified 2yr ago