This is the sixth day of my participation in the August Text Challenge.More challenges in August

The linear table

There are two kinds of linear lists: sequential lists and linked lists. Let’s start with diff.

The order sheet

Order tables are implemented based on arrays, such as ArrayList, which take up a contiguous chunk of memory because they are sequential, and which take up a contiguous chunk of memory because they are not sequential, so compare egg Pain.

First, it takes no memory, since all you need to do is store the element values. I have a lot of rooms, but they’re not next to each other. If you want to have a bunch of rooms next to each other, I have to talk to other guests and ask them to make room for you and get you a bunch of rooms next to each other, which is expressed in the code: GC can be triggered frequently because there is no contiguous memory and you need to rearrange the memory to give you contiguous memory. So its characteristics can be summarized as: small space occupation, but to be continuous.

Second, it supports random access, because it is a continuous memory space, so I just need to press the serial number to find it. For example, it lives on the second floor of the hotel, from room 1 to room 10. I want to find the ninth guest, and directly knock on the door 9. However, its deletion efficiency is very low, for example, now no. 5 room to check out, let no. 5 go, but it is clear to continuous memory space, so if no. 5 room is empty, it is not continuous, also have to let No. 6 to no. 5, 7 to No. 6… In this way, some people say: directly let the last person (10) to move to no. 5 not on the line, no! Because it would destroy the order (number 10 was behind number 9, but now it is in front), it would not work, so the ones behind would have to move forward in order, and in the same way, if someone came to live in room 5, they would have to move back in order. Its two characteristics can be summarized as: good at access, not good at insertion and deletion

Therefore, it can be summarized as follows: The order table is ordered, which does not consume memory but needs to occupy continuous memory space, which is conducive to random access and not conducive to insertion and deletion

There are a lot of uses for sequence lists in development, such as ArrayList, which is a new favorite in The game of LOL:

List<String> list = new ArrayList<>();
Copy the code

Often used in RecyclerView or ListView adapter, this is no nonsense.

You can use ArrayList for anything that doesn’t involve delete and insert, such as pulling server data, retrieving database data, and so on.

If the List stores an Integer, the remove() method must be called with an Object or index parameter:

If the element is Integer, remove(10) defaults to E remove(int index) of remove(index); boolean remove(Object o);Copy the code

This is a trap, because most people don’t look at the return value. If you want to call remove(Object), you can use the wrapper type conversion.

The list

Linked lists are novice killers, and a list inversion algorithm can kill a lot of people. In fact, if you understand how it works, you can press it to the ground and rub it to death.

The core of a linked list is a chain, for example, the simplest single linked list. In addition to storing the value of the element, each node has a reference, which is followed by the adjacent point. This reference is the core of a linked list.

