当前位置:网站首页>[HBZ share] reasons for slow addition and deletion of ArrayList and fast query
[HBZ share] reasons for slow addition and deletion of ArrayList and fast query
2022-07-06 04:21:00 【hbz-】
ArrayList When is the query fast ?
- Only by subscript index When inquiring , Very fast performance , Because you can directly find the corresponding data in the following table , Time complexity O(1)
- When non subscript query , But through for Loop to traverse , The performance is not fast , Time complexity O(n)
- myth : Many people mistakenly think ArrayList Any inquiry is fast , It's actually wrong , Only through index Our inquiry is very fast
ArrayList Why the increase of performance is slow
- In image ArrayList Add elements to add When , Could lead to List Expansion of , because ArrayList The bottom layer is array structure , But the data does not support dynamic expansion , therefore ArrayList The capacity expansion mechanism of is to create a new array , Migrate the array data to the new array , Then add new elements
- The expansion mechanism is , If the original array does not exist , And expand the capacity directly 10 individual . If the original array exists , Then expand 1.5 By , namely oldSize + oldSize >> 1
ArrayList Why is the deletion performance slow
- Deletes the specified element ,ArrayList The bottom layer is actually deleted from index The position is the starting point , All elements to the last , Move one bit forward , Then set the last bit to null
- Move all elements , In fact, it is through the bottom System.arraycopy(), The array of index+1 Position start , Copied to the index Location , Then the last one =null
- So the process will be slow
ArrayList Modification of
- Modification is the same as query , When specifying index when , Directly modifying , A high performance O(1)
- When the cycle for To modify , Then the performance is low O(n)
边栏推荐
- P3500 [POI2010]TES-Intelligence Test(二分&离线)
- 2327. 知道秘密的人数(递推)
- Implementation of knowledge consolidation source code 1: epoll implementation of TCP server
- Solutions: word coverage restoration, longest serial number, Xiaoyu buys stationery, Xiaoyu's electricity bill
- 图应用详解
- 题解:《单词覆盖还原》、《最长连号》、《小玉买文具》、《小玉家的电费》
- 【leetcode】1189. Maximum number of "balloons"
- 拉格朗日插值法
- Yyds dry goods inventory web components series (VII) -- life cycle of custom components
- P2022 interesting numbers (binary & digit DP)
猜你喜欢
Fedora/rehl installation semanage
Understanding of processes, threads, coroutines, synchronization, asynchrony, blocking, non blocking, concurrency, parallelism, and serialization
R note prophet
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
Cross domain and jsonp details
[face recognition series] | realize automatic makeup
How do programmers teach their bosses to do things in one sentence? "I'm off duty first. You have to work harder."
10個 Istio 流量管理 最常用的例子,你知道幾個?
[Zhao Yuqiang] deploy kubernetes cluster with binary package
MySQL learning record 13 database connection pool, pooling technology, DBCP, c3p0
随机推荐
NPM command -- install dependent packages -- Usage / explanation
How to execute an SQL statement in MySQL
[face recognition series] | realize automatic makeup
Web components series (VII) -- life cycle of custom components
2/13 review Backpack + monotonic queue variant
729. 我的日程安排表 I(set or 动态开点线段树)
Deep learning framework installation (tensorflow & pytorch & paddlepaddle)
Mysql database storage engine
【leetcode】22. bracket-generating
80% of the diseases are caused by bad living habits. There are eight common bad habits, which are both physical and mental
BOM - location, history, pop-up box, timing
软考 系统架构设计师 简明教程 | 总目录
In depth MySQL transactions, stored procedures and triggers
SharedPreferences 源码分析
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
Mixed development of QML and QWidget (preliminary exploration)
Knowledge consolidation source code implementation 3: buffer ringbuffer
2328. 网格图中递增路径的数目(记忆化搜索)
During pycharm debugging, the view is read only and pause the process to use the command line appear on the console input
asp. Core is compatible with both JWT authentication and cookies authentication