非线程安全集合

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 包下的线程安全集合