数据结构

heaboy2025/9/22大约 4 分钟

数据结构

数组

数组的特性
存储空间是连续的
长度是不可变的
只能存储相同的类型(不严谨)
可以通过下标访问数组的内容 a[10] 复杂度是O1
每个元素的默认是为'零'值 0 null false -> 一个对象的基本的数据域的初始化也是这样的
- Student 类中的username属性默认值
我们的笔试题动态规划 dp[][] 我们要会使用
ArrayList
- 自动扩容
- 长度有限吗(int的最大值)
- 默认初始容量是10
- 扩容 1.5倍
- 扩容的时机满了才扩容
- 线程不安全的
- new ArrayList（100）这里边的值有啥用
  - 减少自动扩容的次数
- 缩容手动调用的会缩到现有的元素个数
做栈
- 先进后出
- 会有一种题就是abcdefg顺序进栈不可能的出栈顺序是什么选择题
做队列
- 先进先出

练习

用双栈实现一个队列
用双队列实现一个栈

链表

查找麻烦
插入和删除简单
可以定点删除和插入
非连续的
无限定长度
节点类结构体
删除是用指针指向其他的节点
线程不安全
查询效率不好 On
单链表
双向链表
```
LinkedList
双向链表
```
头节点有还是没有头节点
自己实现一个链表完成链表的反转

map⭐

key value
HashMap（重中之重） ⭐ 震惊！史上最全最深入小白专属 hashmap 深度源码解析
- 查找时间复杂度都要小 O1 无限接近
- 线程不安全的
- 1.7
  - 数组+ 链表
- 1.8
  - 数组 +链表/红黑树
  - 进化的阈值 8 并且数组长度》=64
  - 退化的阈值 6
- 数组长度是多少 16
- 每次扩容都会扩容成2的n次方数值当然也就是扩容两倍
  - 扩容因子是0.75
HashTable
- 线程安全的
- 对整个结构加锁性能不好
ConcurrentHashMap 线程安全的 Juc包下的
- 1.7
- 1.8
- image-20200727163100466
- ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
  底层数据结构：
  - JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
  - 实现线程安全的方式（重要）：
    - ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
    - 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表/红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
- 要读部分源码