面试题汇总(1)
面试题汇总（1）
Q：有了Object类为什么还需要泛型？
A：通过泛型可以定义类型安全的数据结构（类型安全），而无须使用实际的数据类型（可扩展）。这能够显著提高性能并得到更高质量的代码（高性能），无须复制类型特定的代码（可重用）。
基于 Object 的解决方案存在两个问题
- 第一个问题是性能，在使用值类型时，一定会进行多次装箱和拆箱，这就会造成很多性能的损失，并且在堆上产生更多的垃圾，造成更大的垃圾回收压力。即使使用的是引用类型也会造成类型强转的开销。
- 基于 Object 的解决方案的第二个问题（通常更为严重）是类型安全。因为编译器允许在任何类型和 Object 之间进行强制类型转换，所以将丢失编译时类型安全。
Q：数据库索引为什么使用B树乃至B+树？
A：B树优化了对磁盘的读取次数，而B树的劣势在于因为B树的元素分散在各个节点上，遍历所有元素很麻烦，而B+树的所有元素都会出现在叶子节点上，B+的数据就在叶子节点上，非叶子节点负责实现索引功能。
m阶B\B+树
- 每个叶子节点至多有m个儿子，至少有[m/2]个儿子。
- 根节点（如果不是叶子节点）至少有2个儿子。
- 所有叶子节点在同一层。
Q：数据库索引的作用 ？
A:
- 加快数据库访问速度
- 约束数据库的值，unique index，主键，外键
Q：数据库索引的分类？
A：Clustered index 聚集索引和non Clustered index非聚集索引。聚集索引是直接指向记录，非聚集索引指向索引，非聚集索引的访问速度要多一次由指针查找记录的步骤。不过聚集索引一个表只能建一个。
Q：B+树和红黑树的区别？
A：前者优化了对磁盘的读取次数，红黑树优化了数据比较的次数
Q：什么情况需要建索引？
A：给查找次数较多的表加索引，对于复杂的 SQL使用query plan分析是否需要加索引。
Q：什么是BIO通信？伪异步IO通信？NIO通信？AIO通信？
A：
- 采用BIO的通信方式是由一个Accceptor线程负责监听客户端的连接，监听到连接后为每个客户端创建一个新的线程进行链路处理，一请求一应答，缺乏弹性伸缩能力，在高并发情况下，服务端的线程个数和客户端的请求数目成1:1的正比关系，会极大地影响系统的性能，例如堆栈溢出等问题。
- 采用伪异步IO通信是通过线程池负责实现，M个请求N个应答，虽然他的资源占用是可控的，但是在高并发情况下线程池会出现线程阻塞的情况。
- 采用NIO通信所有数据都是通过缓冲区Buffer处理的，读是从缓冲区读，写是写入到缓冲区中。通道Channel与流不同在于通道是双向的，通道可以读和写二者同时进行。多路复用器Selector会轮询注册在其上的Channel，如果发现读或者写事件，那么通道就会变为就绪状态。通过selector key可以获取就绪通道集合，便于后续操作。JDK使用了epoll，而没有使用select，因此没有最大通信的限制。
- 采用AIO通信连接注册读写事件和回调函数，读写方法异步，主动通知程序。
Q：并行计算：①如何排序10个G的元素？
A：
- ①使用外部排序，根据一定数量的节点将数据分为若干段，使每一段都可以在内存中运行，分别在每一段数据中采用归并排序或者快速排序等等，每段数据排序完成后，归并节点进行K路归并，在这个过程中使用堆的数据结构实现归并，也就是优先队列（priorityQueue），使用缓冲区存放每段数据的前若干个元素，可能是几k个或者几M个。在获取元素的过程中使用Iterable<T>接口，因为Iterable接口具有不断获取下一个元素的能力，，同时元素的存储/获取方式被抽象，与归并节点无关。归并数据源来自Iterable<T>.next(),策略：如果某一路缓冲区空则读取下一批元素进入缓冲区，缓冲区的第一个元素加入优先队列。
Q：HashSet、HashMap、Hashtable、SynchronizeMap以及ConcurrentHashMap的底层实现？
A：
- HashSet底层就是把HashMap中的Key作为Set的对应存储项，底层的 Hash 存储机制完全一样，甚至 HashSet 本身就采用 HashMap 来实现的。
HashMap
- HashMap由数组+链表组成的，数组是HashMap的主体，默认长度16，链表则是主要为了解决哈希冲突而存在的，即链地址法。HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对和一个hash值和一个指向下一个Entry的next指针。
- 如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可
- 如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，操作是创建新节点，把该新节点插入到链表中的头部，该新节点的next指针指向原来的头结点 ，即需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。
- 所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
HashMap扩容：
- 当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作
- 计算hash值之后，如何通过hash值均匀的存到数组里！当然是取模，但取模消耗大，因此HashMap用的&运算符（按位与操作）来实现的：hashCode & (length-1)
- 这里就隐含了为什么数组长度length一定要是2的n次方。当length不是2的n次方的时候，length-1的二进制最后一位肯定是0，在&操作时，一个为0，无论另一个为1还是0，最终&操作结果都是0，这就造成了结果的二进制的最后一位都是0，这就导致了所有数据都存储在2的倍数位上，所以说当length = 2^n时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快
JDK1.8之前和之后HashMap区别
- 在JDK1.8以前版本中，HashMap的实现是数组+链表，它的缺点是即使哈希函数选择的再好，也很难达到元素百分百均匀分布，而且当HashMap中有大量元素都存到同一个桶中时，这个桶会有一个很长的链表，此时遍历的时间复杂度就是O(n)，当然这是最糟糕的情况。
- 在JDK1.8及以后的版本中引入了红黑树结构，HashMap的实现就变成了数组+链表或数组+红黑树。添加元素时，若桶中链表个数超过8，链表会转换成红黑树；删除元素、扩容时，若桶中结构为红黑树并且树中元素个数较少时会进行修剪或直接还原成链表结构，以提高后续操作性能；遍历、查找时，由于使用红黑树结构，红黑树遍历的时间复杂度为 O(logn)，所以性能得到提升。
HashMap多线程下会发生什么问题
- 可能会产生环形链表
Hashtable：
- HashTable容器使用synchronized来保证线程安全，但是锁的是整个hash表，当一个线程使用 put 方法时，另一个线程不但不可以使用 put 方法，连 get 方法都不可以。
- Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。
- Hashtable中，key和value都不允许出现null值。在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null
synchronizedMap：
- synchronizedMap提供一个不同步的基类和一个同步的包装。允许需要同步的用户可以拥有同步，而不需要同步的用户则不必为同步付出代价，get方法与HashTable一样锁住整个hash表，区别是get()和put()之类的简单操作可以在不需要额外同步的情况下安全地完成。但多个操作组成的操作序列却可能导致数据争用，总之就是不好用。
ConcurrentHashMap
- HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁。
- 那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率。
- 这就是 ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，默认分成16个段，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
ConcurrentHashMap JDK1.8
- 基本结构：Node<K,V>数组+链表（红黑树）的结构。
- 而对于锁的粒度，调整为对每个数组元素加锁（Node），即没有分段锁了，而是Node锁，粒度更小。
- 使用CAS操作来确保Node的一些操作的原子性，这种方式代替了锁。
- ConcurrentHashMap在线程安全的基础上提供了更好的写并发能力，但同时降低了读一致性。ConcurrentHashMap的get操作上面并没有加锁。所以在多线程操作的过程中，并不能完全的保证一致性。这里和1.7当中类似，是弱一致性的体现。
- 代码中使用synchronized而不是ReentrantLock，说明JDK8中synchronized有了足够的优化。
- 因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。这样一来，查询的时间复杂度就会由原先的O(n)变为O(logN)。
- ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响。
- HashEntry中的value以及next都被volatile修饰，这样在多线程读写过程中能够保持它们的可见性。
