是一个自平衡的排序二叉树。
注: 自平衡指的向红黑树当中添加节点、删除节点或者改节点的值的时候,该二叉树始终保持平衡,不会发生失衡现象。
这些约束强制了红黑树的关键性质: **从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。**结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。
区别:
1、红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。
2、平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。
利用可变长(更换数组)数组实现的线性表数据结构
实验: 研究 StringBuilder中字符数组的管理策略, 一个字符一个字符的插入数据.
结论: 方法中单线程情况下使用 ArrayList, 多线程并发访问使用 CopyOnWriteArrayList
经典面试题目: 那个List集合可以遍历时候并发修改?
Java 8 中不再是双向循环链表, 改成了双向链表.
双向链表的优点: 收尾查询和修改性能好, 中部元素的修改查询, 性能最差!
ArrayList | 头部 | 中部 | 尾部 | |
---|---|---|---|---|
add() 插入 | 慢 | 居中 | 快 | |
get() 查找 | 快 | 快 | 快 | |
delete() 删除 | 慢 | 居中 | 快 | |
LinkedList | 头部 | 中部 | 尾部 | |
add() 插入 | 快 | 慢 | 快 | |
get() 查找 | 快 | 慢 | 快 | |
delete() 删除 | 快 | 慢 | 快 |
使用原则:
错误的说法: ArrayList 读取性能好, 修改性能差, LinkedList修改性能好, 读取性能差
根据数组下标, 查找数组的元素, 是Java中天下第一快的操作!
数组和ArrayList 的区别:
数组可以存储数据类型一致的一组数据, 没有提供操作算法, 使用数组需要自行编写算法, 使用数组编码的专用算法, 性能最佳!
ArrayList也可以存储一组数据, 其内部也是数组, 还提供操作算法, 使用方便. 通用算法好处是使用方便, 算法是经过检验的, 非常可靠.
如果期望高性能, 使用数组, 如期望高开发效率, 使用Arraylist
错误的说法: 数组是定长的, ArrayList是变长的!
HashMap 中利用了数组下标查询快的特点, 实现根据key高效查询Value
散列表为了提高性能, 避免在散列桶中进行顺序查询, 设置了加载因子, 当元素数量超过加载因子(3/4)约定的门槛数量, 就进行数组扩容, 扩容以后元素重新散列, 可以大大减少散列值冲突问题
创建散列表时候, 会在其内部创建一个数组
保存数据时候:
红黑树插入为O(lgn),查询为O(lgn),链表插入为O(1),查询为O(n)。个数少时,插入删除成本高,用链表;个数多时,查询成本高,用红黑树。需要定一个值,比这个值大就转红黑树,比这个值小就转链表,而且要避免频繁的转换。根据泊松分布,在负载因子0.75(HashMap默认)的情况下,单个hash槽内元素个数为8的概率小于百万分之一,将7作为一个分水岭,等于7时不做转换,大于等于8才转红黑树,小于等于6才转链表。
查找时候
因为保存和查找时候, 本质上都用了数组下标查找数据, 所以其速度非常快.
因为其查询是根据key映射到下标, 进行查询, 不会进行元素遍历查询, 查询数据和数据量无关.
hashCode() 是Java的设计者,为让Java所有对象, 都支持散列表算法,而设计的方法. hashCode是为散列表设计的方法!
散列表利用hashCode() 的值快速计算出 数组下标!
hashCode方法的实现原则:
- 请成对的重写 hashCode和equals方法!
如果不很好的成对重写方法, 将造成散列表工作异常!
public class HashMapDemo {
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);
}
}
HashMap 不是线程安全的类, 因为没有加锁, 性能好
Hashtable 是Java早期提供的散列表, 线程安全,所有方法用同一把锁, 性能不好
ConcurrentHashMap Java 5 提供的并发版本的散列表, Java 8 中其有多把锁, 每个散列桶一把, 因为采用分段加锁, 并发好. 而且并发安全. 适合在并发情况下使用!
经典面试题目: 多线程并时候使用哪个散列表好?
答案: 使用ConcurrentHashMap, 分段加锁, 并发好.
经典面试题目: HashMap 和 Hashtable 区别 ?
答案: HashMap 非线程安全,性能好, Hashtable 线程安全, 性能不好, 建议使用ConcurrentHashMap
经典面试题目: HashMap 和 ConcurrentHashMap 区别 ?
答案: HashMap 非线程安全,性能好. ConcurrentHashMap 线程安全, 适合多线程并发时候使用
阻塞队列用途:
经典面试题目: 如何解决数据"生产者和消费者"的矛盾(问题)
答案: 使用阻塞队列, 数据生产以后插入队列, 数据消费从队列中取出.
如何处理消峰去谷: 小规模的使用阻塞队列, 大规模使用队列服务器
播放器的原理:
本文地址:https://blog.csdn.net/EdwardWH/article/details/107137444
如对本文有疑问, 点击进行留言回复!!
[JVM学习之路]一、初识JVM,了解其结构、模型及生命周期
【JAVA并发编程】LinkedBlockingQueue原理
网友评论