撩课-Java每天10道面试题第6天

51.HashMap的实现原理

HashMap的主干是一个Entry数组。
Entry是HashMap的基本组成单元，
每一个Entry包含一个key-value键值对。

HashMap基于hashing原理，
我们通过put()和get()方法储存和获取对象。
当我们将键值对传递给put()方法时，
它调用键对象的hashCode()方法
来计算hashcode，
让后找到bucket位置来储存值对象。
当获取对象时，
通过键对象的equals()方法
找到正确的键值对，
然后返回值对象。
HashMap使用链表来解决碰撞问题，
当发生碰撞了，
对象将会储存在链表的下一个节点中。
 HashMap在每个链表节点中储存键值对对象。

当两个不同的键对象的hashcode
相同时会发生什么？ 
它们会储存在同一个bucket位置的链表中。
键对象的equals()方法用来找到键值对。

因为HashMap的好处非常多，
我曾经在电子商务的应用中使用HashMap作为缓存。
因为金融领域非常多的运用Java，
也出于性能的考虑，
我们会经常用到HashMap和ConcurrentHashMap。


HashMap由数组+链表组成的，
数组是HashMap的主体，
链表则是主要为了解决哈希冲突而存在的，
如果定位到的数组位置不含链表
当前entry的next指向null,
那么对于查找，
添加等操作很快，
仅需一次寻址即可；
如果定位到的数组包含链表，
对于添加操作，
其时间复杂度为O(n)，
首先遍历链表，
存在即覆盖，
否则新增；
对于查找操作来讲，
仍需遍历链表，
然后通过key对象的equals方法逐一比对查找。
所以，性能考虑，HashMap中的链表出现越少，
性能才会越好。

52.List、Set、Map之间的区别

List、Set是实现了Collection接口的子接口；
而Map是另一个集合接口。


1元素重复性：
 List允许有重复的元素。
任何数量的重复元素
都可以在不影响现有重复元素的值
及其索引的情况下插入到List集合中；

Set集合不允许元素重复。
Set以及所有实现了Set接口的类
都不允许重复值的插入，
若多次插入同一个元素时，
在该集合中只显示一个；

Map以键值对的形式对元素进行存储。
Map不允许有重复键，
但允许有不同键对应的重复的值；

2.元素的有序性：

List及其所有实现类保持了
每个元素的插入顺序；

Set中的元素都是无序的；
但是某些Set的实现类
以某种殊形式对其中的元素进行排序，
如：LinkedHashSet按照元素的
插入顺序进行排序；

Map跟Set一样对元素进行无序存储，
但其某些实现类对元素进行了排序。
如：TreeMap根据键对其中的元素进行升序排序；

3.元素是否为空值：
1.List允许任意数量的空值；
2.Set最多允许一个空值的出现；
当向Set集合中添加多个null值时，
在该Set集合中只会显示一个null元素
3.Map只允许出现一个空键，
但允许出现任意数量的空值；
---------------------------------
总结： 
List中的元素:
有序、可重复、可为空；
Set中的元素:
无序、不重复、只有一个空元素；
Map中的元素:
无序、键不重，值可重、可一个空键、多可空值；

53.HashMap 的长度为什么是2的幂次方

1.减小哈希冲突概率 
假如当前Entry数组长度为len，
插入节点时，
需要对key的hashcode进行二次哈希，
然后跟len-1相与
得到的值一定小于len，避免数组越界

如果len是2的N次方，
那么len-1的后N位二进制一定是全1

假设有两个key，
他们的hashcode不同，
分别为code1和code2 
code1和code2分别与一个后N位全1的二进制相与，
结果一定也不同 
但是，如果code1和code2分别
与一个后N位非全1的二进制相与，
结果有可能相同

也就是说，
如果len是2^N，
不同hashcode的key
计算出来的数组下标一定不同； 
否则，
不同hashcode的key
计算出来的数组下标一定相同。

所以HashMap长度为全1，
可以减小哈希冲突概率。
----------------------
2.提高计算下标的效率 
如果len的二进制后n位非全1，
与len-1相与时，
0与1相与需要取反。 
如果len的二进制后n位全1，
完全不需要取反。

如果len为2^N，
那么与len-1相与，
跟取余len等价，
而与运算效率高于取余。 
如果len不是2^N，
与len-1相与，
跟取余len不等价。

54.集合框架中的泛型有什么优点？

首先，
了解一下Java关于泛型的概念。
泛型，在C++中被称为模板，
就是一种抽象的编程方式。
当我们定义类和方法的时候，
可以用一种通用的方式进行定义，
而不必写出具体的类，
这些未知的东西会在真正使用的时候在确定。

对于集合类来说，
它们可以存放各种类型的元素。
如果在存放之前，
就能确定元素的类型，
那么就可以更加直观，
也让代码更加简洁。

说明：
java的泛型是停留在编译层的，
也就是说JVM在对待泛型数据的时候，
依然会把它们看成是Object类型，
只不过在使用这些元素的时候，
JVM会自动帮助我们进行相应的类型转换。

总结：
集合使用泛型之后，
可以达到元素类型明确的目的，
避免了手动类型转换的过程，
同时，也让我们更加明确
容器保存的是什么类型的数据。

55.我们能否使用任何类作为Map的key？

1、可以 
但是做为key的数据有如下要求：

2、首先，
要求明确一点Map集合存储数据的
主要目的是为了查找 
而List集合是为了输出

3、既然是查找那么就要涉及到对象比较 
我们说了如果要进行对象比较
就必须覆写Object类中的equals()、hasCode() 
至少覆写equals()方法 简单理解：
自己定义的类如果要想实现对象比较
就必须至少覆写equals()方法

