Java|illustrated data structures and principles for dummies!
Author丨Dao Fang Yuan
cnblogs.com/xdecode/p/9321848.html
Recently, I've been organizing my knowledge of data structures, and I've been systematically looking at common data structures in Java, and I've had the idea to use animation to draw the data flow process.
Based mainly on jdk8, there may be some features that are not the same as before jdk7, such as LinkedList The bidirectional list in LinkedHashMap is no longer loopback.
The single-linked table in HashMap is a tail insertion, not a head insertion, and so on, and these differences will not be repeated later, the structure of this paper is as follows.
LinkedList
Classic double-linked table structure, suitable for insertion and deletion in disorder. Specifying a sequence operation is not as good as an ArrayList, which is also due to its data structure.
add(E) / addLast(E)
add(index, E)
There is a small optimization here, he will first determine if the index is near the beginning or the end of the queue, to determine which direction to traverse the chain in.
1 if (index < (size >> 1)) { 2 Node x = first; 3 for (int i = 0; i < index; i++) 4 x = x.next; 5 return x; 6 } else { 7 Node x = last; 8 for (int i = size - 1; i > index; i--) 9 x = x.prev; 10 return x; 11 }
on the tail of the line
get(index)
也是会先判断index, 不过性能依然不好, 这也是为什么不推荐用for(int i = 0; i < lengh; i++)的方式遍历linkedlist, 而是使用iterator的方式遍历.
remove(E)
ArrayList
The underlying array is an array, so lookups are fast in order, insertions and deletions are slow because they involve shifting elements behind them.
add(index, E)
expand capacity
The default capacity is 10, after expansion, it will be length*1.5.
remove(E)
Loop through array, determine if E equals current element, remove performance is not as good as LinkedList.
Stack
Classical data structure, the underlying is also an array, inherited from Vector, first-in, last-out FILO, default new Stack() capacity is 10, beyond which the capacity is automatically expanded.
push(E)
pop()
suffix expression
A typical application of Stack is to compute expressions such as 9 + (3 - 1) * 3 + 10 / 2, where the computer converts the midfix expression to a suffix expression, and then computes the suffix expression. Recommended reading.
infix to suffix
- Digital Direct Output
- When the stack is empty, when an operator is encountered, it goes directly onto the stack
- If a left bracket is encountered, put it on the stack
- When a right bracket is encountered, the stack-out operation is performed and the elements of the stack-out are output until the stack is popped with a left bracket, which is not output.
- Encounter operator (add, subtract, multiply, divide): pop all top-of-stack elements whose priority is greater than or equal to the operator, then add the operator to the stack
- 最终将栈中的元素依次出栈，输出。
Computational Suffix Expressions
- Press numbers onto the stack when encountered
- When an operator is encountered, the two numbers at the top of the stack are popped out, the operator is used to do the corresponding calculation on them, and the result is added to the stack
- Repeat the above process until the rightmost end of the expression
- The value resulting from the operation is the result of the expression
formation
The difference with a Stack is that a Stack is deleted and added at the end of the queue, while a Queue is deleted at the head of the queue and added at the end.
ArrayBlockingQueue
生产消费者中常用的阻塞有界 formation, FIFO.
put(E)
put(E) queue is full
1 final ReentrantLock lock = this.lock; 2 lock.lockInterruptibly(); 3 try { 4 while (count == items.length) 5 notFull.await(); 6 enqueue(e); 7 } finally { 8 lock.unlock(); 9 }
take()
When an element is taken out, instead of shifting the elements behind the array, the takeIndex is updated to point to the next element.
takeIndex is a circular growth, and when it moves to the end of the queue, it will point to 0 and loop again.
1 private E dequeue() { 2 // assert lock.getHoldCount() == 1; 3 // assert items[takeIndex] != null; 4 final Object[] items = this.items; 5 @SuppressWarnings("unchecked") 6 E x = (E) items[takeIndex]; 7 items[takeIndex] = null; 8 if (++takeIndex == items.length) 9 takeIndex = 0; 10 count--; 11 if (itrs != null) 12 itrs.elementDequeued(); 13 notFull.signal(); 14 return x; 15 }
HashMap
最常用的哈希表, 面试的童鞋必备知识了, 内部通过数组 + 单链表的方式实现. jdk8中引入了红黑树对长度 > 8的链表进行优化, 我们另外篇幅再讲。
put(K, V)
put(K, V) same hash value
resize Dynamic expansion
When the elements in the map exceed the set threshold, a resize (length * 2) operation is performed, during which the elements are manipulated in one pass and placed in a new location.
This is done as follows:
In jdk7 all elements are directly rehashed, and placed in a new location.
在jdk8中判断元素原hash值新增的bit位是0还是1, 0则索引不变, 1则索引变成"原索引 + oldTable.length".
1 // Define two chains 2 // the original hash value added to the chain with bit 0, the head and tail 3 Node loHead = null, loTail = null; 4 // the original hash value added to the chain with bit 1, head and tail 5 Node hiHead = null, hiTail = null; 6 Node next; 7 // Loop traversal out of the chain 8 do { 9 next = e.next; 10 if ((e.hash & oldCap) == 0) { 11 if (loTail == null) 12 loHead = e; 13 else 14 loTail.next = e; 15 loTail = e; 16 } 17 else { 18 if (hiTail == null) 19 hiHead = e;20 else 21 hiTail.next = e; 22 hiTail = e; 23 } 24 } while ((e = next) != null); 25 // Chain with unchanged position before and after expansion 26 if (loTail != null) { 27 loTail.next = null; 28 newTab[j] = loHead; 29 } 30 // chain of expanded positions plus the length of the original array 31 if (hiTail != null) { 32 hiTail.next = null; 33 newTab[j + oldCap] = hiHead; 34 }
LinkedHashMap
Inherits from HashMap, the underlying layer maintains an additional two-way chain to keep the data ordered. FIFO (insert-ordered) or LRU (access-ordered) caching can be implemented by setting accessOrder.
put(K, V)
get(K)
If accessOrder is false, just return the element without adjusting the position.
accessOrder为true的时候, 需要将最近访问的元素, 放置到队尾.
removeEldestEntry removes the oldest element