荐 Java中常见的数据结构API的特点及分析

程序员文章站 2022-11-30 15:12:32

数据结构ArrayList 和 CopyOnWriteArrayListArrayList利用可变长(更换数组)数组实现的线性表数据结构创建默认的ArrayList, 其内部封装了一个对象数组elementData, 默认长度为0在添加第一个元素时候, ArrayList会立即分配数组空间, elementData长度为10. 数据添加到数组elementData的第一个元素中.添加第二个元素时候, 元素按照顺序存储到数组elementData中当数组容量不够时候, ArrayList会进行...

数据结构

红黑树

1)什么是红黑树?

是一个自平衡的排序二叉树。

注：自平衡指的向红黑树当中添加节点、删除节点或者改节点的值的时候，该二叉树始终保持平衡，不会发生失衡现象。
荐
Java中常见的数据结构API的特点及分析

2）红黑树的特点

荐
Java中常见的数据结构API的特点及分析
这些约束强制了红黑树的关键性质: **从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。**结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

3) 平衡二叉树的性质：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

区别：
1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

ArrayList 和 CopyOnWriteArrayList

ArrayList

利用可变长(更换数组)数组实现的线性表数据结构

创建默认的ArrayList, 其内部封装了一个对象数组elementData, 默认长度为0
在添加第一个元素时候, ArrayList会立即分配数组空间, elementData长度为10. 数据添加到数组elementData的第一个元素中.
添加第二个元素时候, 元素按照顺序存储到数组elementData中
当数组容量不够时候, ArrayList会进行扩容, 扩容到1.5倍
插入元素时候, 数组中元素会向后移动位置, 然后将新元素插入到数组中

实验: 研究 StringBuilder中字符数组的管理策略, 一个字符一个字符的插入数据.

线程安全性问题

ArrayList (1.2)有线程安全性问题, 在多线程并发情况下, 不要使用! 因为没同步锁性能好.
Vector 是传统(1.0)Java集合, 是线程安全的, 有同步锁, 性能稍差. 遍历时候不能更改数据
CopyOnWriteArrayList(1.5) 提供的, 线程安全, 在写和遍历时候会创建数组副本, 利用副本遍历\修改, 并发遍历,同时可以并发修改. 具有好的并发安全性. 因为有数组复制, 会消耗一定内存空间.

结论: 方法中单线程情况下使用 ArrayList, 多线程并发访问使用 CopyOnWriteArrayList

经典面试题目: 那个List集合可以遍历时候并发修改?

荐
Java中常见的数据结构API的特点及分析

LinkedList

Java 8 中不再是双向循环链表, 改成了双向链表.

创建LinkedList, 内部没有数据, size为0, first头结点为null, last尾结点为null
添加第一个元素时候, first和last同时引用一个Node类型结点
添加第二个元素时候, first引用第一个Node, last引用最后一个Node, Node之间有双向引用

双向链表的优点: 收尾查询和修改性能好, 中部元素的修改查询, 性能最差!

荐
Java中常见的数据结构API的特点及分析

List操作性能

ArrayList		头部	中部	尾部
	add() 插入	慢	居中	快
	get() 查找	快	快	快
	delete() 删除	慢	居中	快
LinkedList		头部	中部	尾部
	add() 插入	快	慢	快
	get() 查找	快	慢	快
	delete() 删除	快	慢	快

使用原则:

读取的多, 修改少, 就使用ArrayList,
如果头尾操作多, 使用LinkedList
没有原则情况下, 请优先使用 ArrayList

错误的说法: ArrayList 读取性能好, 修改性能差, LinkedList修改性能好, 读取性能差

Java 中, 什么查询最快

根据数组下标, 查找数组的元素, 是Java中天下第一快的操作!

数组和ArrayList 的区别:

数组可以存储数据类型一致的一组数据, 没有提供操作算法, 使用数组需要自行编写算法, 使用数组编码的专用算法, 性能最佳!

ArrayList也可以存储一组数据, 其内部也是数组, 还提供操作算法, 使用方便. 通用算法好处是使用方便, 算法是经过检验的, 非常可靠.

如果期望高性能, 使用数组, 如期望高开发效率, 使用Arraylist

错误的说法: 数组是定长的, ArrayList是变长的!

HashMap 和 ConcurrentHashMap

HashMap

HashMap 中利用了数组下标查询快的特点, 实现根据key高效查询Value
散列表为了提高性能, 避免在散列桶中进行顺序查询, 设置了加载因子, 当元素数量超过加载因子(3/4)约定的门槛数量, 就进行数组扩容, 扩容以后元素重新散列, 可以大大减少散列值冲突问题
- 默认的加载因子 75%
- 比较时候, 计算出门槛: 数组大小*75% 得到门槛
- 如果元素数组超过门槛, 就进行扩容, 并且重新散列
- 扩容为2倍
创建散列表时候, 会在其内部创建一个数组
- 默认时候, 创建一个16个元素的数组
保存数据时候:
- 根据key的hashCode, 计算出一个数组下标, 将数据保存到下标对应的数组元素
- 根据key的hashCode映射到数组下标时候, 会出现重复情况, 利用equals检查key是否重复
- 重复时候, 散列表会利用链表存储数据, 此链表被称为散列桶
- 散列桶中的元素, 只能顺序查询, 可能会产生性能瓶颈,
- 为了避免出现大量的散列桶链表, 当元素数量达到数组的75%的时候, 进行数组扩容, 扩容后, 出现散列值冲突机会大大减少.
- Java 8 为应付大数据量, 在散列桶元素大于等于8个以后, 会将链表转换为红黑树, 提升查找性能.
红黑树插入为O(lgn),查询为O(lgn)，链表插入为O(1)，查询为O(n)。个数少时，插入删除成本高，用链表；个数多时，查询成本高，用红黑树。需要定一个值，比这个值大就转红黑树，比这个值小就转链表，而且要避免频繁的转换。根据泊松分布，在负载因子0.75（HashMap默认）的情况下，单个hash槽内元素个数为8的概率小于百万分之一，将7作为一个分水岭，等于7时不做转换，大于等于8才转红黑树，小于等于6才转链表。
查找时候
- 根据key的hashCode, 计算出数组下标位置, 再利用下标到数组取得数据, 利用equals确认是否成功找到数据
- 如果有散列桶, 就在散列桶中查找, 使用equals比较每个key
因为保存和查找时候, 本质上都用了数组下标查找数据, 所以其速度非常快.
因为其查询是根据key映射到下标, 进行查询, 不会进行元素遍历查询, 查询数据和数据量无关.

