面试问题总结

1、equals() & hashCode()

在重写equals方法的同时，必须重写hashCode方法。

1
2
3

public boolean equals(Object obj) {
    return (this == obj);
}

1	public native int hashCode();//该方法返回一个int类型的数值，并且是本地方法

equals 如果不重写底层为 == 比较的为对象的地址。
重写了 hashcode() 两个相同对象的 hashcode 才相等。

对于两个对象:

1、两个不同的对象可能会生成相同 Hashcode 值（Hashcode值相等，equals方法结果未知）
2、两个对象的 Hashcode 值不同，必定是两个不同的对象，equals方法结果必定为false。
3、如果调用 equals 方法得到的结果为 true，则两个对象的 Hashcode 值必定相等；
4、如果调用 equals 方法得到的结果为 false，则两个对象的 Hashcode 值不一定不同；

配合基于散列的集合一起正常运行，散列集合包括HashSet、HashMap以及HashTable。
如果不重写 hashCode 方法，无法使用 Map，Set 等集合。（实体类作为 Key，失效）

import java.util.HashMap;
import java.util.Objects;

public class Demo {

    public static void main(String[] args) {

        /**
         * 重写了 hashcode() 两个对象的 hashcode 才相等。
         */
        People p1 = new People("Jack", 12);
        System.out.println(p1.hashCode());//71329710

        People p2 = new People("Jack", 12);
        System.out.println(p2.hashCode());//71329710

        HashMap<People, Integer> hashMap = new HashMap<>();
        hashMap.put(p1, 1);

        //TODO 在设计hashCode方法和equals方法的时候，如果对象中的数据易变
        //TODO 则最好在equals方法和hashCode方法中不要依赖于该字段。

        // p1.setAge(1);//如果更改了字段值，hashcode值将更改
        // System.out.println(p1.hashCode());//71329699

        System.out.println(hashMap.get(p1));//
        System.out.println(hashMap.get(p2));//如果不重写 则为 null

        /**
         * equals 如果不重写底层为 == 比较的为 对象地址 则为 false
         * public boolean equals(Object obj) {
         *      return (this == obj);
         * }
         */
        System.out.println(p1.equals(p2));// 期望值为 true
    }
}

class People {

    private String name;
    private int age;

