欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

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

程序员文章站 2022-05-07 18:17:21
数据结构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

上一篇： JSP报错javax.servlet.jsp.JspException cannot be resolved to a type solution

下一篇： 荐 【Java】--创建线程方法之Callable

推荐阅读