image frame

无论走到哪里,
都应该记住,
过去都是假的,
回忆是一条没有尽头的路。
一切以往的春天都不复存在,
就连那最坚韧而又狂乱的爱情,
归根结底也不过是转瞬即逝的现实,
唯有孤独永恒。

——加西亚·马尔克斯

Java FAQ

非线程安全集合

java.util 包下的非线程安全集合

1. ArrayList与LinkedList的实现和区别?

  • 结构上的区别:
       ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
  • 性能上的区别:

查询
ArrayList是随机访问(random access)策略,而LinkedList是不支持快速的随机访问的(访问链表中的某个元素时,就必须从链表的一端开始沿着连接方向一个一个元素地去查找,直到找到所需的元素为止)。对一个LinkedList做随机访问所消耗的时间与这个表的大小是成比例的。而相应的,在ArrayList中进行随机访问所消耗的时间是固定的。

增删
1). 若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。
2). 若是批量插入或删除数据:
  ArrayList 是基于数组实现的,而数组是一块连续的内存空间,当在表的前面或中间插入或删除元素时,所有已经存在的元素都会后移,这就意味着数据移动和复制上的开销,当在表的后面插入或删除元素时,ArrayList和LinkedList数据量小时速度相差无几,但数据量较大时ArrayList的速度快。在末尾插入或删除数据,arraylist的速度比linkedlist的速度反而要快。注:其实在前方插入时,ArrayList可以使用后方插入,最后再使用Collections.reverse()方法反转,速度比LinkedList快。
   LinkedList 插入或删除数据则只是简单的未这个元素分配一个记录,然后调整两个连接,在表的尾端插入数据与在任意位置插入数据是一样的,不会因为插入的位置靠前而导致插入的方法性能降低。
   遍历列表:最简便的ForEach循环并没有很好的性能表现,综合性能不如普通的迭代器,而是用for循环通过随机访问遍历列表时,ArrayList表项很好,但是LinkedList的表现却无法让人接受,甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时,总会进行一次列表的遍历操作。性能非常差,应避免使用。

总结:
  1、在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在LinkedList的中间插入或删除一个元素的开销是固定的。
  2、ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
  3、LinkedList不支持高效的随机元素访问。
  4、ArrayList的查询效率比较高,增删动作的效率比较差,适用于查询比较频繁,增删动作较少的元素管理的集合。
   LinkedList的查询效率低,但是增删效率很高。适用于增删动作的比较频繁,查询次数较少的元素管理集合。

2. HashMap 数据结构? hash冲突如何解决(链表和红黑树)? 扩容时机? 扩容时避免rehash的优化?

  • HashMap是一种散列表,采用(数组 + 链表 + 红黑树)的存储结构
  • hash冲突时,使用链表和红黑树来解决
  • 设置好初始化容量,初始容量(expectedSize / 0.75F + 1.0F)

3. LinkedHashMap 基本原理? 哪两种有序? 如何用来实现 LRU 缓存策略?

  • LinkedHashMap可以看成是 LinkedList + HashMap
  • LinkedHashMap继承HashMap,拥有HashMap的所有特性,并且额外增加了按一定顺序访问的特性
  • 如果accessOrder为false,则可以按插入元素的顺序遍历元素
  • 如果accessOrder为true,则可以按访问元素的顺序遍历元素
  • 如果accessOrder为true,就可以实现了 LRU 缓存策略

4. TreeMap 数据结构?key对象为什么必须要实现Compare接口? 如何用它实现一致性哈希?

  • TreeMap的存储结构是一棵红黑树
  • TreeMap中的元素是有序的,按key的顺序排列
  • tailMap 方法可以找到大于等于目标 key 的元素,利用这一特性,可以实现一致性哈希

线程安全集合

java.util.concurrent 包下的线程安全集合


title: Java FAQ
date: 2020-02-10 17:52:19
comments: true #是否可评论
toc: true #是否显示文章目录
categories: Java
tags: [Java, faq]


非线程安全集合

java.util 包下的非线程安全集合

1. ArrayList与LinkedList的实现和区别?

  • 结构上的区别:
       ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
  • 性能上的区别:

查询
ArrayList是随机访问(random access)策略,而LinkedList是不支持快速的随机访问的(访问链表中的某个元素时,就必须从链表的一端开始沿着连接方向一个一个元素地去查找,直到找到所需的元素为止)。对一个LinkedList做随机访问所消耗的时间与这个表的大小是成比例的。而相应的,在ArrayList中进行随机访问所消耗的时间是固定的。

增删
1). 若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。
2). 若是批量插入或删除数据:
  ArrayList 是基于数组实现的,而数组是一块连续的内存空间,当在表的前面或中间插入或删除元素时,所有已经存在的元素都会后移,这就意味着数据移动和复制上的开销,当在表的后面插入或删除元素时,ArrayList和LinkedList数据量小时速度相差无几,但数据量较大时ArrayList的速度快。在末尾插入或删除数据,arraylist的速度比linkedlist的速度反而要快。注:其实在前方插入时,ArrayList可以使用后方插入,最后再使用Collections.reverse()方法反转,速度比LinkedList快。
   LinkedList 插入或删除数据则只是简单的未这个元素分配一个记录,然后调整两个连接,在表的尾端插入数据与在任意位置插入数据是一样的,不会因为插入的位置靠前而导致插入的方法性能降低。
   遍历列表:最简便的ForEach循环并没有很好的性能表现,综合性能不如普通的迭代器,而是用for循环通过随机访问遍历列表时,ArrayList表项很好,但是LinkedList的表现却无法让人接受,甚至没有办法等待程序的结束。这是因为对LinkedList进行随机访问时,总会进行一次列表的遍历操作。性能非常差,应避免使用。

总结:
  1、在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动;而在LinkedList的中间插入或删除一个元素的开销是固定的。
  2、ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间。
  3、LinkedList不支持高效的随机元素访问。
  4、ArrayList的查询效率比较高,增删动作的效率比较差,适用于查询比较频繁,增删动作较少的元素管理的集合。
   LinkedList的查询效率低,但是增删效率很高。适用于增删动作的比较频繁,查询次数较少的元素管理集合。

2. HashMap 数据结构? hash冲突如何解决(链表和红黑树)? 扩容时机? 扩容时避免rehash的优化?

  • HashMap是一种散列表,采用(数组 + 链表 + 红黑树)的存储结构
  • hash冲突时,使用链表和红黑树来解决
  • 设置好初始化容量,初始容量(expectedSize / 0.75F + 1.0F)

3. LinkedHashMap 基本原理? 哪两种有序? 如何用来实现 LRU 缓存策略?

  • LinkedHashMap可以看成是 LinkedList + HashMap
  • LinkedHashMap继承HashMap,拥有HashMap的所有特性,并且额外增加了按一定顺序访问的特性
  • 如果accessOrder为false,则可以按插入元素的顺序遍历元素
  • 如果accessOrder为true,则可以按访问元素的顺序遍历元素
  • 如果accessOrder为true,就可以实现了 LRU 缓存策略

4. TreeMap 数据结构?key对象为什么必须要实现Compare接口? 如何用它实现一致性哈希?

  • TreeMap的存储结构是一棵红黑树
  • TreeMap中的元素是有序的,按key的顺序排列
  • tailMap 方法可以找到大于等于目标 key 的元素,利用这一特性,可以实现一致性哈希

线程安全集合

java.util.concurrent 包下的线程安全集合

  • © 2015-2020 Andrew
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信