Java学习总结 2020/4/8

12. 深拷贝与浅拷贝

拷贝就是就是将现有的一个对象的属性都保存给另一个对象，由于引用数据类型是引用传递的，直接用=将原对象赋给拷贝对象，只是在栈中新建了一个引用指向堆中同一个对象，并没有实现拷贝。拷贝分为浅拷贝与深拷贝。

浅拷贝：浅拷贝一个对象，是将该对象中基本类型的变量进行拷贝，而对于引用类型，浅拷贝只是把内存地址赋值给了成员变量，它们指向了同一内存空间。改变其中一个，会对另外一个也产生影响。实现：实现Cloneable接口，并重写clone()方法。

深拷贝：深拷贝会将所有的成员变量都复制，在拷贝引用类型成员变量时，为引用类型的数据成员另辟了一个独立的内存空间，实现真正意义上的拷贝。实现方式主要有：

·手动赋值，代码简单，但是啰嗦

·通过序列化与反序列化实现，需要源对象以及所有成员对象类型都实现Serializable()接口，通过序列化，将源对象的信息以另外一种形式存放在了堆外。然后将堆外的这份信息通过反序列化的方式再放回到堆中，就创建了一个新的对象，也就是目标对象

·在浅拷贝的基础上，对所有成员对象类型实现Cloneable接口，并在拷贝时，分别调用每一个成员对象的clone()方法

13. 常用的容器

注意：常见的Vector,Hashtable,ConcurrentHashMap,stack是线程安全的

14. List，Set和Map的区别

·List：实现Collection接口

允许有重复元素

可以插入多个null元素

是有序容器，保持了每个元素的插入顺序

·Set：实现Collection接口

不允许有重复元素

只允许一个null元素

是无序容器

·Map：不是Collection接口的子接口或实现类

每个元素都有两个对象，分别是键与值，其中键不能重复，值可以重复

值可以有多个null值，键只能有一个null

Map接口的实现类中，HashMap是无序的，LinkedHashMap是有序的

15. HashMap底层实现数据结构

HashMap底层上数据结构实现是数组+链表，Java8之后是数组+链表+红黑树。

大概过程是，HashMap会初始化一个数组用于存储每一个key-value,当传入key-value时，HashMap根据key.hashcode()计算出的hash值来决定键值对存放在数组的哪个位置，当两个不同的key值计算出相同的hash值时，为hash冲突，在Java8之前，相同hash值的元素会以链表的形式存放在数组的同一个位置，Java8之后，一条链表上元素超过8个，链表就会转换成红黑树。

先看源码：初始化时

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//初始化数组长度为16

HashMap桶数组初始化默认长度是16，这里规范要求必须是2的幂次，至于为什么是16，这就与索引的计算有关了，可以往后看

static final float DEFAULT_LOAD_FACTOR = 0.75f;//初始化负载因子为0.75f

因为默认数组长度为16，当放入的元素太多时，就会导致hash冲突出现多次，链表越来越长，为了解决这个问题，HashMap引入负载因子，就是当数组数据插入超过一个阈值时，数组就会触发扩容，默认为0.75f，也就是数组默认长度下，当你存进第16*0.75+1个元素时，数组就会触发扩容，直接扩容为原来两倍长度。扩容的具体过程我们也后面再讲^_^

static final int TREEIFY_THRESHOLD = 8;//默认链表转数组条件为超过8个元素
  static class Node<K,V> implements Map.Entry<K,V> {
//这里定义的是数组中保存的对象类型
        final int hash;
        final K key;
        V value;
    Node<K,V> next;
}

HashMap中每一个键值对都以Node的形式保存在数组中，里面不但包括了key和value还有key计算出的hash值和指向链表下一个元素的指针

接下来我们看我们用的最多的get和put方法是怎么实现的：

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

可以看出来，get方法就是直接计算key的hash值，调用getNode方法，getNode就会遍历这个链表或者从红黑树直接取出我们要的数据

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

put方法也是类似，这里我们看一下putVal方法中索引的计算方式

Index = (n - 1) & hash

n是数组长度，默认16，索引是hash值和数组长度减1做与运算，也就是说n默认16的情况下，n-1的二进制表示就是1111，和hash做与运算后就是取hash值的后四位，这样做的目的是为了使hash出的索引能均匀分布在数组中，减少hash冲突。

即使平均分布了，当插入的元素数量增加时，还是会不可避免的出现大量hash冲突，所以上面说到HashMap有扩容机制，我们再讲讲扩容机制，HashMap的扩容过程主要分两步：

·第一步：扩容，创建一个新的桶数组，长度为原来的两倍

·第二步：ReHash：遍历原来的数组，将每一个元素重新计算其hash值，再放到新数组中

特别需要注意的是：在Java7之前，put进新元素进链表和ReHash构造链表时都采用头插法，也就是同一位置上的新数据总是插入在链表的头部，这样会在Rehash后，改变链表顺序，

而在Java7之后，采用尾插法，即同一位置上的新元素是插入在链表尾部。这样就不会改变链表顺序了，这样的好处就是解决了多线程扩容时产生的链表循环问题：

多线程使用头插法时，假设线程1,2都对同一个HashMap进行扩容，线程1执行到扩容，并ReHash了一个元素时，此时线程1被挂起，但此时A.next依然是B，

线程2进行ReHash后，B会插入链表头部，B.next又会指向A，就会造成链表循环，所以这也是HashMap线程不安全的原因之一。

而使用尾插法，在扩容时会保持链表原来的顺序，就不会出现链表循环问题。但也不是说Java7之后的HashMap就是线程安全的了，因为还是没有解决丢失更新的问题。不过也没有关系，在多线程情况下我们还可以使用线程安全的Hashtable和ConcurrentHashMap。

丢失更新：当线程1插入一个Map<key1,value1>，然后线程1挂起，这时线程2插入一个Map<key1,value2>，对于同一个key，value1就被覆盖为value2，现在线程1再获取key1的值就不是value1了，这就是丢失更新。