Shulou(Shulou.com)06/01 Report--

HashMap plus two-way linked list to build an IM system session list memory model example analysis, in view of this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Every IM system has a session list page, and when a session receives or sends a message, the session ranks at the top of the session. Because message roaming is supported, the server side needs to save the session order of each user client. How can we accurately record the conversation order of each client in the scenario of sending and receiving massive messages?

An algorithm similar to LRU memory obsolescence can be used to solve this problem. The combination of HashMap and LinkList (linked list) is adopted (as shown in the following figure).

On the left side of the figure is a Map structure that can be quickly indexed to specific session (session) data through sessionid, and the session data is stored as a linked list (on the right side of the figure).

When the session receives or sends a message, the specific session data is located by Map at O (1) time, and then the linked list pointer of the session data is modified to put the session data into the linked list header (top). The time complexity of completing the entire operation is constant and can be regarded as O (1) level. It's very efficient.

When other devices pull the session list, you can return the session list in batches according to the linked list order.

In the actual R & D level, taking into account the data persistence and R & D efficiency, we can choose the SortedSet structure of Redis, the time complexity is O (lg N), and N is the number of sessions. The complexity of properly controlling the number of saved sessions is perfectly acceptable.

This is the answer to the sample analysis question on the HashMap plus two-way linked list to build the IM system session list memory model. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel for more related knowledge.

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.