![](https://csdnimg.cn/release/download_crawler_static/87375870/bg1.jpg)
数据结构知识梳理
1、常用数据结构简介
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素间的
关系组成。常用的数据有:数组、栈、队列、链表、树、图、堆、散列表。
1)数组:在内存中连续存储多个元素的结构。数组元素通过下标访问,下标从 0 开始。优
点:访问速度快;缺点:数组大小固定后无法扩容,只能存储一种类型的数据,添加删除操
作慢。适用场景:适用于需频繁查找,对存储空间要求不高,很少添加删除。
2)栈:一种特殊的线性表,只可以在栈顶操作,先进后出,从栈顶放入元素叫入栈,从栈
顶取出元素叫出栈。应用场景:用于实现递归功能,如斐波那契数列。
3)队列:一种线性表,在列表一端添加元素,另一端取出,先进先出。使用场景:多线程
阻塞队列管理中。
4)链表:物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表的
指针地址实现,每个元素包含两个结点,一个是存储元素的数据域,一个是指向下一个结点
地址的指针域。有单链表、双向链表、循环链表。优点:可以任意加减元素,不需要初始化
容量,添加删除元素只需改变前后两个元素结点的指针域即可。缺点:因为含有大量指针域,
固占用空间大,查找耗时。适用场景:数据量小,需频繁增加删除操作。
5)树:由 n 个有限节点组成一种具有层次关系的集合。二叉树(每个结点最多有两个子树,
结点的度最大为 2,左子树和右子树有顺序)、红黑树(HashMap 底层源码)、B+树(mysql
的数据库索引结构)
6)散列表(哈希表):根据键值对来存储访问。
7)堆:堆中某个节点的值总是不大于或不小于其父节点的值,堆总是一棵完全二叉树。
8)图:由结点的有穷集合 V 和边的集合 E 组成。
2、并发集合了解哪些?
1)并发 List,包括 Vector 和 CopyOnWriteArrayList 是两个线程安全的 List,Vector 读写操作
都用了同步,CopyOnWriteArrayList 在写的时候会复制一个副本,对副本写,写完用副本替
换原值,读时不需要同步。
2)并发 Set,CopyOnWriteArraySet 基于 CopyOnWriteArrayList 来实现的,不允许存在重复的
对象。
3)并发 Map,ConcurrentHashMap,内部实现了锁分离,get 操作是无锁的。