2023年6月28日发(作者：)

JavaAndroid常⽤数据结构总结本⽂主要针对开发中常⽤的数据结构做个总结，主要还是源码原理相关的内容，尤其是⾯试需要复习的同学可以多研究⼀下。线性表ArrayList、LinkedListArrayList基于动态数组实现的，初始化的时候没有指定⼤⼩的话，默认容量是10，添加元素的时候会判断是否需要对数组扩容，每次扩容⼤⼩为1.5倍，扩容是通过数组的拷贝实现的，这是⼀个⾮常耗性能的操作，所以如果可以确定⼤概的数据量，可以直接指定list⼤⼩。由于list是基于数组实现的，数组的特点是在堆内存中⽤连续的内存空间来存储，所以访问／查找效率⽐较⾼，⽽在列表中间添加／删除元素的话，需要数组拷贝来完成，所以添加／删除效率会⽐较低，如果是在末尾操作的话，效率没什么影响，因为不需要数组拷贝，时间复杂度为O(1)。LinkedList通过⼀个双向链表来实现，⼤概结构如下：双向链表结构

双向链表的数据存储单元是节点（前驱节点、后继节点、本节点数据），它不需要像数组那样知道数据⼤⼩，在内存存储上不需要连续的内存空间，双向链表通过指针来指向前后数据；它插⼊／删除数据是靠改变指针指向来实现。链表结构决定了它没有⼤⼩限制，也不会有什么初始化值和扩容。插⼊／删除效率LinkedList中定义了头部和尾部2个Node，如果插⼊／删除的位置是头部／尾部的话，时间复杂度是O(1)；如果插⼊／删除位置是在中间的话，它会先做⼀次⼆分法查找，判断索引是在前半段还是在后半段，从短的那头开始遍历，找到之后，新建⼀个节点，建⽴新的前置节点和后置节点的关系，时间复杂度最⼤是O (n/2)；访问效率也是同样的查找⽅法，时间复杂度也是最⼤是O (n/2)。DequeLinkedList实现了Deque接⼝，这个接⼝同时实现了栈和队列的功能，所以，LinkedList还可以当作栈或者队列来使⽤。ArrayList 和LinkedList简单对⽐ArrayList是基于动态数组实现的，⽽LinkedList是双向链表；堆内存存储上，ArrayList连续的内存空间，LinkedList不需要；ArrayList随机访问⽐较快，因为可以通过⾸地址+偏移量直接计算出我想访问的第x个元素在内存中的位置,⽤时间复杂度来表⽰的话是O(1),⽽LinkedList是o（n／2）；插⼊／删除来看，ArrayList效率不如LinkedList，因为前者要做数组拷贝（耗性能），后者只是相关节点前后指针的移动；⼆者都是线程不安全ArrayList真的⽐LinkedList添加／删除快吗？如何判断⼆者的使⽤场景？线程安全的 CopyOnWriteArrayList从源码分析可以看出ArrayList不是线程安全的，要变成线程安全⽅法很多，⽐如说替换成Vector，再或者是使⽤ Collections，将ArrayList 包装成⼀个线程安全的类。不过这两种⽅法也有很⼤的缺点，那就是他们使⽤的都是独占锁，独占式锁在同⼀时刻只有⼀个线程能够获取，效率太低。于是CopyOnWriteArrayList 应⽤⽽⽣了。(1) 、独占锁效率低：采⽤读写分离思想解决读操作不加锁，所有线程都不会阻塞。写操作加锁，线程会阻塞。(2) 、写线程获取到锁，其他线程包括读线程阻塞但是这时候⼜出现了另外⼀个问题了：写线程获取到锁之后，其他的读线程会陷⼊阻塞。(3)、解决思路：CopyOnWrite思想当我们往⼀个容器添加元素的时候，不直接往当前容器添加，⽽是先将当前容器进⾏ Copy，复制出⼀个新的容器，然后新的容器⾥添加元素，添加完元素之后，再将原容器的引⽤指向新的容器。简单来说就是更新数据的时候做⼀次数组拷贝，对拷贝的新对象操作完了，再让原来的容器对象指向这个新对象。(4)、优点不会存在读数据阻塞线程的情况，适合多线程中读多写少的场景(5)、缺点数据不⼀致的问题。如果写线程还没来得及写会内存，其他的线程就会读到了脏数据内存消耗⼤。由于在写的时候会做数组拷贝，当2个数组内容都⽐较多的时候，内存占⽤就⽐较⾼。CopyOnWriteArrayList的核⼼思想是利⽤⾼并发往往是读多写少的特性，对读操作不加锁，对写操作，先复制⼀份新的集合，在新的集合上⾯修改，然后将新集合赋值给旧的引⽤，并通过volatile 保证其可见性，当然写操作的锁是必不可少的了。栈、队列Stack注意，这⾥说的栈是指。栈是线性表的⼀种，底层是通过数组来实现的，它只能在栈顶操作数据，数据的进出⽅式是先进后出（FILO）。继承于Vector，是线程安全的。栈.png

