原创

Java成神之路笔记之—Java集合容器必会知识点2

_________________________________________________________________________________

Java成神之路笔记之—Java集合容器必会知识点2

1 集合
  • 对象封装数据,对象多了也需要存储。集合用于存储对象。
  • 对象的个数确定可以使用数组,对象的个数不确定的可以用集合。因为集合是可变长度的。

2 集合和数组的区别
  • 数组是固定长度的;集合可变长度的。
  • 数组可以存储基本数据类型,也可以存储引用数据类型;集合只能存储引用数据类型。
  • 数组存储的元素必须是同一个数据类型;集合存储的对象可以是不同数据类型。

3 常用的集合类
Collection接口的子接口包括:Set接口和List接口
Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等
List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等

4 Java 容器分为 Collection 和 Map 两大类,Collection集合主要有List和Set两大接口
List:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
Set:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。
Map是一个键值对集合,存储键、值和之间的映射。 Key无序,唯一;value 不要求有序,允许重复。Map没有继承于Collection接口,从Map集合中检索元素时,只要给出键对象,就会返回对应的值对象。

5 集合框架底层数据结构
Arraylist: Object数组
LinkedList: 双向循环链表
HashSet(无序,唯一):基于 HashMap 实现的,底层采用 HashMap 来保存元素
LinkedHashSet: LinkedHashSet 继承与 HashSet,并且其内部是通过 LinkedHashMap 来实现的。
TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树。)
HashMap: JDK1.8之前HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突).JDK1.8以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间
LinkedHashMap:LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。
HashTable: 数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
TreeMap: 红黑树(自平衡的排序二叉树)

6 集合类线程安全
vector:就比arraylist多了个同步化机制(线程安全),因为效率较低,现在已经不太建议使用。
hashtable:Hashtable容器使用synchronized来保证线程安全
ConcurrentHashMap:使用的分段锁技术保证线程安全。

7 Iterator 怎么使用?有什么特点
Iterator 的特点是只能单向遍历,但是更加安全,因为它可以确保,在当前遍历的集合元素被更改的时候,就会抛出 ConcurrentModificationException 异常。使用Iterator.remove() 方法移除元素。

8 ArrayList、LinkedList 的优缺点
ArrayList底层是基于动态数组的。而LinkedList底层是基于双向链表的。
ArrayList必须是连续内存的,而LinkedList不要求连续内存。
ArrayList查询快,增加和删除慢;LinkedList增加和删除快,查询慢。
ArrayList 底层为动态数组,所以查询时是直接通过访问下标,查询效率高。而增加而删除时,为了保证内存的连续,增加和删除某一位置后,后方元素都得向前移动一位。所以增加删除慢。LinkedList底层为双向链表,不必保证内存上的连续,所以增删快,而查询时必须要经历从头到尾的遍历,所以查询慢。
两者线程都不安全

9 ArrayList 和 Vector 的区别
两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合
线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。
性能:ArrayList 在性能方面要优于 Vector。

10 如何实现数组和 List 之间的转换
  • 数组转 List:使用 Arrays. asList(array) 进行转换。
  • List 转数组:使用 List 自带的 toArray() 方法。

11 HashSet 的实现原理
HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,HashSet 中的add ()方法会使用HashMap 的put()方法。HashMap 的 key 是唯一的,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V。所以HashSet数据不会重复。

12 Queue
BlockingQueue(阻塞队列)是什么?
Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。

13 在 Queue 中 poll()和 remove()有什么区别?
相同点:都是返回第一个元素,并在队列中删除返回的对象。
不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。

14 HashMap 的实现原理
HashMap是基于哈希表的Map接口的非同步实现,底层是一个“链表散列”的数据结构,即数组和链表的结合体。
往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中,获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过8且数组长度大于64,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

15 拉链法的方式解决哈希冲突
拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

16 HashMap的扩容
HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时(默认扩容因子Load Factor为0.75),就调用resize方法进行扩容;每次扩展的时候,都是扩展2倍;扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。

17 HashMap是使用了哪些方法来有效解决哈希冲突的:
1. 使用链地址法(使用散列表)来链接拥有相同hash值的数据;
2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;
3. 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快;

18 HashMap的key有什么要求
需要重写hashCode()equals()方法;String、Integer等包装类更适合作为Hashmap的key,它们都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况,内部已重写了equals()hashCode()等方法,不容易出现Hash值计算错误的情况。

19 HashMap 与 HashTable 有什么区别?
1.线程安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap )。
2.效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。HashTable 基本被淘汰,不要在代码中使用它;
3.对Null key 和Null value的支持: HashMap 中,null 可以作为键,可以多个值为 null。 HashTable 不支持null键值,抛NullPointerException。
4.初始容量大小和每次扩充容量大小的不同:Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16,每次扩充容量变为原来的2倍。
5.底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时加入了红黑树,而HashTable没有这种结构。

20 TreeMap有什么特殊
TreeMap中的元素默认按照keys的自然排序排列。对Integer来说,其自然排序就是数字的升序;对String来说,其自然排序就是按照字母表排序;字符按照字节码(ascii)来排序。可以实现Comparator接口实现自定义排序规则。

21 ConcurrentHashMap
ConCurrentHashMap是线程安全的。
HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。
原理:在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化),JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发

22 Collection 和 Collections 有什么区别
java.util.Collection 是一个集合接口(集合类的一个顶级接口)。它提供了对集合对象进行基本操作的通用接口方法。其直接继承接口有List与Set。Collections则是集合类的一个工具类/帮助类,用于对集合中元素进行排序、搜索以及线程安全等各种操作。


_________________________________________________________________________________
正文到此结束
本文目录