    public People(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        People people = (People) o;
        return age == people.age &&
                Objects.equals(name, people.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

2、equals & ==

摘自《Java编程思想》一书中的原话：

“关系操作符生成的是一个boolean结果，它们计算的是操作数的值之间的关系”。

== 对于基本数据类型和 String，是直接比较的值。

int i1 = 12;
int i2 = 12;
System.out.println(i1 == i2);// true

String s1 = "hello";
String s2 = "hello";
System.out.println(s1 == s2);// true

String str = new String("hello");
String str1 = new String("hello");
String str2 = new String("hello");
System.out.println("->:" + (str1 == str2));// ->:false
System.out.println("=>:" + str1.equals(str2));// =>:true
//TODO String类对equals方法进行了重写，用来比较指向的字符串对象所存储的字符串是否相等。

str1 = str;
str2 = str;
System.out.println("->:" + (str1 == str2));// ->:true

== 对于引用类型，是直接比较的两个对象的堆内存地址，如果相等，则说明这两个引用实际是指向同一个对象地址。

Integer 在常量池中的存储范围为[-128,127]

127在这范围内，因此是直接存储于常量池的，而128不在这范围内，所以会在堆内存中创建一个新的对象来保存这个值，所以 i5，i6 分别指向了两个不同的对象地址，故而导致了不相等。

Integer 源码 👇

public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high){
            return IntegerCache.cache[i + (-IntegerCache.low)];
        }
        return new Integer(i);
}

Integer i3 = 127;
Integer i4 = 127;
//It's best to use equals() to compare
System.out.println(i3 == i4);// true
System.out.println(i3.equals(i4));// true

Integer i5 = 128;
Integer i6 = 128;
//It's best to use equals() to compare
System.out.println(i5 == i6);// -----> false
System.out.println(i5.equals(i6));// true

1）对于==，比较的是值是否相等

如果作用于基本数据类型的变量，则直接比较其存储的 “值”是否相等；
如果作用于引用类型的变量，则比较的是所指向的对象的地址。

2）对于equals方法，所有类从Object类中继承equals方法，比较的是否是同一个对象。

1
2
3

public boolean equals(Object obj) {
    return (this == obj);
}

注意：equals() 方法本身和 == 没有区别，但不能作用于基本数据类型的变量（可以为包装类型，比较值）；
如果没有对 equals 方法进行重写，则比较的是引用类型的变量所指向的对象的地址，；
诸如String、Date等类对equals方法进行了重写的话，比较的是所指向的对象的内容。

3、HashMap

HashMap实现了Map接口，Map接口对键值对进行映射。Map中不允许出现重复的键（Key）。

在 JDK1.6，JDK1.7 中，HashMap采用 哈希桶数组(位桶)+链表实现，即使用链表处理冲突。头插法
- 当位于一个桶中的元素较多(链表过长)，即 Hash 值相等的元素较多时，通过key值依次查找的效率较低。
在 JDK1.8 中，HashMap采用 哈希桶数组(位桶)+链表+红黑树实现，当链表长度超过阈值 (8) 时，将链表转换为红黑树。

JDK 1.8 HashMap 实现原理

首先有一个哈希桶数组(位桶)，当添加一个元素（key-value）时，首先计算元素 Key 的 Hash 值，以此确定插入数组中的位置，但是可能存在相同 Hash值的元素已经被放在数组同一位置了，这时就添加到同一 Hash 值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的 Hash 值是相同的，所以说数组存放的是链表。但是当链表长度太长时，JDK 1.8 链表就转换为红黑树，大大提高了查找的效率。

hashCode方法的存在是为了减少equals方法的调用次数，从而提高程序效率。

存储结构-字段

HashMap类中有一个非常重要的字段，就是 Node<K,V>[] table，即哈希桶数组；

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。

transient Node<K,V>[] table;

//Node是单向链表，它实现了Map.Entry接口 存储着key-value
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; //保存该桶的hash值
    final K key; //不可变的key
    V value; //指向一个数据的指针
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Hash 冲突

有时候两个 key 的 hashCode 可能会定位到一个桶中，这时就发生了hash冲突，如果HashMap的 Hash 算法越散列，那么发生Hash 冲突的概率越低。如果数组越大，那么发生 Hash 冲突的概率也会越低，但是数组越大带来的空间开销越多，但是遍历速度越快，这就要在空间和时间上进行权衡，这就要看看 HashMap 的扩容机制。

扩容机制

扩容机制几个比较重要的字段

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 默认为16个桶
static final int MAXIMUM_CAPACITY = 1 << 30; //默认桶最多有2^30个,并且必须是 2的幂
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认负载因子是0.75
int threshold; //能容纳最多key_value对的个数
transient int size; //一共有 key-value对个数
transient int modCount; //记录是发生内部结构变化的次数 put不算发生结构变化

threshold = 负载因子 * length，也就是说数组长度固定以后，如果负载因子越大，所能容纳的元素个数越多，如果超过这个值（threshold ）就会进行扩容(默认是扩容为原来的2倍)，0.75这个值是权衡过空间和时间得出的。(这个值可以大于1)

因为 HashMap 扩容每次都是扩容为原来的2倍，所以 length 总是2的次方，这是非常规的设置，常规设置是把桶的大小设置为素数，因为素数发生hash冲突的概率要小于合数，比如HashTable的默认值设置为11，就是桶的大小为素数的应用(HashTable扩容后不能保证是素数)。HashMap采用这种设置是为了在取模和扩容的时候做出优化。

hashMap是通过key的hashCode的高16位和低16位异或后和桶的数量取模得到索引位置。如下：

static final int hash(Object key) {
    int h;
    // h = key.hashCode() 为第一步 取hashCode值
    // h ^ (h >>> 16)  为第二步 高位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在扩容的时候，如果length每次是 2^n，那么重新计算出来的索引只有两种情况，一种是 old 索引+16，另一种是索引不变，所以就不需要每次都重新计算索引。

HashMap的put方法实现

实现思路：

1.判断键值对数组 Node<K,V>[] table 是否为空。
2.判断 table[i] 处是否插入过值。
3.判断链表长度是否大于8，小于挂在链表最后，如果大于就转换为红黑二叉树，并插入树中。
4.判断key是否和原有key相同，如果相同就覆盖原有key的value，并返回原有value。(旧值)
5.如果key不相同，就插入一个key，记录结构变化一次（modCount）。

通俗来说：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值(HashCode值)。有些朋友误以为默认情况下，hashCode返回的就是对象的存储地址，事实上这种看法是不全面的，确实有些JVM在实现时是直接返回对象的存储地址，但是大多时候并不是这样，只能说可能存储地址有一定关联。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断table是否为空，如果是空的就创建一个table，并获取他的长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果计算出来的索引位置之前没有放过数据，就直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //进入这里说明索引位置已经放入过数据了
        Node<K,V> e; K k;
        //判断put的数据和之前的数据是否重复
        if (p.hash == hash &&
            //key的地址或key的equals()只要有一个相等就认为key重复了，就直接覆盖原来key的value
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //判断是否是红黑树，如果是红黑树就直接插入树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //如果不是红黑树，就遍历每个节点，判断链表长度是否大于8，如果大于就转换为红黑树
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //判断索引每个元素的key是否和可要插入的key相同，如果相同就直接覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e不是null，说明没有迭代到最后就跳出了循环，说明链表中有相同的key
        //因此只需要将value覆盖，并将oldValue返回即可
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;//返回存在的Value值 旧值
        }
    }
    //说明没有key相同，因此要插入一个key-value，并记录内部结构变化次数
    ++modCount;
    if (++size > threshold)//大于了 threshold
        resize();//扩容两倍  
    afterNodeInsertion(evict);
    return null;
}

