●篇 准备开发环境
章 开发环境搭建 1
1.1 Java语言版本构成及特性 1
1.2 JDK的安装 3
1.3 IntelliJ IDEA的安装 4
1.4 Apache Maven的安装 5
1.5 IntelliJ IDEA插件安装 5
1.6 小结 6
第二篇 数据结构和算法
第2章 数据结构 7
2.1 线性表 8
2.1.1 线性表的定义 8
2.1.2 线性表的类型 8
2.1.3 线性表的抽象类型的定义 8
2.1.4 线性表常见面试考点 9
2.2 顺序表 10
2.2.1 顺序表添加元素 10
2.2.2 顺序表查找元素 10
2.2.3 顺序表删除元素 11
2.2.4 顺序表的实现 11
2.2.5 顺序表常见面试考点 15
2.3 单链表 15
2.3.1 单链表添加元素 16
2.3.2 单链表查找元素 16
2.3.3 单链表删除元素 17
2.3.4 单链表的实现 17
2.3.5 单链表常见面试考点 23
2.4 双向链表 23
2.4.1 双向链表添加元素 24
2.4.2 双向链表查找元素 24
2.4.3 双向链表删除元素 25
2.4.4 双向循环链表 25
2.4.5 双向链表常见面试考点 26
2.5 栈 26
2.5.1 顺序栈 27
2.5.2 链式栈 31
2.5.3 栈常见面试考点 34
2.6 队列 34
2.6.1 顺序队列 35
2.6.2 循环队列 39
2.6.3 链式队列 43
2. 优先队列 46
2.6.5 队列常见面试考点 50
2.7 树 50
2.7.1 树结构的相关概念 51
2.7.2 二树 52
2.7.3 斜树 52
2.7.4 满二树 53
2.7.5 完全二树 53
2.7.6 二树存储结构 54
2.7.7 二树的遍历 56
2.7.8 二排序树 56
2.7.9 AVL树
2.7.10 2-3-4树 79
2.7.11 红黑树 86
2.7.12 哈夫曼树 106
2.7.13 树常见面试考点 114
2.8 树和森林 115
2.8.1 普通树转化为二树 115
2.8.2 森林转化为二树 116
2.8.3 树的遍历 117
2.8.4 森林的遍历 117
2.8.5 树和森林常见面试考点 117
2.9 图 118
2.9.1 图的相关概念 118
2.9.2 图的邻接矩阵存储结构 119
2.9.3 图的邻接表存储结构 122
2.9.4 图的十字链表存储结构 126
2.9.5 图的遍历 132
2.9.6 小生成树 136
2.9.7 Prim算法求解小生成树 137
2.9.8 Kruskal算法求解小生成树 146
2.9.9 Dijkstra算法求解短路径 152
2.9.10 图的常见面试考点 159
第3章 算法 160
3.1 字符串相关算法 160
3.1.1 验证回文字符串 160
3.1.2 分割回文字符串 162
3.1.3 单词拆分 1
3.1.4 前缀树 167
3.1.5 有效的字母异位词 170
3.1.6 无重复字符的长子串 172
3.1.7 电话号码的字母组合 174
3.1.8 串联所有单词的子串 176
3.1.9 字符串相关算法常见面试考点 179
3.2 数组相关算法 179
3.2.1 乘积大连续子序列 179
3.2.2 求众数 181
3.2.3 旋转数组 183
3.2.4 移动零 186
3.2.5 求数组的交集 187
3.2.6 递增的三元子序列 189
3.2.7 搜索二维矩阵 191
3.2.8 除自身以外数组的乘积 194
3.2.9 数组相关算法常见面试考点 197
3.3 排序算法 197
3.3.1 冒泡排序算法 197
3.3.2 选择排序算法 199
3.3.3 插入排序算法 201
3.3.4 希尔排序算法 203
3.3.5 归并排序算法 206
3.3.6 快速排序算法 208
3.3.7 堆排序算法 213
3.3.8 计数排序算法 219
3.3.9 桶排序算法 221
3.3.10 基数排序算法 224
3.3.11 排序算法常见面试考点 227
第三篇 Java基础
第4章 Java中的集合框架 229
4.1 集合框架概述 229
4.2 ArrayList 230
4.2.1 ArrayList类的使用方式 230
4.2.2 ArrayList类的声明 232
4.2.3 ArrayList类的属性 233
4.2.4 ArrayList类的构造器 233
4.2.5 ArrayList类添加元素的方法 234
4.2.6 ArrayList类查询元素方法 238
4.2.7 ArrayList类更新元素方法 240
4.2.8 ArrayList类删除元素方法 240
4.2.9 ArrayList类批量方法 242
4.2.10 ArrayList类导出数组方法 244
4.2.11 ArrayList类排序方法 245
4.2.12 ArrayList类的迭代器 247
4.2.13 ArrayList常见面试考点 253
4.3 LinkedList 253
4.3.1 LinkedList类的使用方式 253
4.3.2 LinkedList类的声明 255
4.3.3 LinkedList类的属性 256
4.3.4 LinkedList类的内部类Node 256
4.3.5 LinkedList类的构造器 257
4.3.6 LinkedList类添加元素方法 257
4.3.7 LinkedList类查询元素的方法 260
4.3.8 LinkedList类更新元素方法 261
4.3.9 LinkedList类删除元素的方法 262
4.3.10 LinkedList类批量方法 263
4.3.11 LinkedList类的迭代器 265
4.3.12 LinkedList常见面试考点 269
4.4 Deque 270
4.4.1 Deque类的使用方式 270
4.4.2 Queue接口 271
4.4.3 Deque接口 272
4.4.4 LinkedList类的addFirst()方法 276
4.4.5 LinkedList类的addLast()方法 276
4.4.6 LinkedList类的offerFirst()方法 277
4.4.7 LinkedList类的offerLast()方法 277
4.4.8 LinkedList类的removeFirst()方法 278
4.4.9 LinkedList类的removeLast()方法 279
4.4.10 LinkedList类的pollFirst()方法 280
4.4.11 LinkedList类的pollLast()方法 280
4.4.12 LinkedList类的getFirst()方法 280
4.4.13 LinkedList类的getLast()方法 281
4.4.14 LinkedList类的peekFirst()方法 281
4.4.15 LinkedList类的peekLast()方法 281
4.4.16 LinkedList类的add()方法 282
4.4.17 LinkedList类的offer()方法 282
4.4.18 LinkedList类的remove()方法 282
4.4.19 LinkedList类的poll()方法 283
4.4.20 LinkedList类的element()方法 283
4.4.21 LinkedList类的peek()方法 283
4.4.22 LinkedList类的removeFirstOccurrence()方法 284
4.4.23 LinkedList类的removeLastOccurrence()方法 284
4.4.24 LinkedList类的push()方法 285
4.4.25 LinkedList类的pop()方法 286
4.4.26 Deque常见面试考点 286
4.5 PriorityQueue 286
4.5.1 PriorityQueue类的使用方式 286
4.5.2 PriorityQueue类的声明 287
4.5.3 PriorityQueue类的属性 288
4.5.4 PriorityQueue类的构造器 289
4.5.5 PriorityQueue类的add()方法 294
4.5.6 PriorityQueue类的offer()方法 294
4.5.7 PriorityQueue类的poll()方法 297
4.5.8 PriorityQueue类的peek()方法 297
4.5.9 PriorityQueue常见面试考点 298
4.6 HashMap 298
4.6.1 HashMap类的使用方式 298
4.6.2 Entry接口 300
4.6.3 Map接口 301
4. HashMap类的声明 307
4.6.5 HashMap类的属性 307
4.6.6 HashMap静态内部类Node 309
4.6.7 HashMap静态内部类TreeNode 311
4.6.8 HashMap的存储结构 312
4.6.9 HashMap的类构造器 312
4.6.10 HashMap类的put()方法 313
4.6.11 HashMap类的hash()方法 314
4.6.12 HashMap类的putVal()方法 314
4.6.13 HashMap类的resize()方法 318
4.6.14 HashMap类的putTreeVal()方法 323
4.6.15 HashMap类的treeifyBin()方法 324
4.6.16 HashMap类的remove()方法 330
4.6.17 HashMap类的get()方法 334
4.6.18 HashMap常见面试考点 335
4.7 LinkedHashMap 335
4.7.1 LinkedHashMap类的使用方式 336
4.7.2 LinkedHashMap类的声明 339
4.7.3 LinkedHashMap静态内部类Entry 339
4.7.4 LinkedHashMap类的属性 339
4.7.5 LinkedHashMap类的构造器 340
4.7.6 LinkedHashMap类的put()方法 341
4.7.7 LinkedHashMap类的get()方法 345
4.7.8 LinkedHashMap类的getOrDefault()方法 345
4.7.9 LinkedHashMap类的containsValue()方法 346
4.7.10 LinkedHashMap类的removeEldestEntry()方法 346
4.7.11 LinkedHashMap类常见面试考点 346
4.8 TreeMap 346
4.8.1 TreeMap类的使用方式 347
4.8.2 TreeMap类的声明 348
4.8.3 TreeMap静态内部类Entry 352
4.8.4 TreeMap类的属性 353
4.8.5 TreeMap类的构造器 354
4.8.6 TreeMap类的putAll()方法 355
4.8.7 TreeMap类的buildFromSorted()方法 355
4.8.8 TreeMap类的put()方法 358
4.8.9 TreeMap类的get()方法 361
4.8.10 TreeMap类的remove()方法 362
4.8.11 TreeMap类的firstKey()方法 365
4.8.12 TreeMap类的lastKey()方法 365
4.8.13 TreeMap类常见面试考点 366
4.9 HashSet 366
4.9.1 HashSet类的使用方式 366
4.9.2 HashSet类的声明 367
4.9.3 HashSet类的属性 367
4.9.4 HashSet类的构造器 368
4.9.5 HashSet类的add()方法 369
4.9.6 HashSet类的remove()方法 369
4.9.7 HashSet类的contains()方法 369
4.9.8 HashSet类的iterator()方法 370
4.9.9 HashSet类常见面试考点 372
4.10 LinkedHashSet 372
4.10.1 LinkedHashSet类的使用方式 372
4.10.2 LinkedHashSet类的声明 373
4.10.3 LinkedHashSet类构造器 373
4.10.4 LinkedHashSet类常见面试考点 374
4.11 TreeSet 374
4.11.1 TreeSet类的使用方式 375
4.11.2 TreeSet类的声明 377
4.11.3 TreeSet类的属性 379
4.11.4 TreeSet类的构造器 379
4.11.5 TreeSet类的add()方法 380
4.11.6 TreeSet类的first()方法 381
4.11.7 TreeSet类的last()方法 382
4.11.8 TreeSet类的descendingIterator()方法 382
4.11.9 TreeSet类常见面试考点 385
第四篇 Java并发编程
第5章 线程基础 387
5.1 线程的概念 387
5.1.1 进程与线程的关系 387
5.1.2 线程的概念常见面试考点 388
5.2 线程的创建 388
5.2.1 继承Thread类 388
5.2.2 实现Runnable接口 389
5.2.3 实现Callable接口 390
5.2.4 线程池 391
5.2.5 线程创建的常见面试考点 394
5.3 线程的生命周期 394
5.3.1 初始状态 395
5.3.2 就绪状态 396
5.3.3 运行中状态 396
5.3.4 阻塞状态 396
5.3.5 等待状态 396
5.3.6 超时等待状态 396
5.3.7 终止状态 396
5.3.8 线程的生命周期常见面试考点 397
5.4 线程中断 397
5.4.1 线程中断的概念 397
5.4.2 线程中断的响应 397
5.4.3 线程中断的操作 397
5.4.4 线程中断常见面试考点 401
5.5 线程的优先级和守护线程 401
5.5.1 线程优先级的特性 402
5.5.2 守护线程 406
5.5.3 线程优先级和守护线程常见面试考点 408
5.6 线程常用方法 408
5.6.1 sleep()方法 408
5.6.2 wait()方法 410
5.6.3 notify()/notifyAll()方法 411
5. yield()方法 413
5.6.5 join()方法 415
5.6.6 线程常用方法常见面试考点 416
5.7 线程组 416
5.7.1 线程组的概念 416
5.7.2 一级关联 417
5.7.3 多级关联 419
5.7.4 线程组自动归属 420
5.7.5 批量管理线程 421
5.7.6 线程组常见面试考点 422
5.8 Thread类代码解析 423
5.8.1 Thread类常用属性 423
5.8.2 Thread类的构造器 424
5.8.3 Thread类的start()方法 427
5.8.4 Thread类的run()方法 431
5.8.5 Thread类的et()方法 431
5.8.6 Thread类的interrupt()方法 431
5.8.7 Thread类的interrupted()方法 434
5.8.8 Thread类的isInterrupted()方法 435
5.8.9 Thread类的join()方法 435
5.8.10 Thread类的sleep()方法 438
5.8.11 Thread类常见面试考点 441
5.9 volatile 442
5.9.1 硬件系统架构 442
5.9.2 缓存一致性问题 443
5.9.3 缓存一致性协议 444
5.9.4 as-if-serial 445
5.9.5 程序顺序规则 446
5.9.6 指令重排序 447
5.9.7 volatile内存语义 450
5.9.8 volatile常见面试考点 451
5.10 synchronized 451
5.10.1 synchronized的作用 451
5.10.2 synchronized的使用方式 452
5.10.3 synchronized死锁问题 462
5.10.4 synchronized的特性 4
5.10.5 synchronized的实现原理 4
5.10.6 synchronized的存储结构 469
5.10.7 自旋锁 473
5.10.8 锁消除 474
5.10.9 锁粗化 475
5.10.10 偏向锁 475
5.10.11 轻量级锁 478
5.10.12 重量级锁 480
5.10.13 synchronized实现线程通信 481
5.10.14 synchronized常见面试考点 488
5.11 ThreadLocal 488
5.11.1 ThreadLocal的使用方式 488
5.11.2 ThreadLocal原理分析 490
5.11.3 静态内部类ThreadLocalMap 492
5.11.4 ThreadLocal类的set()方法 499
5.11.5 ThreadLocal类的get()方法 499
5.11.6 ThreadLocal与内存泄漏 500
5.11.7 ThreadLocal常见面试考点 501
第6章 并发编程工具 502
6.1 AbstractQueuedSynchronizer 502
6.1.1 AbstractOwnableSynchronizer代码分析 502
6.1.2 AbstractQueuedSynchronizer内部类 503
6.1.3 AbstractQueuedSynchronizer的属性 506
6.1.4 AbstractQueuedSynchronizer独占模式 506
6.1.5 AbstractQueuedSynchronizer共享模式 516
6.1.6 AbstractQueuedSynchronizer条件模式 522
6.1.7 AbstractQueuedSynchronizer常见面试考点 546
6.2 Lock 547
6.2.1 Lock接口加锁方法 547
6.2.2 Lock接口解锁方法 549
6.2.3 Lock接口的newCondition()方法 549
6.3 ReentrantLock 549
6.3.1 ReentrantLock的使用方式 549
6.3.2 ReentrantLock类图 551
6.3.3 ReentrantLock内部类Sync代码解析 552
6.3.4 ReentrantLock内部类FairSync代码解析 554
6.3.5 ReentrantLock内部类NonfairSync代码解析 555
6.3.6 ReentrantLock构造器代码解析 556
6.3.7 ReentrantLock公平锁代码解析 557
6.3.8 ReentrantLock非公平锁代码解析 559
6.3.9 公平锁与非公平锁比较 560
6.3.10 ReentrantLock常见面试考点 561
Semaphore 561
.1 Semaphore的使用方式 561
.2 Semaphore类图 563
.3 Semaphore内部类Sync代码解析 563
.4 Semaphore内部类FairSync代码解析 565
.5 Semaphore内部类NonfairSync代码解析 566
.6 Semaphore构造器代码解析 566
.7 Semaphore公平模式代码解析 567
.8 Semaphore非公平模式代码解析 570
.9 Semaphore常见面试考点 571
6.5 CountDownLatch 571
6.5.1 CountDownLatch的使用方式 572
6.5.2 CountDownLatch类图 575
6.5.3 CountDownLatch内部类Sync代码解析 575
6.5.4 CountDownLatch构造器代码解析 576
6.5.5 await()方法代码解析 577
6.5.6 await(long timeout, TimeUnit unit)方法代码解析 578
6.5.7 countDown()方法代码解析 579
6.5.8 CountDownLatch常见面试考点 580
6.6 CyclicBarrier 580
6.6.1 CyclicBarrier的使用方式 580
6.6.2 CyclicBarrier的属性 583
6.6.3 CyclicBarrier内部类Generation代码解析 583
6. CyclicBarrier构造器代码解析 584
6.6.5 await()方法代码解析 584
6.6.6 reset()方法代码解析 588
6.6.7 CyclicBarrier常见面试考点 588
6.7 ReentrantReadWriteLock 589
6.7.1 ReentrantReadWriteLock的使用方式 589
6.7.2 ReentrantReadWriteLock类图 591
6.7.3 ReentrantReadWriteLock的属性 592
6.7.4 ReentrantReadWriteLock构造器代码解析 592
6.7.5 ReentrantReadWriteLock内部类Sync代码解析 593
6.7.6 ReentrantReadWriteLock内部类FairSync代码解析 595
6.7.7 ReentrantReadWriteLock内部类NonfairSync代码解析 595
6.7.8 ReentrantReadWriteLock内部类ReadLock代码解析 596
6.7.9 ReentrantReadWriteLock内部类WriteLock代码解析 597
6.7.10 ReentrantReadWriteLock写锁代码解析 599
6.7.11 ReentrantReadWriteLock读锁代码解析 602
6.7.12 ReentrantReadWriteLock常见面试考点 607
6.8 ArrayBlockingQueue 607
6.8.1 ArrayBlockingQueue的使用方式 608
6.8.2 ArrayBlockingQueue的属性 609
6.8.3 ArrayBlockingQueue构造器代码解析 610
6.8.4 ArrayBlockingQueue入队方法代码解析 612
6.8.5 ArrayBlockingQueue出队方法代码解析 614
6.8.6 ArrayBlockingQueue常见面试考点 617
6.9 LinkedBlockingQueue 618
6.9.1 LinkedBlockingQueue的使用方式 618
6.9.2 LinkedBlockingQueue内部类Node代码解析 620
6.9.3 LinkedBlockingQueue的属性 621
6.9.4 LinkedBlockingQueue构造器代码解析 622
6.9.5 LinkedBlockingQueue入队方法代码解析 623
6.9.6 LinkedBlockingQueue出队方法代码解析 625
6.9.7 LinkedBlockingQueue常见面试考点 629
6.10 DelayQueue 629
6.10.1 DelayQueue的使用方式 629
6.10.2 DelayQueue的声明 632
6.10.3 DelayQueue的属性 632
6.10.4 DelayQueue构造器代码解析 633
6.10.5 DelayQueue入队方法代码解析 633
6.10.6 DelayQueue出队方法代码解析 635
6.10.7 DelayQueue工作原理解析 639
6.10.8 DelayQueue常见面试考点 0
6.11 LinkedBlockingDeque 0
6.11.1 LinkedBlockingDeque的使用方式 0
6.11.2 LinkedBlockingDeque的声明 4
6.11.3 LinkedBlockingDeque内部类Node代码解析 7
6.11.4 LinkedBlockingDeque的属性 8
6.11.5 LinkedBlockingDeque构造器代码解析 9
6.11.6 LinkedBlockingDeque入队方法代码解析 650
6.11.7 LinkedBlockingDeque出队方法代码解析 654
6.11.8 LinkedBlockingDeque常见面试考点 658
6.12 CopyOnWriteArrayList 658
6.12.1 CopyOnWriteArrayList的使用方式 658
6.12.2 CopyOnWriteArrayList的属性 660
6.12.3 CopyOnWriteArrayList构造器代码解析 660
6.12.4 CopyOnWriteArrayList添加元素方法代码解析 661
6.12.5 CopyOnWriteArrayList更新元素方法代码解析 663
6.12.6 CopyOnWriteArrayList删除元素方法代码解析 6
6.12.7 CopyOnWriteArrayList查找元素方法代码解析 666
6.12.8 CopyOnWriteArrayList工作原理解析 667
6.12.9 CopyOnWriteArrayList常见面试考点 668
6.13 ConcurrentHashMap 668
6.13.1 ConcurrentHashMap的使用方式 669
6.13.2 ConcurrentHashMap类的属性 670
6.13.3 ConcurrentHashMap内部类Node代码解析 671
6.13.4 ConcurrentHashMap内部类TreeNode代码解析 672
6.13.5 ConcurrentHashMap内部类TreeBin代码解析 674
6.13.6 ConcurrentHashMap内部类ForwardingNode代码解析 675
6.13.7 ConcurrentHashMap类put()方法代码解析 676
6.13.8 ConcurrentHashMap类putIfAbsent()方法代码解析 676
6.13.9 ConcurrentHashMap类putVal()方法代码解析 677
6.13.10 ConcurrentHashMap类initTable()方法代码解析 679
6.13.11 ConcurrentHashMap类helpTransfer()方法代码解析 680
6.13.12 ConcurrentHashMap类treeifyBin()方法代码解析 682
6.13.13 ConcurrentHashMap类tryPresize()方法代码解析 683
6.13.14 ConcurrentHashMap类transfer()方法代码解析 684
6.13.15 ConcurrentHashMap类get()方法代码解析 690
6.13.16 ConcurrentHashMap常见面试考点 690
6.14 Unsafe 690
6.14.1 Unsafe单例设计模式 691
6.14.2 Unsafe类内存操作相关方法 691
6.14.3 Unsafe类CAS相关方法 695
6.14.4 Unsafe类线程调度相关方法 697
6.14.5 Unsafe类Class相关方法 698
6.14.6 Unsafe类对象相关方法 700
6.14.7 Unsafe类数组相关方法 701
6.14.8 Unsafe类volatile相关方法 703
6.14.9 Unsafe类内存屏障相关方法 704
6.14.10 Unsafe类常见面试考点 704
6.15 LockSupport 704
6.15.1 LockSupport的使用方式 705
6.15.2 LockSupport构造器代码解析 706
6.15.3 LockSupport静态代码块 707
6.15.4 LockSupport类阻塞方法代码解析 708
6.15.5 LockSupport类唤醒方法代码解析 709
6.15.6 LockSupport常见面试考点 709
6.16 原子类 710
6.16.1 AtomicInteger的使用方式 711
6.16.2 AtomicInteger类的属性 712
6.16.3 AtomicInteger构造器代码解析 712
6.1 AtomicInteger常用方法代码解析 713
6.16.5 ABA问题 715
6.16.6 AtomicStampedReference代码解析 717
6.16.7 原子类常见面试考点 718
6.17 线程池 719
6.17.1 ThreadPoolExecutor的使用方式 719
6.17.2 ThreadPoolExecutor构造器代码解析 722
6.17.3 ThreadPoolExecutor工作流程 726
6.17.4 ThreadPoolExecutor内部类Worker代码解析 727
6.17.5 ThreadPoolExecutor的状态 729
6.17.6 ThreadPoolExecutor提交任务代码解析 731
6.17.7 ThreadPoolExecutor类execute()方法代码解析 733
6.17.8 ThreadPoolExecutor类addWorker()方法代码解析 735
6.17.9 ThreadPoolExecutor类runWorker()方法代码解析 738
6.17.10 ThreadPoolExecutor类getTask()方法代码解析 741
6.17.11 ThreadPoolExecutor类processWorkerEt()方法代码解析 742
6.17.12 ThreadPoolExecutor类shutdown()方法代码解析 743
6.17.13 ThreadPoolExecutor类shutdownNow()方法代码解析 743
6.17.14 线程池常见面试考点 744
第五篇 面试与技巧
第7章 剖析面试 745
7.1 什么是面试 745
7.1.1 让面试官记住你 746
7.1.2 让面试官信任你 747
7.2 面试环节分析 748
7.2.1 笔试 748
7.2.2 语音面试 748
7.2.3 视频面试 748
7.2.4 现场面试 749
7.2.5 压力面试 750
7.2.6 背景调查 750
7.2.7 在线考试 751
第8章 面试技巧 752
8.1 类候选人 752
8.2 第二类候选人 755
8.3 第三类候选人 755
8.4 第四类候选人 756
参考文献 762