Java基础

没有特别说明线程安全,代表线程不安全

equals和hashCode

1. 如果重写了equals方法,则一定要重写hashCode方法
2. 在程序执行期间,只要equals方法的比较操作用到的信息没有被修改,那么对这同一个对象调用多次,hashCode方法必须始终如一地返回同一个整数
3. 如果两个对象通过equals方法比较得到的结果是相等的,那么对这两个对象进行hashCode得到的值应该相同
4. 两个不同的对象的hashCode可能是相同的,这就是哈希表中的冲突,为了保证哈希表的效率,哈希算法应尽可能的避免冲突
5. 如果只重写了equals方法而没有重写hashCode方法的话,则会违反这条约定:相等的对象必须具有相等的hashCode

Map

1. List接口和Set接口都继承了java.util.Collection接口, Map接口没有继承java.util.Collection接口

HashMap

1. key只可以有一个null,value可以有多个null，key为null时返回的hashCode值为0
2. 存放元素无序
3. hash冲突时,1.8之前是插入链表头部,1.8中是插入链表尾部
4. 增删改查时间复杂度都是O(1),牛牛牛

put元素

1. 对key的hashCode()做hash操作，然后再计算index
2. 如果没碰撞直接放到bucket里
3. 如果碰撞了以链表的形式插入链表尾部
4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树
5. 如果节点已经存在就替换old value(保证key的唯一性)
6. 如果bucket中的元素超过容器容量大小*负载因子,就要resize

获取元素

1. 如果没有冲突,即该下标对应的bucket中只有一个元素，则直接取该元素
2. 如果产生了冲突,则通过key.equals(k)去查找对应的entry：若为树则在树中通过key.equals(k)查找O(logn); 若为链表则在链表中通过key.equals(k)查找O(n)

扩容

1. 当put元素时,如果bucket中的元素超过容器容量大小*负载因子就要扩容
2. 创建一个新数组,容量是之前的2倍,然后将之前的元素拷贝到新数组中. 1.8之前需要重新计算每个元素在数组中的下标,即重新计算hash; 1.8中只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成原索引+2的n次方

扩容的时候需要重新计算Hash吗? 1.8之前需要,1.8中不需要. 在1.8中元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置

LinkedHashMap

HashMap有一个问题，就是迭代HashMap的顺序并不是HashMap元素插入的顺序，也就是无序，而LinkedHashMap是有序的。

1. 它是HashMap的子类，在HashMap数据结构的基础上,还维护着一个双向链表链接所有元素,这个链表定义了迭代顺序，同HashMap一样，key只可以有一个null,value可以有多个null
2. 支持两种排序：默认是元素插入的顺序；可以通过设置accessOrder=true来达到按访问顺序排序的效果，也就是访问一个元素之后，会将它放到尾部
3. 遍历的时候，从head指针指向的节点开始遍历,一直到tail指向的节点，默认情况下是元素的插入顺寻
4. 在创建LinkedHashMap的时候，可以通过设置accessOrder=true来达到按访问顺序遍历LinkedHashMap的效果。什么叫访问顺序？即通过get方法访问的元素，会放到链表尾部，也就是按照了访问时间进行排序，基于这个特性和
5. 添加元素：先添加到HashMap数据结构里，然后维护双向链表的关系,添加到链表尾部
6. 删除元素：先从HashMap数据结构里删除，同时将其从链表里面删除

TreeMap

LinkedHashMap虽然可以根据插入顺序和访问顺序排序，但是无法自定义排序规则，而TreeMap可以

1. 实现基于红黑树，key不能为null，如果为null没法比较，value可以为null
2. 实现了Cloneable接口，所以它可以被克隆
3. 默认情况下，根据其key的自然顺序进行排序，这时候通过key#compareTo方法进行比较，此种情况key必须实现Comparable接口；或者根据创建映射时提供的Comparator进行排序
4. 基本操作containsKey、get、put、remove方法，它的时间复杂度是O(log(n))

HashTable

1. key不能为null,value也不能为null
2. 线程安全的,通过synchronized实现,效率低
3. hash冲突时,插入链表头部

ConcurrentHashMap

1. key不能为null,value也不能为null
2. 线程安全的，1.7基于分段锁实现(Segment+ReentrantLock), 1.8基于CAS+synchronized实现(锁粒度更细), 相对HashTable来说,性能好很多

List

1. List接口和Set接口都继承了java.util.Collection接口, Map接口没有继承java.util.Collection接口
2. 可以存重复的元素

ArrayList

1. 可以存null,可以存重复元素
2. 初始化大小为10,初始化的时候也可以指定大小
3. 扩容时默认扩充1.5倍,如果还是不够,就扩充容量为实际的元素个数. 扩容本质上是数组拷贝System.arraycopy,效率很低,所以最好在初始化的时候指定大小
4. 增删改查中,增导致扩容,则会修改modCount; 删一定会修改modCount; 改和查一定不会修改modCount; modCount和Fail-Fast机制相关
5. 扩容操作会导致数组复制, 删除会导致数组复制操作, 因此增删操作都相对低效, 而改查操作比较高效

arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
src:源数组；
srcPos:源数组要复制的起始位置；
dest:目的数组；
destPos:目的数组放置的起始位置；
length:复制的长度；
src 和 dest 必须是同类型或者可以进行转换类型的数组

LinkedList