HashMap的get方法实现

实现思路：

1.判断表或key是否是null，如果是直接返回null。
2.判断索引处第一个key与传入key是否相等，如果相等直接返回。
3.如果不相等，判断链表是否是红黑二叉树，如果是，直接从树中取值。
4.如果不是树，就遍历链表查找。

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果表不是空的，并且要查找索引处有值，就判断位于第一个的key是否是要查找的key
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            //如果是，就直接返回
            return first;
        //如果不是就判断链表是否是红黑二叉树，如果是，就从树中取值
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果不是树，就遍历链表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

4、HashSet

HashSet 实现了Set接口，底层是HashMap。

HashSet 的方法，也是借助HashMap的方法来实现的。

HashSet 实现了Set接口，它不允许集合中出现重复元素。(仅存储对象)
不能保证元素的顺序，元素是无序的。
集合元素值允许为null。
HashSet不是同步的，需要外部保持线程之间的同步问题。
将对象存储在HashSet之前，要确保重写 equals() 方法和 hashCode() 方法 ，这样才能比较对象的值是否相等，确保集合中没有储存相同的对象。

HashSet 元素不重复

实现了 Set 接口：

1
2
3

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

类中 map 和 PARENT 的定义：

private transient HashMap<E,Object> map;//map集合，HashSet存放元素的容器

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();//map，中键对应的value值

构造方法:

//无参构造方法，完成map的创建
public HashSet() {
    map = new HashMap<>();
}
//指定集合转化为HashSet, 完成map的创建
public HashSet(Collection<? extends E> c) {
   map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
   addAll(c);
}
//指定初始化大小，和负载因子
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
//指定初始化大小
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
//指定初始化大小和负载因子，dummy 无实际意义
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

源码 👉 HashSet 类中的add()方法：

1
2
3

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

来到了 👉 HashMap 的 put()方法：

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

 HashSet<String> set = new HashSet<>();
 set.add("1");
 set.add("1");
 set.add("2");
 set.add(null);

Iterator<String> iterator = set.iterator();
while (iterator.hasNext()){
    String next = iterator.next();
    System.out.println(next);
}
/**
* null
* 1
* 2
*/

