[数据结构与算法]Java面试题讲解总结——第三回（据说是华为大佬讲的)

九、HashCode和equals的区别

原理：

HashCode()的作用是获取哈希码，返回值是一个int型整数，此哈希码的作用是确定对象在哈希表中的索引位置。HashCode()函数定义在JDK的Object().java中，因此所有类中都有HashCode()函数，哈希表存储的是键值对，其特点是能够根据Key值迅速找到对应的Value值。

HashCode()的作用

在HashSet中添加对象时，先计算其哈希码的如果其代表的位置没有元素，则添加该对象，如果该哈希码代表的位置有元素了，再调用equals判断对象是否相等，如果相等则不添加，如果不相等再添加，因此减少了equals的次数，提高了效率。

区别：

如果两个对象相等则它们的Hashode一定相等；

如果两个对象相等则调用equals返回true;

两个对象的Hashode相等，对象不一定相等；

根据Hashode调用规则，如果equals重写了，那么Hashde也要重写；

十、ArrayList和Linkedist的区别

ArrayList：基于动态数组，连续内存存储，适合随机下标访问；扩容机制，因为数组长度固定，因此在超出数组长度时需要新建数组并把原数组中的数据拷贝到新建数组中，如果不是采用尾插法还可能涉及到元素移动，故设置初始数组长度并采用尾插法可以提高性能。

Linkedist：基于链表，不可以随机访问需要遍历整个链表，适合做插入删除操作；且遍历需要iterator接口，尽量不要使用for循环，因为for循环体内调用get(i)需要重新对链表遍历消耗太大。如果使用IndexOf查找元素，即便没有找到也会将链表遍历一遍。

十一、HashMap与HashTable（目前已经不常用了）的区别以及其底层实现

区别：

HashMap是线程不安全的，HashTable中的方法都加了Synchronized因此是线程安全的。

HashMap允许Key和Value为空，HashTable不可以。

底层实现：数组+链表

jdk8开始，链表长度到8.数组长度超过64，链表转为红黑树，元素以内部类node节点存在；

计算Key的哈希值，二次Hash然后对数组长度取模，再对应到数组下标；

如果没有产生下标冲突则直接创建node存入数组；

如果产生Hash冲突，则equals判断对象是否相同，如果相同则替代元素并存储，如果不同则判断链表高度再插入链表，如果链表高度超过8且数组长度超过64则转变为红黑树，如果链表高度小于6 则由红黑树变回链表。

Key为Null时直接放入下标为0处。

十二、Concurrent HashMap原理，在jdk7和jdk8中的区别

jdk7：Reentrantlock+Segment+HashEntry，一个Segment包含一个HashEntry数组，每个HashEntry数组是一个链表结构；

元素查询：两次Hash，第一次确定元素所在的Segment，第二次确定元素所在链表的表头；

锁：Segment是分段锁，继承Reentrantlock，锁定操作的Segment，其他的Segment不受影响，并法度为Segment个数，可以通过构造函数指定，数组扩容时不会影响其他的Segment。

get方法无需加锁，volatile保证。

jdk8：Syntronized+CAS+Node+红黑树，Node的val和next都volatile修饰保证可见性；

查找、赋值、替换都使用CAS；

锁：锁链表的head节点，不影响其他元素，因此细粒度和效率更高，扩容时阻塞所有的读写操作，并法扩容，为保证扩容时的可见性，数组volatile修饰。