精于心，简于形
- O(1) access/modify via index
- O(N) iteration (memory friendly)
- O(N) search for a particular value in an unsorted array
- O(logN) search for a value in a sorted array
code
int[] myArray = new int[3];
for (int i = 0; i < myArray.length; i++) {
myArray[i] = i;
}
System.out.println("Items in array:");
for (int i: myArray) {
System.out.println(i + " ");
}
ArrayList底层是用数组实现的，随着元素添加，其大小是动态增大的；在内存中是连续存放的；如果在集合末尾添加或删除元素，所用时间是一致的，如果在列表中间添加或删除元素，所用时间会大大增加。通过索引查找元素速度很快。适合场合：查询比较多的场景
- O(1) access/modify via index
- O(1) Append
- O(N) iteration (memory friendly)
- O(N) search for a particular value in an unsorted List
ArrayList myArrayList = new ArrayList();
myArrayList.add('a');
myArrayList.add('b');
myArrayList.add('c');
System.out.println("Second char is: " + myArrayList.get(1));
System.out.println("Chars in list:");
for (int i = 0; i < myArrayList.size(); i++) {
System.out.println(myArrayList.get(i));
}
Vector与ArrayList基本是一致的，不同的是Vector是线程安全的，会在可能出现线程安全的方法前面加上synchronized关键字。 Vector特点是随机访问速度快，插入和移除性能较差。该类可以使用Collections.synchronizedList替换掉。
- O(N) access/modify via index
- O(1) Adding to front
- O(N) iteration
- O(N) search for a particular value in an unsorted List
code
LinkedList linkedList = new LinkedList();
//set value
for (int i=0; i<3; i++) {
linkedList.add(i + "");
}
for (String value: linkedList) {
System.out.println(value);
}
- O(1) insert
- O(1) checking whether it contains a value
code
Set mySet = new HashSet(); mySet.add("Book"); mySet.add("Pear"); mySet.add("Apple"); mySet.add("Book"); mySet.add("Class"); mySet.add("Orange"); mySet.add("Class");System.out.println("My set elements count: " + mySet.size()); for (String item : mySet) { System.out.println(item); }
code
BitSet myBitSet = new BitSet(1); System.out.println(myBitSet.size()); //64 myBitSet = new BitSet(65); System.out.println(myBitSet.size()); //128 myBitSet = new BitSet(23); System.out.println(myBitSet.size()); //64//将数组内容组bitmap myBitSet.set(1, true); myBitSet.set(2, true); myBitSet.set(3, true); myBitSet.set(0, true); myBitSet.set(3, true); System.out.println(myBitSet.get(2)); System.out.println(myBitSet.get(60)); for ( int i = 0; i < myBitSet.size(); i++ ){ System.out.println(myBitSet.get(i)); }
- O(1) to add to the top of the stack (add)
- O(1) to remove the top of the stack (pop)
- O(N) to iterate
code1
Stack myStack = new Stack<>(); myStack.push("Apple"); myStack.push("Pear"); myStack.push("Grape");System.out.println(myStack.size() + " items in stack:"); for(String item : myStack){ System.out.println(item); } while (!myStack.isEmpty()){ String top = myStack.peek(); System.out.println("Stack Top: " + top); myStack.pop(); }
code2
Deque myStack2 = new ArrayDeque();
myStack2.push("Apple");
myStack2.push("Pear");
myStack2.push("Grape");
- O(1) insert
- O(1) access & modify via Key
- O(1) check if it contains certain Key
- O(N) to look for a particular value
desc
散列表：插入删除查找都是O(1), 是最常用的，但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。code
Map myMap = new HashMap<>();
myMap.put("T.Rex", 100);
myMap.put("Bob", 35);
myMap.put("Jack", 25);
for(String key : myMap.keySet()){
System.out.println(key + " : " + myMap.get(key));
}
线程安全版本 HashMap
可以利用LinkedHashMap实现LRU Cache
code
class LruCache extends LinkedHashMap { private final int maxEntries;public LruCache(final int maxEntries) { super(maxEntries + 1, 1.0f, true); this.maxEntries = maxEntries; } @Override protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) { return super.size() > maxEntries; } }
- O(1) to add to the end of the queue (add)
- O(1) to remove the front of the queue (poll)
- O(N) to iterate
code
Queue myQueue = new LinkedList(); myQueue.add("Box"); myQueue.add("T.Rex"); myQueue.add("Jack");System.out.println(); System.out.println(myQueue.size() + " items in the queue: "); for(String i : myQueue){ System.out.println(i); } while(!myQueue.isEmpty()){ String front = myQueue.peek(); System.out.println("Front of the queue: " + front); System.out.println(" pop"); myQueue.poll(); }
线程安全版本Queue
- O(1) Inserting an element
- O(1) Accessing smallest element
- O(log(n)) Removing biggest element
code
Queue logic = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer i1, Integer i2){
return i2-i1;
}
});
Queue pq = new PriorityQueue<>(logic);
pq.add(1);
pq.add(2);
pq.add(0);
System.out.println("max element -> "+pq.peek());
TODO
- O(logn) Access complexity
- O(logn) Search complexity
- O(logn) Delete complexity
- O(logn) Insert complexity
desc
跳表：插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。
下面是一个包含 64 个结点的链表，按照前面讲的这种思路，建立了五级索引。原来没有索引的时候，查找 62 需要遍历 62 个结点，现在只需要遍历 11 个结点。
code
ConcurrentSkipListMap mySkipListMap = new ConcurrentSkipListMap();
System.out.println(mySkipListMap);
mySkipListMap.put(1, "a");
mySkipListMap.put(2, "b");
mySkipListMap.put(3, "c");
mySkipListMap.put(1, "d");//测试同一个key值
mySkipListMap.put(4, "e");
mySkipListMap.put(6, "f");
mySkipListMap.put(5, "g");
System.out.println(mySkipListMap);
System.out.println(mySkipListMap.size());
- O(logn) Insert
- O(logn) Search
- O(logn) Deletion
desc
插入删除查找都是O(logn), 中序遍历即是顺序遍历，稳定。缺点是难以实现，code
TreeMap myTreeMap = new TreeMap();
myTreeMap.put(2,"2");
myTreeMap.put(3,"3");
myTreeMap.put(1,"1");
System.out.println(myTreeMap);
Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
- O(n) build tree n 表示所有字符串的长度和
- O(k) k 表示查找的字符串长度
code
class Trie { // Define the alphabet size (26 characters for `a – z`) private static final int CHAR_SIZE = 26;private boolean isLeaf; private List<Trie> children = null; // Constructor Trie() { isLeaf = false; children = new ArrayList<>(Collections.nCopies(CHAR_SIZE, null)); } // Iterative function to insert a string into a Trie public void insert(String key) { System.out.println("Inserting \"" + key + "\""); // start from the root node Trie curr = this; // do for each character of the key for (char c: key.toCharArray()) { // create a new Trie node if the path does not exist if (curr.children.get(c - 'a') == null) { curr.children.set(c - 'a', new Trie()); } // go to the next node curr = curr.children.get(c - 'a'); } // mark the current node as a leaf curr.isLeaf = true; } // Iterative function to search a key in a Trie. It returns true // if the key is found in the Trie; otherwise, it returns false public boolean search(String key) { System.out.print("Searching \"" + key + "\" : "); Trie curr = this; // do for each character of the key for (char c: key.toCharArray()) { // go to the next node curr = curr.children.get(c - 'a'); // if the string is invalid (reached end of a path in the Trie) if (curr == null) { return false; } } // return true if the current node is a leaf node and the // end of the string is reached return curr.isLeaf; } }