5、ConcurrentHashMap

if (key == null || value == null) throw new NullPointerException();

key-value都不可为空！

public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();

ConcurrentHashMap 可以支持并发的读写。

HashMap：非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。

HashMap 做put 操作的时候，假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。同理，当多线程对同一数组位置进行remove操作时也会产生覆盖。因此如果不进行额外的外同步操作，HashMap 是非线程安全的。样必然导致效率低下，而且竞争越激烈，效率越低下。严重情况，两个线程使用HashMap进行put操作会引起死循环(比如put的两个对象引起扩容，可能出现同时在同一数组下用链表表示，结果在get时会出现死循环)，导致CPU利用率接近100%。

HashTable：遗留类，线程安全。 很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能进入Hashtable。

HashTable 只有一把锁，当一个线程访问 HashTable 的同步方法时，会将整张 table 锁住，当其他线程也想访问 HashTable 同步方法时，就会进入阻塞或轮询状态。也就是确保同一时间只有一个线程对同步方法的占用，避免多个线程同时对数据的修改，确保线程的安全性。但是 HashTable 对 get，put，remove 方法都使用了同步操作，这就造成如果两个线程都只想使用get 方法去读取数据时，因为一个线程先到进行了锁操作，另一个线程就不得不等待，这样必然导致效率低下，而且竞争越激烈，效率越低下。

JDK 1.7 ConcurrentHashMap

ReentrantLock + Segment + HashEntry

JDK1.7之前的 ConcurrentHashMap 使用分段锁机制实现。(JDK 1.5—JDK1.7)

ConcurrentHashMap 在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段；而每个Segment元素，即每个分段则类似于一个Hashtable；这样，在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后对该Segment加锁即可。

JDK 1.8 ConcurrentHashMap

Synchronized + CAS + HashEntry + Red-Black Tree

JDK 1.8 已经抛弃了Segment的概念，虽然源码里面还保留了，也只是为了兼容性的考虑。
JDK1.8 则使用数组+链表+红黑树数据结构、并发控制使用Synchronized和CAS原子操作实现ConcurrentHashMap

CAS原理（乐观锁）

一般地，锁分为悲观锁和乐观锁：

悲观锁 认为对于同一个数据的并发操作，一定是为发生修改的；
乐观锁 认为对于同一个数据的并发操作是不会发生修改的，在更新数据时会采用尝试更新不断重试的方式更新数据。

CAS有三个操作数：
- 内存值 V
- 预估值 A
- 更新值 B

当且仅当 V == A 时，–> V = B; B 赋值给 V 否则，不会执行任何操作。

模拟CAS算法

public class TestCompareAndSwap {

    public static void main(String[] args) {
        final CompareAndSwap cas = new CompareAndSwap();

        for (int i = 0; i < 10; i++) {

            /*new Thread(new Runnable() {

                @Override
                public void run() {
                    int expectedValue = cas.get();
                    boolean b = cas.compareAndSet(expectedValue, (int) (Math.random() * 101));
                    System.out.println(b);
                }
            }).start();*/

            new Thread(() ->
                    System.out.println(cas.compareAndSet(cas.get(), (int) (Math.random() * 101)))
            ).start();
        }
    }
}

class CompareAndSwap{
    private int value;
    //获取内存值
    public synchronized int get(){
        return value;
    }
    //比较
    public synchronized int compareAndSwap(int expectedValue, int newValue){
        int oldValue = value;

        if(oldValue == expectedValue){
            this.value = newValue;
        }
        return oldValue;
    }
    //设置
    public synchronized boolean compareAndSet(int expectedValue, int newValue){
        return expectedValue == compareAndSwap(expectedValue, newValue);
    }
}

ConcurrentHashMap 的put方法实现

实现思路：

1.如果没有初始化就先调用 initTable() 方法来进行初始化过程。
2.如果没有hash冲突就直接CAS插入。
3.如果还在进行扩容操作就先进行扩容。
4.如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入。
5.最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环。
6.如果添加成功就调用 addCount() 方法统计size，并且检查是否需要扩容。

