Set
- 首先Set是一个接口,它里面封装了一些基本的方法,比如:add(),size(),isEmpty(),remove,主要的实现在于HashSet,TreeSet,AbstractSet,SortedSet这些类
HashSet的面试题
- HashSet的特点?
答: 线程不安全,基于哈希表实现,快速查找,没有顺序,失去了元素的插入的顺序信息,也就是说使用Iterator遍历HashSet得到的值是不确定的.set的值可以为null. - HashSet的底层是什么?
答:HashMap. - 既然是HashMap为什么Map是key,value,而set是一个值呢?
答:set的值相当于map中的key,而map的value是一个Object的常量,默认new了一个Object(),所有的添加操作,key不同,value相同. - 为什么Set可以去重?
答: - 那为什么map中的值必须是一个常量而不是为null?
答: 在HashMap里面确实是可以添加value为空进map里面,但是在set里面,它还有一个重要的作用就是判断删除操作是否成功.见下题. - 为什么
Object PRESENT = new Object();它的作用是什么?
答:判断删除操作是否为空,public boolean remove(Object o) {return map.remove(o)==PRESENT; },删除是否成功,就是看删除的这个值是否为那个常量,如果设置value为空,就不能判断删除是否成功.不能判断删除的是哪个key的value.
LinkedHashSet
- LinkedHashSet继承了HashSet,它最主要的功能就是实现了有序,即按照add的顺序,依次输出,可以为null,不能重复.
TreeSet
HashMap的面试题
HashMap的put方法:
简答:首先取得哈希值,通过哈希值获得一个数组的下标,看对应的数组节点里面是否为空,为空则插入,不为空,key如果一样,则覆盖当前的value;如果key值不一样,看节点类型,是树,执行红黑树的插入操作.是链表,则遍历链表,看key一样吗,一样就覆盖,不一样,在链表后面插入一个节点<k,v>,如果链表元素个数超过8,并且数组的⻓度⼤于等于64时才会将链表转为红⿊树。如果数组的长度大于阈值,则扩容.HashMap的扩容?
创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。为什么HashMap的默认初始容量为2的幂?
①、设置为2的幂的方,是为了更快速的得到它数组的下表
②、通常如果一个键值对<K,V>,通过K获得哈希值,通过与容量进行取模来得到数组的下表,即hashCode(key) % cap,但是如果哈希值是一个负数,我们要先变成正数,然后取模,效率比较低.
③、但是如果我们设置初始容量为2的幂,-1操作才能拿到低位全部是1的值,然后与哈希值进行&运算,运算结果就是数组的下表,更快速,而且散列均匀.Java 8 对于 7 有了那些改进?为什么?
①、在java 1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）
②、发生hash碰撞时，java 1.7 会在链表的头部插入，而java 1.8会在链表的尾部插入为什么选择红黑树?不选择二叉树
①、红黑树是一个平衡二叉树,他会在你插入节点的过程中,变换结构,使它两边的叶子节点数量一致
②、二叉树在极端的情况下,会变成一个链表,性能降低什么时候链表转换为红黑树?
HashMap的Hash算法?
HashMap 的 table 的容量如何确定？loadFactor 是什么？ 该容量如何变化？这种变化会带来什么问题？
①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；
②、loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；
③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）
④、如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。HashMap与Hashtable比较
①. HashTable的key和value都不能为空;HashMap的key和value都可以为空,但是key只能有一个为空,因为要key值要唯一.
②. HashTable是线程安全的,但是效率较低,他对整个的表都进行了加锁;HashMap线程不安全,但是效率高
③. Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。创建时，如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说Hashtable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小。是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。
④. HashTable计算hash先进行与运算,然后进行除法运算,HashMap直接位运算.HashMap与ConcurrentHashMap比较
①. ConcurrentHashMap 和 HashMap 实现上类似，最主要的差别是 ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）
.默认是16个Segment,Segment是继承ReentrantLock来进行加锁的,它每次需要加锁的时候只锁一个Segment,Segment有16个,那么他就有16个并发
②.ConcurrentHashMapJDK 1.7 使用分段锁机制来实现并发更新操作，核心类为 Segment，它继承自重入锁 ReentrantLock，并发度与 Segment 数量相等。
JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。
③.ConcurrentHashMap的key和value都不能为空