Class Node {// Store the element value Object value; // store Node next; }Copy the code

However, it does not require high memory requirements, does not need continuous memory space, for example, or live in A hotel, they do not need next to the room, for example: A says, I live in this room, then it holds B’s wechat, B says, I live in this room, it holds C’s wechat, and so on…. In this way, the rooms do not need to be next to each other, so they can live in their own rooms. Moreover, if B leaves, C does not need to go to B’s room to live, but only need to let B give C’s contact information to A, so that A and C are connected, very convenient. But it has one drawback: it does not support random access. For example, IF I want to find D among them, I don’t know where D is. I have to find A first, then find B through its wechat, then find C through B’s wechat, and then find D through C’s wechat.. .

Therefore, its characteristics can be summarized as follows: Linked lists consume more memory, but do not require continuous memory space, which is conducive to insertion and deletion, not conducive to random access

Let’s say we have A list :A -> B ->C -> D, we want to delete B, someone said, just A->C, no! Because A can only find B, but not C directly, we need to make the wechat in A’s hand become the wechat in B’s hand. A. ext = b. ext.

Similarly, if we were to insert E between A and B, it would be: A -> E -> B -> C -> D. As we know, this requires E to have B’s wechat, and A to have E’s wechat. Then, we can first make A’s wechat turn into E, and then let E’s wechat turn into B. Wait, there is A problem. If the wechat in A’s hand is changed to E first, THEN A will not have B’s wechat. Where can E find B’s wechat? No way! Because to find B, you first have to find A to get B’s wechat account, but now A doesn’t have B’s wechat account either. So we should: first let A give B’s wechat to E, and then let THE wechat in A’s hand change to E, because E is standing here, A can directly find E to ask for its wechat. That is:

E.next = A.next; // A sends B's wechat to E. // A is changing wechat into ECopy the code

So the trick with linked lists is to first list the results you want, and then place the actions that cause the changes later, as in the example above:

  • Let’s list the results: a.ext = E; E.next = A.next;
  • Then sort:
// order 1 a.ext = E; // a.ext changed e.ext = a.ext; // we want to use a.ext, but we have already changed a.ext. Then you need to put the previous changes behindCopy the code

So, we need to adjust the order:

E.next = A.next; // modify e.ext a.ext = E; // change a.ext, e.ext is not used hereCopy the code

So, the trick of the linked list algorithm is to reorder the results of the first column and put the operations that cause the subsequent changes behind. Of course, in some cases you may need to introduce temporary variables, which I won’t go into here.

So, where do linked lists work in development scenarios: where inserts and deletions are frequent. For example: a member list of a live broadcast room, members frequently enter and exit, when I want to delete this person from the list. In general terms, linked lists should be used wherever frequent insertion and deletion of elements are involved.

To sum up, we know that both sequential and linked lists are ordered, and they are ordered by the order in which the elements are added. The sequential table has high access efficiency but low insertion and deletion efficiency. It does not consume memory but requires continuous memory space. Linked list access efficiency is low, insert and delete efficiency is high, relatively memory consumption but does not need continuous memory space.

The mapping table

The family of mapping tables is large and can be subdivided into many, but there are several commonly used ones:

  • HashMap: The most basic mapping table, based on linked list array and red-black tree implementation, unordered, ideal access efficiency O(1), but relatively memory.
  • TreeMap: based on red-black tree, ordered by key, adding/removing elements involves tree rotation, so the time complexity is log(n).
  • LinkedHashMap: Implements the same principle as HashMap, but with an internal linked list that maintains the order of elements in order of addition, and can specify whether to automatically adjust the latest element to the header, which can be used to implement LRUCache.
  • ConcurrentHashMap: Based on piecewise lock implementation, supports a certain granularity of concurrent access, because the internal implementation principle is CAS, so the efficiency is higher than the general Synchronized series.

The Android API:

  • ArrayMap: Based on a complete binary tree, it has basically the same function as HashMap. The access efficiency is lower than HashMap (log(n)), but it is very saving. There are only two arrays inside, one for hash and one for key and value.
  • SparseArray: similar to HashMap, except that the Key can only be an Integer and the access efficiency is log(n). It is very simple to store. There are only two internal arrays, one for Key and one for value.

As you can see, most of the apis provided in Android are for saving memory, which makes sense on mobile devices where memory is precious. So, in Android development, SparseArray is recommended if your key is Integer; Otherwise, ArrayMap is recommended. Of course, if you have high performance requirements and low memory requirements, you can use HashMap, if you want to order by key, you can use TreeMap, if you want to order by store order, you can use LinkedHashMap, if it’s concurrent, ConcurrentHashMap can be used.

For example, if I want to maintain a list of friends and be able to find friends based on their IDS, I need an ID-friends mapping. If the ID is Integer, we can use SparseArray, and if the ID is String, we can use ArrayMap.

For example, in a music App, the user has a “favorite list”, which can be added according to the order of the user’s favorites and searched according to the name of the song. Then there are two key points: 1. If you just add order by ArrayList or LinkedList, you can use ArrayList or LinkedList, but in this case, you need to traverse by song name, which is too inefficient, so since you search by song name, there must be a: song name-song mapping. So we’re going to use the map table, and because we’re adding order, we’re going to use the LinkedHashMap.

When a LinkedHashMap is created, you can specify the accessOrder parameter, which, if true, will be automatically sorted to place the most recently accessed elements first, ensuring that the preceding elements are the most recently accessed. You can use this to implement LRUCache.

For example, if we want to make an app and need to cache the friends list locally, we can create a friends table to save our friends. However, if I log in to another account on this device one day, the friends list obtained will be the friends list of the previous account, so, We need to create multiple tables based on different user ids to match the friends table with the user ID, but there is a problem. What if I log in 100 accounts one by one on this device? Can I save 100 Friends tables on my phone? No, this is a mobile phone, not a server, it consumes too much storage space, so we can limit each device to 3 friends table at most, then what about the fourth login account, should we delete the first login? If A is the first user to log in, but B has logged in recently, then B is the least recently logged in, that is, the furthest logged in. Therefore, we should delete the friends table of account B. But there is a problem, if MY login order is: ABBBBBBBBBBCA, so, you also delete B? No, because B logs in so often, we can assume that he is A frequent user, C and A only come here occasionally, so we should delete C. In general, we should not only record the login time, but also the login times, the one with the least combination should be deleted. This is the Least Recent Use, or LRU. That’s how our LRUCache works.

Therefore, the LinkedHashMap is suitable for scenarios where you want to store elements in order or implement an LRU cache.

TreeMap is ordered by key. It is based on a red-black tree. That is, each element has a smaller left child and a larger right child, and each put or remove element is adjusted to this order. TreeMap is used when we need elements to be ordered.

As for ConcurrentHashMap, which is rarely used by most people, just remember that it is preferred for concurrent applications, since high concurrency scenarios are rare for clients.

To sum up, in mobile development, we use SparseArray when our key is Integer, and ArrayMap otherwise; To store ordered elements or implement LRU caching, use LinkedHashMap; When you want to customize sorting, use TreeMap. When encountering concurrency, use ConcurrentHashMap.

The stack and queue

Stacks and queues are also linear tables in nature, but the order of entry and exit of elements is quite special.

Stack: first in, last out, queue: first in, first out. In other words, the stack goes back to history, the queue goes back to history, and the rollback goes back to front.

The stack is rarely used in development, but it is ubiquitous, such as our common method calls:

void funA() {
    funB();
}

void funB() {
    funC();
}

void funC() {

}
Copy the code

In the JVM, there is a stack of methods, and each method call creates a stack frame to merge into the stack. FunA () is pushed, funB() is pushed, funC() is pushed, then funC() is pushed, then funC() is pushed, then funB() is pushed, then funB() is pushed, and the result is given to funA(), then funA() is pushed.

FunA () -> funB() -> funC(); FunC () -> funB() -> funA();

So, the JVM’s method calls are implemented on a stack basis. It also embodies the idea of backtracking: go this way, and go back this way!

Queues are common in the development, everywhere, for instance we should achieve a downloader to download Queue, you can create a Queue, each time there is a task, to add to the Queue, then detect the current tasks to download, if you have, even if, not out of the team and download, download after testing Queue again whether there is any task, Get out of the queue and download, and so on.

Queue in the source code is also a lot of use, such as the most common Handler MessageQueue, for example, OkHttp inside the request queue is a double-ended queue, is also a queue. Actually LinkedList is also a two-ended queue, but queue is an abstract concept, and LinkedList is a concrete implementation of queue.

And then let’s look at the PriorityQueue. PriorityQueue is based on a pile of implementation, its essence is a complete binary tree, can be divided into big heap or small cap pile, large pile top is the root node is the largest, small cap pile is minimum root node, and each time you add or remove elements, it will automatically adjust, making the remaining elements is still a big pile top/small cap heaps, and traverse the big heap, Each time you get the largest element, the smallest element is the little top heap.

Let’s start with a simple observer pattern: users can subscribe to changes in books from a bookstore:

Class Book {String name; String title; } // Interface Observer {void onBookChanged(Book Book); } // Define the class BookStore {// observers private List<Observer> observers = new ArrayList<>(); Public void addObserver(Observer Observer) {if (! observers.contains(observer)) { observers.add(observer); Observeobserver public void observeObserver (Observer Observer) {observe.remove (Observer); } // Notify observers of changes private void notify(Book Book) {for (Observer Observer: observers) {observer.onbookchanged (Book); Void changeBook(Book Book) {book.name = "android"; notify(book); }}Copy the code

The code is simple and understandable, and we implement an observer model that notifies the observer indiscriminately when a book changes, but now: one day, the boss says: If a book changes, inform me first, how can I make sure I inform the boss first? We have two options:

  • 1 Add a separate observer to the BookStore, representing the boss, and the code looks like this:
// define class BookStore {private List<Observer> observers = new ArrayList<>(); Private Observer bossObserver; Public void setBossObserver(Observer bossObserver) {this.bossObserver = bossObserver; } public void addObserver(Observer observer) { if (! observers.contains(observer)) { observers.add(observer); } } public void removeObserver(Observer observer) { observers.remove(observer); } private void notify(Book Book) {if (bossObserver! =null) bossObserver.onBookChanged(book); For (Observer Observer: observers) {observer.onbookchanged (book); } } void changeBook(Book book) { book.name = "android"; notify(book); }}Copy the code

Is that ok? Yeah, but, uh, what kind of model is this? There’s registration and de-registration, there’s setter functions, nondescribable, and! Most importantly: if you have two bosses and three bosses, why not continue to add member variables? Definitely not! This maintenance is too laborious, and, as a bookstore, also have to know who is the big boss, who is the small boss, in fact, as a bookstore, should not know so fine, this does not accord with the least knowledge principle. Even one day: big boss say, you first send 2 boss, then send me again,…. No solution!

So, can we solve it? Yes, we use the second method, which is: let the observers be in order. Our bookstore just distributes them, as long as the observers are in order, they will be distributed to the boss and users in the right order.

Comparable interface Observer extends Comparable<Observer> {int priority(); Void onBookChanged(Book Book); Override default int compareTo(Observer o) {return o.ority () -priority (); }}Copy the code

Our BookStore needs to be slightly modified:

Private List<Observer> observers = new ArrayList<>(); Public void addObserver(Observer Observer) {if (! observers.contains(observer)) { observers.add(observer); // New observers need to sort collections.sort (observers); Observeobserver public void observeObserver (Observer Observer) {observe.remove (Observer); // Remove the need to sort collections.sort (observers); } // Notify observers of changes private void notify(Book Book) {for (Observer Observer: observers) {observer.onbookchanged (Book); Void changeBook(Book Book) {book.name = "android"; notify(book); }}Copy the code

The changes are minimal, and we simply reorder them every time we add or remove an observer. So, is there an easier way? Yes! BookStore is the largest/smallest remaining element in the sequence. We modify BookStore as follows:

Observers = new PriorityQueue<Observer> observers = new PriorityQueue<>(); Public void addObserver(Observer Observer) {if (! Observers. contains(observer)) {// observers.offer(observer); Observeobserver public void observeObserver (Observer Observer) {observe.remove (Observer); } // Notify observers of changes private void notify(Book Book) {for (Observer Observer: observers) {observer.onbookchanged (Book); Void changeBook(Book Book) {book.name = "android"; notify(book); }}Copy the code

The code is simple, we simply replace the observer set with PriorityQueue and add the observer using offer(). BookStore does not need to be changed at all. However, there is a risk that the Observer can return its own Priority and the boss’s Priority if it is not the boss. Therefore, we need to reduce the permission and use enumeration. You can also use the check mechanism, without further ado.

Based on the above code, we can build a framework of NB, we can define an event dispatcher, a data processor, a UI handler, when the server data to come over, we will in the event the dispenser to receive first, and then distributed to the data processor, data processor parses and save the data, then the dispenser and then distributed to the UI handler events, In this case, the UI processor directly goes to the data processor to obtain the data, the code is roughly as follows:

Enum Priority {DATA(10), UI(0); int priority; Priority(int priority) { this.priority = priority; } } interface Observer extends Comparable<Observer> { Priority priority(); void onBookChanged(Book book); @Override default int compareTo(Observer o) { return o.priority().priority - priority().priority; }} class DataHandler implements Observer {@override public Priority Priority () {return Priority.DATA; } @override public void onBookChanged(Book Book) {UIHandler implements Observer {@override public Priority Priority () {// Return Priority.UI; } @override public void onBookChanged(Book Book) {Copy the code

The above code describes the general logic, and once we understand this, our application architecture will be much more flexible.

Atom type

Atomic types refer to AtomicInteger, AtomicBoolean, and other types of the Atomic family, which are implemented based on CAS and are thread-safe.

You must have encountered the problem of using a local variable ina lambda, but the prompt must be final. The key is how to declare it as final when the lambda is modified. It is estimated that someone will extract it as a member variable.

For example, code like this: first use the local URL, if the server returns, use the server’s,

Void test() {// Get the local URL. String URL = "http://www.baidu.com"; HttpAPi. GetRealUrl ("url/data", (bean) -> {runOnUiThread(() -> {if (bean! = null) { if (! IsEmpty (bean.url) {// Return the url of the server, but the error message is that the lambda can only use final, MMP! url = bean.url; } // println(url); }); }); }Copy the code

In a lambda, only final modifiers can be accessed, but I want to modify them without using final modifiers. On the Atomic! , the code is as follows:

Void test() {// Take the local URL. AtomicReference<String> url = new AtomicReference<>("http://www.baidu.com"); HttpAPi. GetRealUrl ("url/data", (bean) -> {runOnUiThread(() -> {if (bean! = null) { if (! Set (bean.url); textutils.isempty (bean.url); Println (url.get());}} // Print, use get() to get println(url.get()); }); }); }Copy the code

As you can see, the Atomic series is like a repository, easily accessed using PUT/GET. And it is based on CAS, it is optimistic and there are no efficiency issues.

conclusion

  • Non-mapping, random access more, insert and delete less, use ArrayList; Otherwise, use LinkedList.
  • Mapping relationships, key is Integer, use SparseArray, otherwise use ArrayMap; If performance requirements are high, use HashMap. If storage order is required or LRUCache is implemented, use LinkedHashMap. You can use TreeMap if you need to sort yourself, or ConcurrentHashMap if you have concurrent scenarios.
  • Consider Queue for fifo, Stack for fifO, PriorityQueue for automatic ordering of elements, and Atomic series for lambda using/to modify local variables.