ConcurrentHashMap 的get方法实现

实现思路：

1.计算hash值，定位到该table索引位置，如果是首节点符合就返回。
2.如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回。
3.以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null 。

6、Java集合类框架的基本接口

Collection:代表一组对象，每一个对象都是他的子元素;
- Set：不包含重复元素的Collection；
  - HashSet
- List：有序的Collection，可以包含重复元素；
  - ArrayList
  - LinkedList
  - Vector
Map：将key映射到value的对象，key不能重复。
- HashMap

7、关于List,Map,Set,Vector,HashTable

List 👇

@Test
public void testArrayList(){
    ArrayList<String> list = new ArrayList<>();
    list.add(null);
    list.add(null);
    Assert.assertEquals(2,list.size()); // success
}

@Test
public void testLinkedList(){
    LinkedList<String> list = new LinkedList<>();
    list.add(null);
    list.add(null);
    Assert.assertEquals(2,list.size()); // success
}

ArrayList底层是数组，可以存储多个null，添加 null 并未对他的数据结构造成影响。
LinkedList 底层为双向链表，node.value = null也没有影响。

Map 👇

@Test
public void testHashMap() {
    HashMap<String, String> map = new HashMap<>();
    map.put(null, null);
    map.put(null, "1");
    map.put("2", null);
    for (Map.Entry<String, String> entry : map.entrySet()) {
        String key = entry.getKey();
        String value = entry.getValue();
        System.out.println(key + "->" + value);
    }
    Assert.assertEquals(2, map.size()); //OK size = 2
}

@Test
public void testTreeMap() {
    TreeMap<String, String> map = new TreeMap<>();
    map.put(null, null);
    Assert.assertEquals(1, map.size()); //Error NullPointException
}

HashMap中最多只有一个key == null的节点，因为key相同时，后面的节点会替换之前相同key的节点，所以HashMap是可以添加key == null的节点的，只不过只会存在一个，并且 put() 方法返回旧值。
TreeMap的put方法会调用 compareTo 方法，对象为null时，会报空指针错。
- TreeMap存储两个对象Key和Value（仅仅key对象有序，根据键排序的有序集合)。
- TreeMap的底层采用红黑树的实现，完成数据有序的插入，排序。

Set👇

@Test
public void testHashSet(){
    HashSet<String> set = new HashSet<>();
    set.add(null);
    Assert.assertEquals(1,set.size()); //OK size = 1
    set.add(null);
    Assert.assertEquals(2,set.size()); //Error size = 1
}

@Test
public void testTreeSet(){
    TreeSet<String> set = new TreeSet<>();
    set.add(null); //Error NullPointException
}

HashSet 底层是HashMap，所以它的 add() 调用的是 HashMap的 put() ，也只能有一个null。

```java
public boolean add(E e) {

return map.put(e, PRESENT)==null;

}


- **TreeSet 的 add() 方法会调用 compareTo 方法，对象为null时，会报空指针错。**

  - ```java
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

TreeSet中不能有重复对象，而TreeMap中可以存在。(排序集合)

Vector 👇

@Test
public void VectorTest(){
    Vector box = new Vector();
    box.add(null);
    box.add(null);
    Assert.assertEquals(2,box.size()); //ok
}

Vector 底层是数组，可以存储多个null。add() 方法如下：

```java
public synchronized boolean add(E e) {

modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;

}


---

### HashTable 👇

```java
@Test
public void HashTableTest(){
    Hashtable table = new Hashtable();
    table.put(new Object(),null); //Exception
    //table.put(null,new Object()); //Exception
    //table.put(null,null); //Exception
    Assert.assertEquals(1,table.size());//NullPointerException
}

底层为散列表，无论是key为null，还是value为null，都会报错。

Why —> 源码奉上：

459行 -> value 需要判空，所以value不可为null。
465行 -> key需要拥有实例去调用hashCode方法，所以也不能为空。

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) { //value 需要判空，所以value不可为null
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();//key需要拥有实例去调用hashCode方法，所以也不能为空
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}
<!--25-->