1. 双向链表，插入和删除操作比 ArrayList 更加高效，随机访问的效率要比 ArrayList 差

Vector

1. 线程安全
2. Vector扩容时，扩容是翻倍size，而ArrayList是扩容50%

Stack

1. 线程安全，继承自Vector

CopyOnWriteArrayList

1. 线程安全,可以存null,可以存重复元素
2. 写时复制,读的时候不存在并发问题; 写的时候通过ReentrantLock获取锁,然后基于原数组复制出一个新的数组,在新数组的基础上修改
3. 基于volatile语义可以在读数据时不会有问题,适用于读多写少的场景,如果写比较多的话比较影响性能

Set

1. List接口和Set接口都继承了java.util.Collection接口, Map接口没有继承java.util.Collection接口
2. 不能存重复的值,对于添加到Set中的元素,需要重写hashCode和equals方法

HashSet

1. 实现安了Set接口,底层完全基于HashMap实现,相当于Set里面存的就是HashMap的key,无序,可以存null
2. 对于添加到HashSet中的元素,需要重写hashCode和equals方法
3. 在添加一个元素的时候,实际上将该元素作为HashMap中的key,而所有元素的值,其实是一个final类型的对象private static final Object PRESENT = new Object()
4. 通过Iterator遍历的时候,实际上是遍历HashMap的keymap.keySet().iterator(). 也就是说HashSet依赖于HashMap实现,仅仅是利用了HashMap的key,value只是一个常量对象,没有什么意义

TreeSet

1. TreeSet基于TreeMap实现,它的作用是提供有序的Set集合,底层基于红黑树
2. 实现Comparable接口,可以按照插入值大小排序

LinkedHashSet

1. 可以按插入顺序和访问顺序排序,不可重复,可以存null
2. LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承自HashSet,其所有的方法操作上又与HashSet相同

CopyOnWriteArraySet

1. 线程安全的,可以存null
2. 内部持有一个CopyOnWriteArrayList引用,也就是说它的实现完全基于CopyOnWriteArrayList
3. 那它是如何保证元素不唯一呢?在CopyOnWriteArrayList中有一个addIfAbsent方法,该方法会通过遍历的方式去判断你要添加的元素是否存在
4. 适合读多写少的场景

Fail-Fast机制

1. 在遍历一个集合时,当集合结构被修改,会抛出ConcurrentModificationException
2. 在删除或者增加元素时,通过modCount记录修改次数,在创建迭代器Iterator时通过expectedModCount记录了当前的修改次数,在迭代时判断expectedModCount是否与modCount相等,不相等则抛出ConcurrentModificationException
3. 迭代器的快速失败行为不能得到保证,快速失败迭代器尽最大努力抛出 ConcurrentModificationException,因此迭代器的快速失败行为应该仅用于检测程序错误
4. 单线程和多线程情况下都有可能发生

Fail-Safe机制

1. 在原集合的copy上进行遍历,因此不会抛出ConcurrentModificationException
2. 创建copy需要额外的空间和时间上的开销
3. 遍历的时候无法保证数据的实时性

ThreadLocal

ThreadLocal

1. ThreadLocal中有一个内部类:ThreadLocalMap. 数据会被封装成Entry然后存到ThreadLocalMap中
2. Thread中有一个ThreadLocalMap类型的属性:threadLocals
3. set元素时,如果当前线程的threadLocals属性值为null,则创建一个ThreadLocalMap对象并赋值给当前线程的threadLocals属性,然后以ThreadLocal本身为key,将值存到ThreadLocalMap对象中
4. get元素时,获取当前线程的threadLocals属性值(即ThreadLocalMap对象),然后以ThreadLocal本身为key从ThreadLocalMap对象中获取值
5. HashMap采用拉链法处理哈希冲突: 如果在一个位置已经有元素了就采用链表把冲突的元素链接在该元素后面; ThreadLocal采用的是开放地址法: 有冲突后把要插入的元素放在要插入的位置后面为null的地方(有冲突了就放下一个槽)
6. 线程死亡时,线程局部变量会自动回收内存
7. 当线程拥有的局部变量超过了容量的2/3(没有扩大容量时是10个),会涉及到ThreadLocalMap中Entry的回收

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

public T get() {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null) {
            T result = (T)e.value;
            return result;
        }
    }
    return setInitialValue();
}

为什么ThreadLocalMap中的元素(Entry)要继承弱引用类WeakReference?

1. 只具有弱引用的对象拥有短暂的生命周期,在垃圾回收器线程扫描它所管辖的内存区域的过程中,一旦发现了只具有弱引用的对象,不管当前内存空间足够与否,都会回收它的内存. 但由于垃圾回收器是一个优先级很低的线程,因此不一定会很快发现那些只具有弱引用的对象
2. 如果不使用弱引用,因为ThreadLocalMap中的key就是ThreadLocal对象本身,这时就会和Entry对象存在强引用关联而无法被GC回收,造成内存泄漏. 除非线程结束后,线程被回收了,线程中的ThreadLocalMap也跟着回收

ThreadLocal什么情况下会造成内存泄漏问题?

1. 假如我们将某个ThreadLocal对象的引用设置为null,但线程中的threadLocals属性还指向了那个ThreadLocalMap对象,即存在一条强引用. 如果该线程没有被回收(例如线程池),那就存在内存泄漏问题.
2. 解决方法是在某个ThreadLocal对象使用完了后,马上调用remove方法删除Entry对象