HashCode是什么?

hashCode() 是Java的设计者,为让Java所有对象, 都支持散列表算法,而设计的方法. hashCode是为散列表设计的方法!

散列表利用hashCode() 的值快速计算出数组下标!

hashCode方法的实现原则:

- 请成对的重写 hashCode和equals方法!

当两个对象相等equals比较结果为true时候, 这个两个对象必须有相同的hashCode
当两个对象不相等 equals比较结果为false时候, 这个两个对象尽可能不同的hashCode, 也就是说, 两个对象不等时候, 可能存在相同的hashCode!
hashCode 的值要稳定!
hashCode不能用于比较两个对象是否相等! 在散列表中只能使用hashCode计算数组下标位置, 不能用于判断是否找到key, 散列表每次查找, 添加都会最终调用 equals判断是否找到key!
简单说散列表中: 先利用hashCode计算位置, 在利用equals检查是否找到key

如果不很好的成对重写方法, 将造成散列表工作异常!
荐
Java中常见的数据结构API的特点及分析

public class ＨashMapDemo {

	public static void main(String[] args) {
		Map<String, Integer> map = new HashMap<>();
		map.put("Tom", 1);
		map.put("Jerry", 2);
		map.put("Andy", 3);
		map.put("Mac", 4);
		map.put("Apple", 5);
		map.put("Black", 6);
		map.put("John", 7);
		map.put("熊大", 8);
		map.put("熊二", 9);
		map.put("光头强", 10);
		map.put("范传奇", 11);
		map.put("成恒", 12);
		map.put("程祖红", 13);
		map.put("李大嘴", 14);
		map.put("白展堂", 15);
		map.put("莫小贝", 16);
		map.put("童老板", 17);
		
	}

}

ConcurrentHashMap

HashMap 不是线程安全的类, 因为没有加锁, 性能好

Hashtable 是Java早期提供的散列表, 线程安全,所有方法用同一把锁, 性能不好

ConcurrentHashMap Java 5 提供的并发版本的散列表, Java 8 中其有多把锁, 每个散列桶一把, 因为采用分段加锁, 并发好. 而且并发安全. 适合在并发情况下使用!

荐
Java中常见的数据结构API的特点及分析
经典面试题目: 多线程并时候使用哪个散列表好?

答案: 使用ConcurrentHashMap, 分段加锁, 并发好.

经典面试题目: HashMap 和 Hashtable 区别 ?

答案: HashMap 非线程安全,性能好, Hashtable 线程安全, 性能不好, 建议使用ConcurrentHashMap

经典面试题目: HashMap 和 ConcurrentHashMap 区别 ?

答案: HashMap 非线程安全,性能好. ConcurrentHashMap 线程安全, 适合多线程并发时候使用

BlockingQueue 阻塞队列

荐
Java中常见的数据结构API的特点及分析

阻塞队列用途:

可以实现线程之间数据通信: 一个线程将数据通过阻塞队列发生到另外一个线程
调和数据生产和数据消费的矛盾:
- 数据生产时快时慢, 数据消费需要稳定的速度
- 数据生产很快, 数据消费很慢

经典面试题目: 如何解决数据"生产者和消费者"的矛盾(问题)

答案: 使用阻塞队列, 数据生产以后插入队列, 数据消费从队列中取出.

如何处理消峰去谷: 小规模的使用阻塞队列, 大规模使用队列服务器

播放器的原理：
荐
Java中常见的数据结构API的特点及分析

本文地址：https://blog.csdn.net/EdwardWH/article/details/107137444

上一篇：联想美国黑五打6.5折：国内双11五折起！

下一篇：螃蟹蒸多少时间就可以吃了?怎样做最好吃呢？

荐 Java中常见的数据结构API的特点及分析

数据结构

红黑树

1)什么是红黑树?

2）红黑树的特点

3) 平衡二叉树的性质：

ArrayList 和 CopyOnWriteArrayList

ArrayList

线程安全性问题

LinkedList

List操作性能

Java 中, 什么查询最快

HashMap 和 ConcurrentHashMap

HashMap

HashCode是什么?

ConcurrentHashMap

BlockingQueue 阻塞队列

荐 Java中常见的数据结构API的特点及分析

Java基础-----与Java集合相关的数据结构&Java集合特点、底层实现、是否线程安全&集合使用选取原则&集合的常见方法及遍历方式

荐 Java中常见的数据结构API的特点及分析