非守护线程：如果主线程销毁，用户线程继续运行且互不影响。 👇

当主线程销毁停止，非守护线程（用户线程）并没有结束，而是一直在执行，与主线程互不影响。

public class NotDaemonThread {
    public static void main(String[] args) {
       /* Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    try {
                        Thread.sleep(1000);

                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    System.out.println("我是子线程(用户线程)");
                }
            }
        });*/

        Thread t1 = new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(1000);

                } catch (Exception e) {
                    e.printStackTrace();
                }
                System.out.println("我是子线程(用户线程)");
            }
        });
        // TODO 启动线程 没有开启守护线程
        t1.start();

        //相当与主线程
        for (int i = 0; i < 10; i++) {
            try {
                Thread.sleep(300);
            } catch (Exception e) {
                e.printStackTrace();
            }
            System.out.println("main:i:" + i);
        }
        System.out.println("主线程执行完毕...");
    }
}

// TODO
main:i:0
main:i:1
main:i:2
我是子线程(用户线程)
main:i:3
main:i:4
main:i:5
我是子线程(用户线程)
main:i:6
main:i:7
main:i:8
我是子线程(用户线程)
main:i:9
主线程执行完毕...
我是子线程(用户线程)
我是子线程(用户线程)
我是子线程(用户线程)
......

9、Synchronized & lock 区别

synchronized是关键字属于JVM层面，底层是通过monitor对象来完成，其实wait/notify等方法也依赖monitor 对象只有在同步代码块和同步方法中才能调用wait/notify等方法)

Lock 是一个接口，是 API 层面的锁；默认非公平锁。

锁的释放：
- Synchronized 在线程发生异常时会自动释放锁，因此不会发生异常死锁。
- Lock 异常时不会自动释放锁，所以需要在finally中实现释放锁。
锁的获取：
- Synchronized 假设A线程获得锁，B线程等待。如果A线程阻塞，B线程会一直等待。
- Lock 需在finally中手工释放锁（unlock()方法释放锁），否则容易造成线程死锁；
底层实现区别：
- Synchronized： 底层使用指令码方式来控制锁的，映射成字节码指令就是增加来两个指令：monitorenter 和 monitorexit。当线程执行遇到 monitorenter 指令时会尝试获取内置锁，如果获取锁则锁计数器+1，如果没有获取锁则阻塞；当遇到 monitorexit 指令时锁计数器-1，如果计数器为0则释放锁。
- Lock： 底层是CAS乐观锁，依赖 AbstractQueuedSynchronizer 类，把所有的请求线程构成一个CLH队列。而对该队列的操作均通过Lock-Free（CAS）操作。
Lock 可以使用读锁提高多线程读效率。（ReadWriteLock）

层次	Synchronized Java关键字，jvm 层面上	Lock 是一个接口，Java API 层
锁状态	无法判断	可以判断
锁类型	隐式锁可重入不可中断非公平	显示锁可重入可中断可公平（两者皆可）
性能	悲观锁适用少量同步	乐观锁（CAS）适用大量同步
唤醒	随机唤醒 1 个或唤醒全部线程。	可精确唤醒

锁的分类

可重入锁： Synchronized和ReentrantLook都是可重入锁，锁的可重入性标明了锁是针对线程分配方式而不是针对方法。例如调用Synchronized方法A中可以调用Synchronized方法B，而不需要重新申请锁。
读写锁： 按照数据库事务隔离特性的类比读写锁，在访问统一个资源（一个文件）的时候，使用读锁来保证多线程可以同步读取资源。ReadWriteLock是一个读写锁，通过readLock()获取读锁，通过writeLock()获取写锁。
可中断锁： 可中断是指锁是可以被中断的，Synchronized内置锁是不可中断锁，ReentrantLock可以通过lockInterruptibly() 方法中断显性锁。例如线程B在等待线程A释放锁，但是线程B由于等待时间太久，可以主动中断等待锁。
公平锁： 公平锁是指尽量以线程的等待时间先后顺序获取锁，等待时间最久的线程优先获取锁。synchronized 隐性锁是非公平锁，它无法保证等待的线程获取锁的顺序，ReentrantLook可以自己控制是否公平锁。