Queue注意，这⾥说的栈是指. Queue。队列也是线性表的⼀种，它是从队尾插⼊数据，从队列头部取数据，数据进出⽅式先进先出（FIFO）。Queue是⼀个接⼝，所以队列的实现由其他实现类完成，⽐如LinkedList，是线程不安全的。队列.png Deque双端队列，继承于，也是⼀个接⼝，同时具备中栈和队列的特点，它可以从两端分别进⼊插⼊，删除操作。我们熟知的LinkedList就实现了Deque。HashMap、LinkedHashMap、ConcurrentHashMapHashMap数据结构是：数组+链表（jdk1.8引⼊了红⿊树）的形式来存放键值对的。⾸先对key做hash()运算来确定元素在数组中的位置，但是不同的key做hash运算得到的值可能是⼀样的，如果不同的key计算之后得到的索引相同，那么在这个位置会创建⼀个单向链表来存储相同索引的元素，在jdk1.8中，如果这个链表的元素超过8个，会引⼊红⿊树来提升效率，说HashMap是兼具数组访问快和链表添加／删除快的优点，由于HashMap 是根据key的hash值在数组上随机分布的，所以hashmap是⽆序的。hashmap之所以要设置长度必须为2的n次⽅，是因为这样可以减少碰撞，使元素分散的更均匀。

int index= hash & (length- 1)

具体来说，当length=2^n，那么length-1转化为2进制数，低位的每⼀位都是1，这样在做与运算的时候，index就能分散到更多的位置，否则的话就有⼀些位置永远都不会存储元素。当然如果⽤取模运算就不必有这个限制，hash % (length- 1)，但是这样呢运算效率很低。hashmap的加载因⼦为什么是0.75f？因为过⼩的话，会造成扩容频繁；过⼤的话会产⽣更多碰撞LinkedHashMapLinkedHashMap继承于HashMap，它是在HashMap的基础上通过双向链表维护元素节点间的顺序，默认是按插⼊顺序排序，原理是把新加⼊的元素放在双向列表的尾部；如果是访问顺序排序的话，访问元素的时候会把元素放在链表尾部，这样就可以维护访问顺序，最常见的应⽤就是LRU算法。ConcurrentHashMapConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。⼀个ConcurrentHashMap⾥包含⼀个Segment数组，Segment的结构和HashMap类似，是⼀种数组和链表结构， ⼀个Segment⾥包含⼀个HashEntry数组，每个HashEntry是⼀个链表结构的元素，每个Segment守护者⼀个HashEntry数组⾥的元素,当对HashEntry数组的数据进⾏修改时，必须⾸先获得它对应的Segment锁。所以ConcurrentHashMap是线程安全的，且在性能上不输HashMap。Set⾸先Set是⼀个接⼝，它的实现类主要有HashSet、TreeSet，它的特点是：不允许存储的元素重复。HashSetHashSet内部是使⽤HashMap来实现的元素存储，特点：⽆序、不允许元素重复。利⽤了hashmap的key不会重复的特性来实现元素的唯⼀性。TreeSet使⽤的TreeMap来实现的元素存储。同样是以存储的元素作为TreeMap的key，所以元素也是不能重复的。另外因为TreeMap的key是有序的，所以TreeSet是⼀个有序的集合。树形结构Tree深度优先遍历：对每⼀个可能的分⽀路径深⼊到不能再深⼊为⽌，⽽且每个结点只能访问⼀次。⽽⼆叉树的深度优先遍历分为先序遍历，中序遍历和后续遍历。先序遍历：先访问根，在访问左⼦树，最后访问右⼦树，总结就是“根左右”；中序遍历：先访问左⼦树，再访问根，最后访问右⼦树，总结就是“左根右”；后序遍历：先访问左⼦树，再访问右⼦树，最后访问根，总结就是“左右根”；通常采⽤递归的⽅式实现遍历，⾮递归⽅式需要结合栈（后进先出）的特点实现。⼴度优先遍历：⼜叫层次遍历，从上往下对每⼀层依次访问，在每⼀层中，从左往右（也可以从右往左）访问结点，访问完⼀层就进⼊下⼀层，直到没有结点可以访问为⽌。⼴度优先遍历的⾮递归的通⽤做法是采⽤队列（先⼊先出）。⼆叉查找树⼆叉查找树（Binary Search Tree），或者是⼀颗空树，或者是具有下列性质的⼆叉树：1、若它的左⼦树不空，则其左⼦树上的所有结点的值均⼩于它根结点的值；2、若它的右⼦树不空，则其右⼦树上的所有结点的值均⼤于它根结点的值；3、它的左、右⼦树也分别为⼆叉查找树。树形结构就是利⽤⼆叉查找树这种特性来实现快速查询，效率上和线性表的⼆分查找差不多。数据结构⾯试篇