Data Structure & Design

HashMap

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

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

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

Union Find (Disjoint Set)

并查集: 一种用来解决集合查询合并的数据结构 支持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);
        }
    }
}

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.

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

Resources

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 when used as a stack, and faster than LinkedList 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 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)); 
    } 
}

TreeSet / TreeMap

TreeMap

https://www.baeldung.com/java-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

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.

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

Last updated