4、或则这么说只要是自己定义的类
要想将其作为key 
就必须覆写equals()方法

5、实际工作中 key的类型一定是String型 
(95%通用) 其余的5%是没事找事的

6、按标准开发、你会感到事半功倍，
不要没事给自己找事，
当然求知精神是值得肯定的。

56.Map接口提供了哪些不同的集合视图？

Map接口提供了三个集合视图：

1.Set keyset()：
返回map中包含的所有key的一个Set视图。
集合是受map支持的，
map的变化会在集合中反映出来，
反之亦然。
当一个迭代器正在遍历一个集合时，
若map被修改了(除迭代器自身的移除操作以外)，
迭代器的结果会变为未定义。
集合支持通过
Iterator的Remove、
Set.remove、
removeAll、
retainAll和clear操作进行元素移除，
从map中移除对应的映射。
它不支持add和addAll操作。

2.Collection values()：
返回一个map中包含的
所有value的一个Collection视图。
这个collection受map支持的，
map的变化会在collection中反映出来，
反之亦然。
当一个迭代器正在遍历一个collection时，
若map被修改了(除迭代器自身的移除操作以外)，
迭代器的结果会变为未定义。
集合支持通过
Iterator的Remove、
Set.remove、
removeAll、
retainAll和clear操作进行元素移除，
从map中移除对应的映射。

它不支持add和addAll操作。

3.Set> entrySet()：
返回一个map钟包含的
所有映射的一个集合视图。
这个集合受map支持的，
map的变化会在collection中反映出来，
反之亦然。
当一个迭代器正在遍历一个集合时，
若map被修改了
除迭代器自身的移除操作，
以及对迭代器返回的entry进行setValue外，
迭代器的结果会变为未定义。
集合支持通过
Iterator的Remove、
Set.remove、
removeAll、
retainAll和clear操作进行元素移除，
从map中移除对应的映射。
它不支持add和addAll操作。

57.哪些集合类是线程安全的？

在集合框架中，有些类是线程安全的，
这些都是jdk1.1中的出现的。
在jdk1.2之后，
就出现许许多多非线程安全的类。
下面是这些线程安全的同步的类：
vector：
就比arraylist多了个同步化机制（线程安全），
因为效率较低，
现在已经不太建议使用。
在web应用中，
特别是前台页面，
往往效率（页面响应速度）是优先考虑的。

statck：堆栈类，先进后出

hashtable：就比hashmap多了个线程安全

enumeration：枚举，相当于迭代器

除了这些之外，
其他的都是非线程安全的类和接口。

线程安全的类其方法是同步的，
每次只能一个访问。
是重量级对象，
效率较低。

58.队列和栈是什么，列出它们的区别？

队列（Queue）：
是限定只能在表的一端进行
插入和在另一端进行删除操作的线性表；

栈（Stack）：
是限定只能在表的一端
进行插入和删除操作的线性表。

区别如下：
一、规则不同
1. 队列：先进先出（First In First Out）FIFO
2. 栈：先进后出（First In Last Out ）FILO

二、对插入和删除操作的限定不同
1. 队列：只能在表的一端进行插入，
并在表的另一端进行删除；
2. 栈：只能在表的一端插入和删除。

三、遍历数据速度不同
 1. 队列：基于地址指针进行遍历，
而且可以从头部或者尾部进行遍历，
但不能同时遍历，
无需开辟空间，
因为在遍历的过程中不影响数据结构，
所以遍历速度要快；

 2. 栈：只能从顶部取数据，
也就是说最先进入栈底的，
需要遍历整个栈才能取出来，
而且在遍历数据的同时需要
为数据开辟临时空间，
保持数据在遍历前的一致性。

59.哪一个List实现了最快插入？

LinkedList和ArrayList
是另个不同变量列表的实现。
ArrayList的优势在于动态的增长数组，
非常适合初始时总长度未知的情况下使用。
LinkedList的优势在于在中间位置插入和删除操作，
速度是最快的。

LinkedList实现了List接口，
允许null元素。
此外LinkedList提供额外的
get，remove，insert方法
在LinkedList的首部或尾部。
这些操作使LinkedList可被
用作堆栈（stack），
队列（queue）
或双向队列（deque）。

ArrayList实现了可变大小的数组。
它允许所有元素，
包括null。 
每个ArrayList实例都有一个容量（Capacity），
即用于存储元素的数组的大小。
这个容量可随着不断添加新元素而自动增加，
但是增长算法并没有定义。
当需要插入大量元素时，
在插入前可以调用ensureCapacity方法来
增加ArrayList的容量以提高插入效率。

60.什么时候使用ConcurrentHashMap？

快速失败的Java迭代器
可能会引发ConcurrentModifcationException
在底层集合迭代过程中被修改。
故障安全作为发生在实例中的一个副本
迭代是不会抛出任何异常的。
快速失败的故障安全范例定义了
当遭遇故障时系统是如何反应的。
例如，用于失败的快速迭代器ArrayList
和用于故障安全的迭代器ConcurrentHashMap。

ConcurrentHashMap被作为
故障安全迭代器的一个实例，
它允许完整的并发检索和更新。
当有大量的并发更新时，
ConcurrentHashMap此时可以被使用。
这非常类似于Hashtable，
但ConcurrentHashMap不锁定
整个表来提供并发，
所以从这点上ConcurrentHashMap的性能
似乎更好一些。
所以当有大量更新时
ConcurrentHashMap应该被使用。