1. Java中有哪些容器?
Java的容器可以分为单值集合和键值对集合,这两种集合的父分别是Collection和Map这两大类
而Colletion又可以分为有List、Set这些都是存储一个元素的,其中,List一族的集合可以存储重复的元素,而Set不可以存储重复的元素,下面来讲讲具体的实现类
List的实现类有ArrayList、LinkedList、Vector、Stack
Set的实现类有HashSet、TreeSet、LinkedHashSet
Map的实现类有HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap、HashTable
2. 怎么选择这些集合?
首先按照存储对象分类,如果存储的对象是一个对象,也就是存储并不要求能使用{key=>value}寻址的,那么在这样的情况下,就可以使用单值集合,这样又分为以下的情况
当存储的元素比较少删除同时插入都是在尾部的话,并且要满足以O(1)的时间查询的时候,这时候就可以用ArrayList
当存储的元素比较少删除同时插入都是在头部或者尾部的话,并且不经常查询中间的数据的时候,这时候就可以使用LinkedList了
当存储的元素是单值元素,并且在要求这个集合中只能够存储一个相同的元素的时候,这时候就要选用Set类的
当是普通的寻址查询的话,那么这时候使用HashSet就可以了
当要求遍历的时候要以插入的顺序遍历的时候,这时候使用LinkedHashSet就可以了
当要求集合中的元素是有序的时候,这时候就可以使用TreeSet了
当存储的元素需要满足某些特定的规则,比如说先进先出,后进先出这样的规则的时候,就需要使用队列或者是栈结构了
3. Collcetion和Collcetions有什么区别?
Collection是一个接口,它定义了集合容器的基本操作,比如说add()、size()这些都是由它来抽象定义类的
Collcetions是一个包装类,包含有很多静态的方法,无法被实例化,可以对执行排序Collections.sort(list)
4. 讲讲List/Set/Map有什么区别?
这三个集合的区别主要可以从以下方面进行讲述,元素是否有序?是否允许元素重复?
首先先来讲讲有序是啥意思?有序就是说元素在集合中存储的顺序它是按照插入顺序的,List可以保证插入的元素是有序的,同时允许元素重复,Set的话它的实现思路通常是基于hash()来实现的,因此存储的顺序通常不是由插入顺序来决定的,而是由hashCode()来实现的,但是也可以通过链表的方式,通过链表寻址的方式来确定这些方式,而Map的话它也是无序的,为什么无序和Set为什么无序是一样的
接着来讲讲是否允许元素重复,直接说结论,List可以重复,而Set和Map是不可重复的
这和add()和put()的逻辑有关,add()的话通常来说就是分配一块新的内存空间,然后将数据存进去
而put()的逻辑则是计算一个hash(),然后根据这个hash()来计算下标来决定你这个东西要放到哪里,姑且不谈hashCode()相同的场景,在相同的hash()的情况下,你的这个值是会被覆盖,具体逻辑是:当put()一个元素的时候,如果当前位置上没有这个key,那么就新建插入,否则就覆盖了
5. HashMap和HashTable的区别
主要的区别可以从三个方面进行讲述:
(1)第一个方面可以从线程安全方面进行讲述,HashMap是线程不安全的,而HashTable是线程安全的,这是因为HashMap默认并且推荐在单线程环境下使用,因此对于多线程并发操作没有做任何的保护,而HashTable底层因为对每一个方法使用了synchronized()关键字进行修饰,因此在这样的情况下,它是线程安全的
(2)第二方面可以从键值对的存储的角度上进行讲述,HashMap可以存储空key和空value,而HashTable不能够存储空key和空value
原因是什么?
这是因为在多线程环境下,空key和空value会造成歧义,当
get(key)这个方法的时候,如果这时候返回一个null的时候,这时候会有两种情况:
- 本来就不存在你这个
key=>value的映射- 你有这个key=>value的映射,但是value为null
那么这时候就要调用
containsKey(key)来判断你的key是否存在了,如果这时候有一个线程调用了put(key,null)的方法,那么这时候就会导致一个问题如果线程并发下,如果先执行了
containsKey(key),再执行put(key,value),这时候就会返回false如果先执行了
put(key,value),再执行containsKey(key),那么就会返回true这时候就产生了歧义了,产生了并发测试环境下,代码路径的不稳定性,解决办法也简单,就是在代码块中加入
synchronized来确保原子性
问题,那么为什么HashMap又允许你这个
key,value为空呢?这样就不会产生歧义了么?由于是单线程,那么在判断
contains(key)的时候,这时候就不会产生歧义,包含就是包含,代码的执行逻辑是稳定的
6. LinkedHashMap是什么?是如何实现的?
LinkedHashMap继承自HashMap,因此它本质上还是一个HashMap,但是我们知道,你这个HashMap中的元素组织起来是无序的,它的底层还是基于数组+红黑树来实现的,LinkedHashMap在这个基础上,将你的HashMap中的元素根据插入顺序,组织成了一个双向链表,在遍历的时候,只需要获取到头部元素,就可以遍历到全表了
7. 如何确定使用HashMap和TreeMap?
对于在Map中插入、删除、定位一个元素这种操作,HashMap是最好的选择,因为相对而言,HashMap的插入会更快一些,但是如果对一个key需要实现一个有序的遍历,那么TreeMap就最好了
总结一下:就是需要实现一个{key=>value}的映射,同时你需要在遍历的时候,要按照你定义的规则进行排序,这样的话最好就使用这个了
8. 讲讲HashMap的实现原理是怎么样的?
简单讲一下,首先从HashMap的底层实现来看,它的底层是基于数组+链表/红黑树实现的,后面讲的这个链表就是用来解决哈希冲突的,HashMap最关键的两个方法就是put()和get()方法,通过这两个方法的实现逻辑,我们就可以知道它的原理是怎么样的
put()流程,首先先对输入的key进行一个key.hashCode()的计算,然后通过一个叫做扰动函数的处理后,得到一个hash值,通过这个hash值来确定你这个元素要存放在数组中的哪个位置上
如果发现你这个数组这个位置上的这个bucket不是空的,那么就要遍历这个链表或者红黑树,如果上面有元素和当前的key是相同的,那么就覆盖这个value
如果发现你这个数组这个位置上的这个bucket是空的,那么就直接插入
get()流程,首先对输入的key执行相同的操作,也就是说先进行一个key.hashCode()，然后同一个叫做扰动函数的处理,得到一个hash,根据你这个值来确定你这个元素在哪个位置上,如果有链表,那么就顺着查,如果顺着查有key'==key 的话,那么就直接返回,否则遍历完返回空
说说红黑树的转换逻辑
转换逻辑会有两个参数,第一个参数是单个链表中的长度阈值,第二参数是数组的长度
- 将链表转换成红黑树之前会先判断,如果当前数组的长度小于了64,那么就会先进行数组扩容,而不是转换为红黑树
- 将链表转换为红黑树,条件是这样:当数组的长度大于等于64,并且当前看表的长度大于8,就会变化成红黑树
- 当树中的元素小于6的时候,又会退化为链表
讲讲这些参数的由来
- 首先第一个6-8这个参数怎么来的
还有选择6和8，中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。
9. HashSet是如何检查重复的
在JDK1.8的源码中,HashSet的add()方法只是简单的调用了HashMap的put()方法,并且判断了一下返回值,将是否有重复元素的反馈到用户
public boolean add(E e){
return map.put(e,PRESENT) == null;
// 这个意思就是讲,当有重复元素的时候就返回false的
// 然后覆盖掉这个对象
}
