Java工程师应该掌握的相关知识(基础篇01)

自己并不是 CS 科班出身，学习 Java 的时间也不长，但自己比较喜欢这行业。所以想写一些文章记录一些自己想去详细了解的知识，并且希望能分享出来大家进行讨论，一起进步~

我比较喜欢问题驱动学习的形式，所以经常会看一些大公司的面试题了解自己的不足，下面有五道面试题与大家讨论。下面讨论的问题出自 —— 你应该知道的JAVA面试题

1. Java 线程的状态

这算是一个比较常见的问题了，经常在不同的面经里看见，但经常又记了大概就忘记。
Java 线程在某个时刻只能处于以下六种状态

• 新建(NEW)，线程尚未启动的状态。
• 可运行(RUNNABLE)，可运行状态的线程正在Java虚拟机中执行，但它可能正在等待来自操作系统（例如处理器）的其他资源。
• 阻塞中(BLOCKED)，一个线程试图获取监视器锁（JVM规范实现的内容，每个对象和类在逻辑上都是和一个监视器相关联的），但该锁正在被其它线程持有时的状态。例如进入Synchronize块或者其它线程线程调用了Object.wait方法。
• 等待(WAITING)，一个线程调用了 Object.wait、Thread.join或者LockSupport.park后的状态。例如一个线程调用了 Object.wait 等待 Object.notify 或者 Object.notifyAll 方法。
• 计时等待(TIMED_WAITING)，就是触发等待状态的相关方法加上时间参数的状态。
• 终止(TERMINATED)，线程被终止（抛出一个未被捕获的异常）或正常退出的状态。

参考资料：JDK8 的 Thread 源码，相关源码在1742行开始

2. 进程和线程的区别，进程间如何通讯，线程间如何通讯

我也没上过操作系统的课，只能基于搜索的资料与自己的理解和大家讨论。
进程和线程都是基于一个 CPU 时间段的描述，线程是基于进程的进一步划分。现代 OS 中，进程是 CPU 资源分配的最小单位，线程是 CPU 调度的最小单位。进程之前通讯依靠系统资源，线程之间通讯依靠 JVM 提供的方法。
用户下达运行程序的命令后，就会产生进程。同一程序可产生多个进程（一对多关系），以允许同时有多位用户运行同一程序，却不会相冲突。
维基百科相关解释：进程需要一些资源才能完成工作，如CPU使用时间、内存、文件以及I/O设备，且为依序逐一进行，也就是每个CPU核心任何时间内仅能运行一项进程。
那基于多线程能依赖于多核心执行，就是说多个核心能同时运行一个进程?
进程与线程似乎还与操作系统，语言实现有关，并没有找到很好的资料，欢迎大家讨论。

3. HashMap 的数据结构是什么？如何实现的。和 HashTable，ConcurrentHashMap 的区别

HashMap 是基于 Node 为元素的数组，Node 实现了 Map.Entry 接口，实现上来说有几个关键的点

• put时计算出相应的hash值映射到相应的桶中。
• 如果一个桶中有多个元素则将该通内部元素构造成链表提高索引效率。
• 如果内部链表长度超过 TREEIFY_THRESHOLD 的值（默认为8）将其转换成红黑树，如果红黑树内元素小于 UNTREEIFY_THRESHOLD 大小时将其转换为链表。
• HashMap 默认的初始容量(DEFAULT_INITIAL_CAPACITY)为16，默认的负载因子(DEFAULT_LOAD_FACTOR)为0.75。
• 负载因子表示 HashMap 对表空间的使用程度，负载因子高时表内空间就越紧凑，检索效率就低，占用空间就相对来说小。
• 当容量不足时会出发 resize 方法在达到最大值之前会默认扩大两倍，达到最大值就不进行扩容。
• HashMap 与 HashTable 的哈希算法不同，HashMap 为了加快哈希速度，将哈希表的大小固定为 2 的幂，而 HashTable 使用取模运算实现。简单的取模哈希的结果会更加均匀，所以 HashTable 会分散的更均匀，但由于取模运算对比位运算效率较低。HashMap 又实现了拉链法+红黑树的实现，综上我认为 HashMap更好。

Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。
ConcurrentHashMap 大量的使用了 Unsafe 的本地方法，使用分段锁，降低了锁粒度，提高了在竞争激烈的情况下的性能。Guava 的缓存就是参考其实现的。
参考资料：
https://tech.meituan.com/java-hashmap.html
http://www.infoq.com/cn/articles/ConcurrentHashMap/
https://my.oschina.net/ovirtKg/blog/777520

4. 索引有什么用？如何建索引？

索引相当于目录的功能，例如我们翻书时想快速找到自己感兴趣的章节就要通过索引。如果没有索引时我们只能一页一页的去找自己想要的内容。不同的数据库实现的索引不同，MySQL 中常用的有 B-TREE(从技术上说是B+TREE) 和哈希索引。
就我个人经验来说，创建索引时我会使用 explain 调试和业务相关的语句，当读写都在一个数据库中时要少建索引，避免插入效率低，因为插入时索引自然要去更新一遍，当索引太多时更新就会对整个流程有影响。
避免冗余的索引，例如 AB 索引就维护了 A 的索引，了解 B+TREE 的结构很直观的就能理解，MySQL会针对搜索做优化，但使用索引的效率低时就选择不用索引。
选择合适的索引顺序，原则上说选择性高的索引应放在前面，但又要考虑索引利用率的问题。当然如果实现了读写分离，那就可以随意建索引了！

参考资料：高性能mysql第三版

5. ArrayList 是如何实现的，ArrayList 和 LinkedList 的区别？ArrayList 如何实现扩容？

ArrayList 是基于动态数组实现的数据结构，LinkedList 是基于双向链表实现的数据结构。所以 ArrayList 查找更快，LinkedList 占用的空间更大。由于 LinkedList 是基于链表实现的，而 ArrayList 在插入时又需要动态扩容，所以插入和删除应该理论上比 ArrayList 更快。但实际测试结果并不是如此，由于 LinkedList 的检索效率太拙计，只要在容量大小的 1/10 之前会快于 ArrayList。

时间复杂度对比
参考资料：
http://blog.csdn.net/eson_15/article/details/51145788
http://www.importnew.com/6629.html