Shulou(Shulou.com)05/31 Report--

Today Xiaobian to share with you the common data structure in jdk8 and its design principle is what the relevant knowledge points, detailed content, clear logic, I believe most people still know too much about this knowledge, so share this article for everyone to refer to, I hope you read this article after some gains, let's learn about it together.

1. LinkedList

LinkedList Classic double linked list structure, suitable for random insertion, deletion. The specified sequence operation performs worse than ArrayList, which is also determined by its data structure.

add(E) / addLast(E)

add(index, E)

There is a small optimization here, he will first determine whether the index is close to the head or the tail of the team, to determine which direction to traverse the chain.

if (index

< (size >

> 1)) { Node x = first; for (int i = 0; i

< index; i++) x = x.next; return x; } else { Node x = last; for (int i = size - 1; i >

index; i--) x = x.prev; return x; }

Stay at the end of the line.

get(index)

It will also judge index first, but the performance is still not good, which is why it is not recommended to use for(int i = 0; i

< lengh; i++)的方式遍历linkedlist，而是使用iterator的方式遍历。

remove(E)

2. ArrayList

The bottom layer of ArrayList is an array, so it is fast to find in order, insert in disorder, and delete because it involves shifting the elements behind it, so the performance is slow.

add(index, E)

expansion

Generally, the default capacity is 10. After expansion, it will be length*1.5.

remove(E)

Loop through the array, determine whether E equals the current element, delete performance is not as good as LinkedList.

3. Stack

Stack is a classic data structure, the bottom layer is also an array, inherited from Vector, first out of FILO, the default new Stack() capacity is 10, beyond the automatic expansion.

push(E)

pop()

4. Postfix expression

A typical application of Stack is to evaluate expressions such as 9 + (3 - 1) * 3 + 10 / 2, where the computer converts the infix expression into a suffix expression and then evaluates the suffix expression.

infix to suffix

digital direct output

When the stack is empty, the operator is encountered and directly pushed into the stack

If you encounter a left parenthesis, push it to the stack

Encounter right parenthesis, execute stack pop operation, and output the elements popped from the stack until the left parenthesis pops out of the stack, and the left parenthesis is not output.

Operator encountered (addition, subtraction, multiplication and division): pop up all stack top elements with priority greater than or equal to the operator, and then push the operator to the stack

Finally, the elements in the stack are sequentially popped out of the stack and output.

Compute Suffix Expression

When numbers are encountered, push numbers onto the stack

When an operator is encountered, pop up the top two numbers, calculate them accordingly with the operator, and push the result to the stack.

Repeat until you reach the rightmost end of the expression

The value of the operation is the result of the expression

5. queue

The difference with Stack is that Stack's deletion and addition are carried out at the end of the queue, while Queue deletion is carried out at the head of the queue and addition is carried out at the end of the queue.

ArrayBlockingQueue

A blocking bounded queue commonly used in production consumers, FIFO.

put(E)

put(E) queue is full

final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == items.length) notFull.await(); enqueue(e); } finally { lock.unlock(); }

take()

When an element is fetched, the takeIndex is updated to point to the next element instead of shifting the next element of the array.

TakeIndex is a circular increment that points to 0 when moving to the end of the queue and loops again.

private E dequeue() { // assert lock.getHoldCount() == 1; // assert items[takeIndex] != null; final Object[] items = this.items; @SuppressWarnings("unchecked") E x = (E) items[takeIndex]; items[takeIndex] = null; if (++takeIndex == items.length) takeIndex = 0; count--; if (itrs != null) itrs.elementDequeued(); notFull.signal(); return x; }

6. HashMap

The most commonly used hash table, the interview of children's shoes essential knowledge, internal through the array + single-linked list way to achieve. dk8 introduces red-black trees to optimize lists of length> 8, which we will talk about in another section.

put(K, V)

put(K, V) same hash value

resize Dynamic expansion

When the elements in the map exceed the set threshold, the resize (length * 2) operation will be performed. During the expansion process, the elements will be operated and placed in a new position.

The specific operation is as follows:

In jdk7, rehash all elements directly and put them in new positions.

In jdk8, determine whether the new bit bit of the original hash value of the element is 0 or 1. If 0, the index will remain unchanged, and if 1, the index will become "original index + oldTable.length".

//Define two chains//The original hash value adds a chain with bit 0, head and tail Node loHead = null, loTail = null; //The original hash value adds a chain with bit 1, head and tail Node hiHead = null, hiTail = null; Node next; //Loop through the chain do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else www.example.com = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while (e = next) != loTail.next null); //chain with constant position before and after expansion if (loTail != null) {loTail.next = null; newTab[j] = loHead; } //chain of expanded position plus original array length if (hiTail != null) { 32 hiTail.next = null; 33 newTab[j + oldCap] = hiHead; 34 }

7. LinkedHashMap

Inherited from HashMap, the bottom layer additionally maintains a doubly linked list to maintain data order. FIFO(insert ordered) or LRU(access ordered) cache can be implemented by setting accessOrder.

put(K, V)

get(K)

When accessOrder is false, just return the element directly, no need to adjust the position.

When accessOrder is true, the most recently accessed element needs to be placed at the end of the queue.

removeEldestEntry Remove the oldest element

The above is "jdk8 commonly used data structure and its design principle is what" all the content of this article, thank you for reading! I believe everyone has a great harvest after reading this article. Xiaobian will update different knowledge for everyone every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.