从集合类开始

此文为我在备战秋招过程中对Java基础知识的启发式总结。

Java集合类，有Set, List, Queue.

List底下有Vector, ArrayList, LinkedList. Vecotr底下还有个Stack.

讲一讲区别？

要说区别的话，Vector和ArrayList底层都是动态数组，不同的是Vector是线程安全的，因为它的方法有被**synchronized**关键字修饰，

还有就是扩容，ArrayList是1.5倍扩容，关于这点可参考这篇文章, 而Vector一般是两倍扩容（为什么说是一般呢，是不是两倍取决于我们new Vector的时候有没有传容量参数）。

然后Stack继承自Vector,所以它也是线程安全的。

讲一讲锁、Synchronized关键字？

而LinkerList底层是链表，还有一点就是LinkedList实现了Queue接口，所以它可以当做队列来用(准确的来说，应该是个双端队列)。

而Set的实现主要有HashSet, TreeSet, 还有一个LinkedHashSet, 它继承自HashSet, 但是性质有所不同。

HashSet底层其实也是个HashMap, 只不过把HashMap的value变成一个静态对象了。

TreeSet底层是红黑树，目的就是可以实现排序。

LinkedHashSet继承自HashSet, 它俩的区别类似于HashMap和LinkedHashMap的区别（准确的说不是类似，是等同，因为它的），其区别就在于我们可以按照存入的顺序按序把元素取出。

LinkedHashSet或LinkedHashMap的这个特性是如何实现的呢？LinkedHashMap内部是有一个双向链表的（准确说是维护一个静态内部类Entry, 继承自Node），通过这个双向链表来维护顺序。具体体现在：

1
2
3
4
5
6
7
8
9
10
11

// link at the end of list
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

聊聊红黑树？

Map准确讲不能算在集合类里面，但是也很常用，Map接口底下主要有HashMap, TreeMap, HashTable, 以及继承自HashMap的LinkedHashMap.

谈谈区别

HashMap是数组+链表结构，用于存放键值对，HashTable也是，不同的是HashTable线程安全，因为它的put等方法是用synchronized关键字修饰的。TreeMap可以实现排序,之所以有这个功能是因为它的底层是红黑树，所以每次put都是相当于是按序插入。LinkedHashMap继承自HashMap, 上面在将LinkedHashSet的时候讲过，它可以按照插入顺序取出元素。

谈谈HashMap的扩容

HashMap是数组+链表的结构，它比较有趣的地方就在于它的put和扩容了。它的构造方法有以下几种：

1
2
3

public HashMap(int initialCapacity, float loadFactor) 
public HashMap(int initialCapacity)
public HashMap()

其中，initialCapacity是”初始容量“，loadFactor是负载因子。注意这里初始容量加了引号，意味着这并不一定是真的初始容量，它会根据传入的这个initialCapacity, 计算一个离它最近的比它的二的次幂作为真实容量。具体操作如下：

1
2
3
4
5
6
7
8
9

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

（有一说一，这个写法有点灵性）

而负载因子的意思其实就是阈值，它表示当HashMap的容量达到多少时要进行一个扩容操作。

当我们使用无参的构造函数时，它俩默认值分别是16和0.75.

谈谈HashMap和ConcurrentHashMap?

HashMap不是线程安全的，所以有了ConcurrentHashMap, 虽然HashTable也是线程安全的，但是两者实现略有不同，性能也有所差异。HashTable是通过synchronized关键字实现的，而ConcurrentHashMap在1.7和1.8中实现略有不同。1.7是通过分段锁实现的，1.8是通过CAS+synchronized实现的。

分段锁：首先是有一个Segment数组，这个数组的每一个元素指向的才是一个真正的HashMap, 这个Segment对象继承自ReentrantLock, 所以是有锁的功能的。基于分段锁的ConcurrentHashMap理论上最大可以达到Segment数组size的并发度。

1.8的ConcurrentHashMap放弃了分段锁的技术，使用CAS+synchronzied来保证线程安全。在插入的时候，先CAS插入，如果失败，则用synchronized加锁插入。

谈谈ReentrantLock?