ReentrantLock 公平锁和非公平锁

ReentrantLock 默认采用非公平锁，除非在构造方法中传入参数 true ，为公平锁。源码如下：👇

/**
* Creates an instance of {@code ReentrantLock}.
* This is equivalent to using {@code ReentrantLock(false)}.
* default false
*/
public ReentrantLock() {
    sync = new NonfairSync();
}

/**
* Creates an instance of {@code ReentrantLock} with the
* given fairness policy.
* @param fair {@code true} if this lock should use a fair ordering policy
*/
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

10、产生死锁的条件

死锁是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

死锁的发生必须满足以下四个条件：

互斥条件：一个资源每次只能被一个进程使用。
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺。
循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

10、为什么选择MySQL数据库

2008年阿里提出去IOE。O—>Oracle
MySql 性能卓越，服务稳定，很少出现宕机；
开放源代码且无版权制约，自主性，使用成本低；
历史悠久，社区用户非常活跃，遇到问题可以寻求帮助；
软件体积小，安装使用简单，并且易于维护；
品牌口碑效应，使得企业无需考虑就直接用之，LAMP LEMP流行架构；
支持多种操作系统，提供多个API接口，支持多个开发语言。

11、系统设置的主键与我们定义的主键区别

没有根本性区别，只是系统自动添加的一般数据类型是自动编号型，数据是系统维护；
而自己定义的主键，可以选择其他数据类型，自己维护数据。

12、有无主键区别

没有主键，表中可以有重复的行；
有主键，表中不可以有重复的行；
主键的好处是能唯一确定表中的行，体现到现实世界中就是能区别事物。多个字段为表的主键代表这些字段的值组合起来才能确定表中的一行，选课（学生学号，课程号，分数）主键为学号和课程号的组合，只有这两个值确定了，选课表中的一行才能被唯一的确定。

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

面试问题总结

1、equals() & hashCode()

2、equals & ==

3、HashMap

JDK 1.8 HashMap 实现原理

存储结构-字段

Hash 冲突

扩容机制

HashMap的put方法实现

HashMap的get方法实现

4、HashSet

HashSet 元素不重复

5、ConcurrentHashMap

JDK 1.7 ConcurrentHashMap

JDK 1.8 ConcurrentHashMap

CAS原理（乐观锁）

模拟CAS算法

ConcurrentHashMap 的put方法实现

ConcurrentHashMap 的get方法实现

6、Java集合类框架的基本接口

7、关于List,Map,Set,Vector,HashTable

List 👇

Map 👇

Set👇

Vector 👇

9、Synchronized & lock 区别

锁的分类

ReentrantLock 公平锁和非公平锁

10、产生死锁的条件

10、为什么选择MySQL数据库

11、系统设置的主键与我们定义的主键区别

12、有无主键区别

FEATURED TAGS

FRIENDS

1、equals() & hashCode()

2、equals & ==

3、HashMap

JDK 1.8 HashMap 实现原理

存储结构-字段

Hash 冲突

扩容机制

HashMap的put方法实现

HashMap的get方法实现

4、HashSet

HashSet 元素不重复

5、ConcurrentHashMap

JDK 1.7 ConcurrentHashMap

JDK 1.8 ConcurrentHashMap

CAS原理 （乐观锁）

模拟CAS算法

ConcurrentHashMap 的put方法实现

ConcurrentHashMap 的get方法实现

6、Java集合类框架的基本接口

7、关于List,Map,Set,Vector,HashTable

List 👇

Map 👇

Set👇

Vector 👇

9、Synchronized & lock 区别

锁的分类

ReentrantLock 公平锁和非公平锁

10、产生死锁的条件

10、为什么选择MySQL数据库

11、系统设置的主键与我们定义的主键区别

12、有无主键区别

FEATURED TAGS

FRIENDS

CAS原理（乐观锁）