数据结构与算法相关续

第三章 Java

1.HashMap

1）HashMap的数据结构？

哈希表结构(链表散列：数组+链表)实现，结合数组和链表的优点。当链表长度超过8时，链表转换为红黑树。

transient Node<K,V>\ [ \ ] table;

2）HashMap的工作原理？

HashMap底层是hash数组和单向链表实现，数组中的每个元素都是链表，由Node内部类(实现Map.Entry接口)实现，HashMap通过put&get方法存储和获取。
存储对象时，将K/V键值传给put()方法：
①调用hash(k)方法计算k的hash值，然后结合数组长度，计算得数组下标；
②调整数组大小(当容器中的元素个数大于capacity * loadfactor时，容器会进行扩容resize为2n)；
③ i.如果k的hash值在HashMap中不存在，则执行插入，若存在，则发生碰撞；
ii.如果k的hash值在HashMap中存在，且它们两者equals返回true，则更新键值对；
iii.如果k的hash值在HashMap中存在，且它们两者equals返回false，则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。(JDK1.7之前使用头插法、JDK1.8使用尾插法)
（注意：当碰撞导致链表大于TREEIFY_THRESHOLD=8时，就把链表转换成红黑树）
获取对象时，将k传给get()方法；
①调用hash(k)方法(计算k的hash值)从而获取该键值所在链表的数组下标；
②顺序遍历链表，equals()方法查找相同Node链表中K值对应的V值。
hashCode是定位的，存储位置；equals是定性的，比较两者是否相等。

3）当两个对象的hashCode相同会发生什么？

因为HashCode相同，不一定就是相等(equals方法比较)，所以两个对象所在数组的下标相同，“碰撞”就此发生。又因为HashMap使用链表存储对象，这个Node会存储到链表中。

4)你知道hash的实现吗？为什么要这样实现？

JDK1.8中，是通过hashCode()的高16位异或或低16位实现的:（h=k.hashCode()）^(h>>>16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。

5)为什么要用异或运算符

保证了对象的hashCode的32位值只要有一位发生改变，整个hash()返回值就会改变。尽可能减少碰撞。

6)HashMap的table的容量如何确定？loadFactor是什么?该容量如何变化?这种变化会带来什么问题？

①table数组大小是由capacity这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30;
②loadFactor是装载因子，主要目的是用来确认table数组是否需要动态扩展，默认值是0.75，比如table数组大小为16，装载因子为0.75时，threshold就是12，当table的实际大小超过12时，table就需要动态扩容；
③扩容时，调用resize()方法，将table长度变为原来的两倍(注意是table长度,而不是threshold)
④如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。

7)HashMap中put方法的过程？

“调用哈希函数获取Key对应的hash值，在计算其数组下标”；
如果没有出现哈希冲突，则直接放入数组；如果出现哈希冲突，则以链表的方式放在链表后面；
如果链表长度超过阀值(TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表；
如果结点的key已经存在，则替换其value即可；
如果集合中的键值对大于12，调用resize方法进行数组扩容

8）数组扩容的过程?

创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。

9）拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了，造成很深的问题),遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋、右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持"平衡"是需要付出代价的，但是该代价所耗损的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

10)说说你对红黑树的见解？

每个节点非红即黑
根节点总是黑色的
如果节点是红色的，则它的子节点必须是黑色的(反之不一定)
每个叶子节点都是黑色的空节点(NIL节点)
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点(即相同的黑色高度)

11)jdk1.8中对HashMap做了哪些改变？

在java1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。(桶的数量必须大于64，小于64的时候只会扩容)
发生hash碰撞时，java1.7会在链表的头部插入，而java1.8会在链表的尾部插入
在java1.8中，Entry被Node替代(换了一个马甲)

12)HashMap、LinkedHashMap、TreeMap有什么区别?

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历时，先取到的记录肯定是先插入的，遍历比HashMap慢。
TreeMap实现SortMap接口，能够把它保存的记录根据键排序(默认按键值升序排序，也可以指定排序的比较器)

13)HashMap&TreeMap&LinkedHashMap使用场景?

一般情况下，使用最多的是HashMap。
HashMap:在Map中插入、删除和定位元素时;
TreeMap:在需要按自然顺序或自定义顺序遍历键的情况下；
LinkedHashMap:在需要输出的顺序和输入的顺序相同的情况下。

14)HahMap和HashTable有什么区别?

①HashMap是线程不安全的，HashTable是线程安全的；
②由于线程安全，所以HashTable的效率比不上HashMap。
③HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而HashTable不允许；
④HashMap默认初始化数组的大小为16，HashTable为11，前者扩容时，扩大两倍，后者扩大两倍+1;
⑤HashMap需要重新计算hash值，而HashTable直接使用对象的hashCode

15）Java中的另一个线程安全与HashMap极其类似的类是什么？同样是线程安全，它与HashTable在线程同步上有什么不同?

ConcurrentHashMap类(是Java并发包java.util.concurrent中提供的一个线程安全且高效的HashMap实现)
HashTable是使用synchronize关键字加锁的原理(就是对对象加锁)
而针对ConcurrentHashMap,在JDK1.7中采用分段锁的方式；JDK1.8中直接采用了CAS(无锁算法)+synchronized。

16)HashMap&ConcurrentHashMap的区别?

除了加锁，原理上无太大区别。另外，HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

17)为什么ConcurrentHashMap比HashTable效率要高？

HashTable使用一把锁(锁住整个链表结构)处理并发问题，多个线程竞争一把锁，容易阻塞；
CurrentHashMap
JDK1.7中使用分段锁（ReentrantLock+Segment+HashEntry），相当于把一个HashMap分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度:基于Segment，包含多个HashEntry。
JDK1.8中使用CAS+synchd+Node+红黑树。锁粒度:Node（首结点）(实现Map.Entry)。锁粒度降低了。

18)针对ConcurrentHashMap锁机制具体分析(JDK1.7 VS JDK1.8)

JDK1.7中，采用分段锁的机制，实现并发的更新操作，底层采用数组+链表的存储结构，包括两个核心静态内部类Segment和HashEntry。
①Segment继承ReentrantLock（重入锁）用来充当锁的角色，每个Segment对象守护每个散列映射表的若干个桶
②HashEntry用来封装映射表的键-值对
③每个桶是由若干个HashEntry对象链接起来的链表

image.png

JDK1.8中，采用Node+CAS+Synchronized来保证并发安全。取消类Segment，直接用table数组存储键值对；当HashEntry对象组成的链表长度超过TREEIFY_THRESHOLD时，链表转换为红黑树，提升性能。底层变更为数组+链表+红黑树

image.png

19)ConcurrentHashMap在JDK1.8中，为什么要使用内置锁synchronized来代替重入锁ReentrantLock？

①粒度降低了
②JVM开发团队没有放弃synchronized，而且基于JVM的ReentrantLock优化空间更大，更加自然。
③在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存。

20)ConcurrentHashMap简单介绍？

①、重要的常量:
private transient volatile int sizeCtl;
当为负数时，-1标识正在初始化，-N标识N-1个线程正在进行扩容
当为0时，表示table还没有初始化
当为其他正数时，表示初始化或者下一次进行扩容的大小
②数据结构：
Node是存储结构的基本单元，继承HashMap中的Entry，用于存储数据；
TreeNode继承Node，但是数据结构换成了二叉树结构，是红黑树的存储结构，用于红黑树中存储数据
TreeBin是封装TreeNode的容器，提供转换红黑树的一些条件和锁的控制
③存储对象时(put()方法)
如果没有初始化，就调用initTable(）方法来进行初始化
如果没有hash冲突就直接CAS无锁插入
如果需要扩容，就先进行扩容；
如果存在hash冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入
如果该链表的数量大于阀值8，就要先转换成红黑树的结构；break再一次进入循环
如果添加成功就调用addCount()方法统计size，并且检查是否需要扩容。
④扩容方法transfer():默认容量为16，扩容时，容量变为原来的两倍
helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高
⑤获取对象时(get()方法)：
计算hash值，定位到该table索引位置，如果是首结点符合就返回；
如果遇到扩容时,会调用标记正在扩容结点ForwardingNode.find()方法，查找该结点，匹配就返回；
以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回null

21)ConcurrentHashMap的并发度是什么？

程序运行时能够同时更新ConcurrentHashMap且不产生锁竞争的最大线程数。默认为16，且可=可以在构造函数中设置
当用户设置并发度时，ConcurrentHashMap会使用大雨等一该值的最小2幂指数作为实际并发度(假如用户设置并发度为17，实际并发度则为32)

2.ArrayList

1)ArrayList是什么？可以用来干嘛？

ArrayList就是有序的动态数组列表，主要用来装载数据，只能装载包装类(Integer，String，Double等)，它的主要底层实现是数组Object[] elementData

2)ArrayList与LinkedList的区别？

①ArrayList的查找和访问元素的速度较快，但新增，删除的速度较慢，LinkedList的查找和访问元素的速度较慢，但是他的新增、删除的速度较快。
②ArrayList需要一份连续的存储空间，LinkedList不需要连续的存储空间(特别地，当创建一个ArrayList集合的时候，连续的内存空间必须要大于等于创建的容量)
③两者都是线程不安全的

3）为什么线程不安全还使用ArrayList?

因为在我们正常的使用场景中，都是用来查询的，不会设计太频繁的增删，如果涉及频繁的增删，可以使用LinkedList，如果需要线程安全的就是可以使用Vector，CopyOrWriteArrayList

4）它的底层实现是数组，但是数组的大小是定长的，如果我们不断的往里面添加数据的话，不会有问题吗？

JDK1.7->>相当于设计模式中的饿汉式，第一次创建无参构造器时就创建一个初始容量为10的数组。
JDK1.8->>相当于设计模式中的懒汉式，ArrayList可以通过光谱早方法在初始化的时候指定底层数组的大小。通过无参构造方法的方式ArrayList()初始化，则赋值底层数Object[] elementData为一个默认空数组Object[]
DEFAULTCAPACITY_EMPTY_ELEMENTDATA ={}
所以数组容量为0，只有真正对数据进行添加add时，才分配默认DEFAULT_CAPACITY = 10的初始容量。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//无参数
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//有参数
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

5）ArrayList数组扩容

假设我们有一个长度为10的数组，此时需要新增一个，发现满了，ArrayList会进行扩容

image.png

1.重新定义10*1.5的数组

image.png
然后把原数组的数据，原封不动的复制到新数组中，然后把ArrayList的地址指向新数组
image.png

//详细扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

6)1.7和1.8版本初始化的区别

1.7的时候是初始化就创建一个容量为10的数组，1.8后是初始化先创建一个空数组，第一次add时才扩容为10

7）ArrayList在增删的时候是怎么做的？(为什么慢)

新增
ArrayList有指定index(索引下标)新增，也有尾部新增，但是都有校验长度的判断ensureCapacityInternal，就是说如果长度不够，是需要扩容的。
在扩容的时候，1.7是取余，1.8是位运算，右移一位，其实就是除以2这个操作。

//尾插add方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
//index(索引)插入，指定位置新增的时候，在校验之后的操作很简单，就是数组的copy
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}
//真正扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
//删除
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

总结：总的来说，不论是删除还是新增，其实本质上都是移动位置，当指定位置新增的时候，新增的锁空出，后面向后移一位，然后赋值，当删除时，也是一样，将要删除的索引下标的值置为null。

8）ArrayList（int initialCapacity）会不会初始化数组大小?

会初始化大小，但是list的大小没有变，也就是size不变。
而且将构造函数与initialCapacity结合使用，然后使用set()会抛出异常，尽管该数组已创建，但是大小设置不正确。使用sureCapacity()也不起作用，因为它基于elementData数组而不是大小。
还有其他副作用，这是因为带有sureCapacity（）的静态DEFAULT_CAPACITY。
进行此工作的唯一方法是使用构造函数后，根据需要使用add()多次。

image.png

9)ArrayList是线程安全的么？

不是，可以用Vector，Collections,synchronizedList(),原理都是给方法套个synchronized，CopyOnWriteArrayList

10)ArrayList用来做队列合适么？

队列一般是FIFO(先入先出)的，如果用ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数组，反过来也可以。
但是无论如何总会有一个操作会设计到数组的数据搬迁，这个是比较耗费性能的。
结论:ArrayList不适合做队列。

11）那数组适合用来做队列么？

数组是非常合适的。比如ArrayBlockingQueue内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的。另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列。
简单点来说就是使用两个偏移量来标记数组的读位置和写位置，如果超过长度就折回到数组开头，前提是女它们是定长数组。

12）ArrayList的遍历和LinkedList遍历性能比较如何？

ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅度降低读取内存的性能开销。

13）ArrayList常用对的方法总结

boolean add(E e)
将指定的元素添加到此列表的尾部。 void add(int index, E element)
将指定的元素插入此列表中的指定位置。boolean addAll(Collection<? extends E> c)
按照指定collection的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。 boolean addAll(int index, Collection<? extends E> c)
从指定的位置开始，将指定 collection 中的所有元素插⼊到此列表中。 void clear()
移除此列表中的所有元素。 Object clone()
返回此 ArrayList 实例的浅表副本。 boolean contains(Object o)
如果此列表中包含指定的元素，则返回 true。 void ensureCapacity(int minCapacity)
如有必要，增加此 ArrayList 实例的容量，以确保它⾄少能够容纳最⼩容量参数所指定的元素数。 E get(int index)
返回此列表中指定位置上的元素。 int indexOf(Object o)
返回此列表中⾸次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。 boolean isEmpty()
如果此列表中没有元素，则返回 true int lastIndexOf(Object o)
返回此列表中最后⼀次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。 E remove(int index)
移除此列表中指定位置上的元素。 boolean remove(Object o)
移除此列表中⾸次出现的指定元素（如果存在）。 protected void removeRange(int fromIndex, int toIndex)
移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。 E set(int index, E element)
⽤指定的元素替代此列表中指定位置上的元素。 int size()
返回此列表中的元素数。 Object[] toArray()
按适当顺序（从第⼀个到最后⼀个元素）返回包含此列表中所有元素的数组。 T[] toArray(T[] a)
按适当顺序（从第⼀个到最后⼀个元素）返回包含此列表中所有元素的数组；返回数组的运⾏时类型是指定数组的运⾏时类型。 void trimToSize()
将此 ArrayList 实例的容量调整为列表的当前⼤⼩。

3.LinekdList

1）ArrayList与和LinkedList区别

①是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全。
②底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表数据结构(JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别。下面有介绍到)
③插入好删除是否受元素位置影响：1.ArrayList采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响.比如:执行add(E e)方法的时候，ArrayList会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置i插入和删除元素的话(add(index,E element))时间复杂度就为O(n-i)。因为在进行上述操作的时候集合中第i和第i个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
2.LinkedList采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似O(1)而数组为近似O(n)
④是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)
⑤内存空间占用：ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)

Hashset源码分析

1)请问HashSet有哪些特点?

HashSet实现自set接口，set集合中元素无序且不能重复。

2）HashSet如何保证元素不重复？

因为HashSet底层是基于HashMap实现的，当你new一个HashSet时候，实际上是new了一个map，执行add方法时，实际上调用map的put方法，value始终是PRESENT,所以根据HashMap的一个特性：将一个key-value对放入HashMap中时，首先根据key的hashCode()返回值决定该Entry的存储位置。如果两个key的hash值相同，那么它们的存储位置相同。如果这两个key的equals比较返回true。那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖。因此，如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖原来已有的集合元素。

源码分析

先看一下无参的构造函数：

public HashSet() {
     map = new HashMap<>();
}

很显然，当你new一个HashSet的时候，实际上是new了一个HashMap

再来看一下add方法：

private static final Object PRESENT = new Object();
 
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

定义一个虚拟的Object PRESENT是向map中插入key-value对应的value，因为HashSet中只需要用到key，而HashMap是key-value键值对；所以，向map中添加键值对时，键值对的值固定是PRESENT。

HashSet构造方法和成员变量

// HashSet 真实的存储元素结构
 private transient HashMap<E,Object> map;

 // 作为各个存储在 HashMap 元素的键值对中的 Value
 private static final Object PRESENT = new Object();

 //空参数构造方法 调用 HashMap 的空构造参数  
 //初始化了 HashMap 中的加载因子 loadFactor = 0.75f
 public HashSet() {
        map = new HashMap<>();
 }

 //指定期望容量的构造方法
 public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
 }
 //指定期望容量和加载因子
 public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
 }
 //使用指定的集合填充Set
 public HashSet(Collection<? extends E> c) {
        //调用  new HashMap<>(initialCapacity) 其中初始期望容量为 16 和 c 容量 / 默认 load factor 后 + 1的较大值
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
 }

 // 该方法为 default 访问权限，不允许使用者直接调用，目的是为了初始化 LinkedHashSet 时使用
 HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
 }

通过HashSet的构造参数我们可以看出每个构造方法，都调用了对应的HashMap的构造方法用来初始化成员变量map，因此我们可以知道，HashSet的初始容量也为1<<4即16，加载因子默认也是0.75f。
我们都知道Set不允许存储重复元素，又由构造参数得出结论底层存储结构为 HashMap,那么这个不可重复的属性必然是有 HashMap 中存储键值对的 Key 来实现了。在分析 HashMap 的时候，提到过 HashMap 通过存储键值对的 Key 的 hash 值（经过扰动函数hash()处理后）来决定键值对在哈希表中的位置，当 Key 的 hash 值相同时，再通过 equals 方法判读是否是替换原来对应 key 的 Value 还是存储新的键值对。那么我们在使用 Set 方法的时候也必须保证，存储元素的 HashCode 方法以及 equals 方法被正确覆写。

HashSet 中的添加元素的方法也很简单，我们来看下实现：

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

可以看出add方法调用了HashMap的put方法，构造的键值对的key为待添加的元素，而value这时有全局变PRESENT来充当，这个PRESENT只是一个Object对象。
除了add方法外HashSet实现了Set接口中的其他方法这些方法有：

public int size() {
        return map.size();
}

public boolean isEmpty() {
   return map.isEmpty();
}

public boolean contains(Object o) {
   return map.containsKey(o);
}

//调用 remove(Object key)  方法去移除对应的键值对
public boolean remove(Object o) {
   return map.remove(o)==PRESENT;
}

public void clear() {
   map.clear();
}

// 返回一个 map.keySet 的 HashIterator 来作为 Set 的迭代器
public Iterator<E> iterator() {
   return map.keySet().iterator();
}

关于迭代器我们在讲解 HashMap 中的时候没有详细列举，其实 HashMap 提供了多种迭代方法，每个方法对应了一种迭代器，这些迭代器包括下述几种，而 HashSet 由于只关注 Key 的内容，所以使用 HashMap 的内部类 KeySet 返回了一个 KeyIterator ，这样在调用 next 方法的时候就可以直接获取下个节点的 key 了。

//HashMap 中的迭代器

final class KeyIterator extends HashIterator
   implements Iterator<K> {
   public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
   implements Iterator<V> {
   public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
   implements Iterator<Map.Entry<K,V>> {
   public final Map.Entry<K,V> next() { return nextNode(); }
}

内存模型

JVM内存模型有:堆、栈、永久区、寄存器、堆外内存

栈(Stack)

每当一个线程去执行方法时，就会同时在栈里面创建一个栈帧(Stack Frame)用于存储局
每一个方法从被调用到执行完的过程，都对应着一个栈帧从入栈到出栈的过程。
栈是线程私有的，每个线程在栈中保有自己的数据，别的线程无法访问。
在栈中我们可能遇到的两种异常：StackOverflowError和OutOfMemoryError
StackOverflowError是指线程请求的栈深度大于虚拟机所允许的深度
OutOfMemoryError是指栈扩展时无法申请到足够的内存

本地方法栈(Native Method Stack)

本地方法栈和栈差不多，区别只在于本地方法栈为Native方法服务。
Native方法就是一个Java调用非Java代码的接口，比如JNI
本地方法栈也是线程私有的。

程序计数器(PC Register)

要理解程序计数器，我们需要知道java代码最终都要编译成一条条的字节码，然后由字节码解释器一条条的执行的。而程序计数器可以看作是当前线程所执行的字节码的行号计数器。
如果正在执行的是一个java方法，那么这个计数器记录的是正在执行的字节码指令地址。如果正在执行的是Native方法，那么计数器的值为Undefined
程序计数器也是线程私有的，每条线程都有一个独立的程序计数器，各线程的程序计数器互不影响
程序计数器是唯一一个不会OOM的内存区域

堆(Heap)

堆的唯一作用就是存放对象，不过并非所有对象都在堆中
堆如果空间不足，就会抛出OOM异常
堆是可以让多个线程共享的

方法区(Method Area)

方法区也是可以多个线程共享的
方法区主要用来存放类的版本、字段、方法、接口、常量池和运行时常量池
常量池里存储着字面量和符号引用

永久代与元空间

作为和堆一样可以让线程共享的区域，堆之外的空间被叫做非堆(Non-Heap）。可以粗略地理解为非堆里包含了永久代，而永久代里又包括了方法区。
我们常常把永久代和方法区等同起来，然而永久其实是Hotspot虚拟机把分代的GC的范围扩展到方法区的产物。

image.png

所以，永久代和方法区虽然基本上指的是同一片内存区域，但是实质上是有差别的。
而到了jdk1.8中，永久代被取消，取而代之的便是元空间。
元空间跟永久代最大额区别就在于，元空间直接使用机器内存，不在jvm虚拟机内。所以理论上你的机器内存有多大，元空间就能有多大。
此外，之前永久代的符号引用（Symbols）转移到了堆外内存(native heap);字面量(interned strings)和类的静态变量(class statics)转移到了堆内(heap）
这样做的好处在于可以减少OOM，同时方便HotSpot和JRockit合并
1.描述一下jvm内存模型
jvm内存模型分为5个区域，其中线程独占的区域是栈、本地方法栈、程序计数器，线程共享的区域是堆、方法区。
2.描述一下java内存模型
回答这个问题一定要问清楚是不是要问java内存模型，确认是的话，可以回答：java内存模型规定了变量的访问规则，保证操作的原子性、可见行、有序性。
3.谈一下你对常量池的理解
常量池是类在编译后储存常量的一块区域，当程序运行到该类，常量池的大部分数据会进入运行时常量池，字符串会进入字符串常量池。
4.什么情况下会发生栈内存溢出？和内存溢出有什么不同？
栈内存溢出指程序调用的栈深度多大或栈空间不足时抛出的StackOverflowError。
一般所谓内存溢出指的是堆内存溢出，抛出的是OutOfMemoryError:java heap space。
在jdk1.7中，还可能出现永久代内存溢出，抛出的是OutOfMemoryError: PermGen space
在jdk1.8中，则会出现元空间溢出，抛出的是OutOfMemoryError：MetaSpace

垃圾回收算法（JVM）

1.什么是垃圾回收？

GC就是垃圾收集的意思（Gabage Collection）。
程序的运行必然需要申请内存资源，无效的对象资源如果不及时处理就会一直占有内存资源，终将导致内存溢出，所以对内存资源的管理是非常重要了。

2.常见的垃圾回收算法

引用计数法、标记清除法、标记压缩法、复制算法、分代算法等

3.引用计数法

假设有一个对象A，任何一个对象对A的引用，那么对象A的引用计数器+1，对象A的引用计数器就-1，如果对象A的计数器值为0，就说明对象A没有引用了，可以被回收。

优缺点

优点

实时性较高，无需等到内存不够的时候，才开始回收，运行时根据对象的计数器是否为0，就可以直接回收。
在垃圾回收过程中，应用无需挂起。如果申请内存时，内存不足，则立刻报outofmember错误。
区域性，更新对象的计数器时，只是影响到该对象，不会扫描到全部对象。

缺点

每次对象被引用时，都需要去更新计数器，有一点时间开销。
浪费CPU资源，即使内存够用，仍然在运行时进行计数器的统计。
无法解决循环应用问题(大的缺点)

什么是循环引用

public class Test {
   public static void main(String[] args) {
       TestA testA = new TestA();
       TestB testB = new TestB();
       testA.b = testB;
       testB.a = testA;
       testA = null;
       testB = null;
   }
}

class TestA{
    public TestB b;
}
class TestB{
    public TestA a;
}

虽然a和b都为null，但是由于a和b都存在循环引用，这样a和b永远都不会被回收

标记清除法

标记清除法，是将垃圾回收分为2个阶段，分别是标记和清除。
标记：从根节点开始标记引用的对象
清除：未被标记引用的对象就是垃圾对象，可被清理

原理

image.png

这张图代表的是程序运行期间所有对象的状态，它们的标志位全部是0(也就是未标记，以下默认0就是未标记，1为已标记)，假设这会儿有效内存空间耗尽了，JVM会停止应用程序的运行并开启GC线程，然后开始进行标记工作，按照根搜索算法，标记完以后，对象的状态如下图

image.png

可以看到，按照根搜索算法，所有从root对象可达的对象就被标记为了存活的对象，此时已经完成了第一阶段标记。接下来，就要执行第二阶段清除了，那么清除完以后，剩下的对象以及对象的状态如下图所示：

image.png
可以看到，没有被标记的对象将会回收清除掉，而被标记的对象将会留下，并且将标记重新归0。接下来唤醒停止的程序线程，让程序继续运行即可。

优缺点

可以看到，标记清除法解决了引用计数法中的循环引用问题，没有从root结点引用的对象会被回收
缺点：
效率较低，标记和清除两个动作都需要遍历所有的对象，并且在GC时，需要禁止应用程序，对于交互性要求比较高的应用而言，这个体验是非常差的。
通过标记清除算法清理出来的内存，碎片化较为严重，因为被回收的对象可能存在于内存的各个角落，所以清理出来的内存是不连贯的。

标记压缩算法

标记压缩算法是在标记清除算法的基础之上，做了优化改进的算法。和标记清除算法一样，也是从根节点开始，对对象的引用进行标记，在清理阶段，并不是简单的清理未标记的对象，而是将存活的对象压缩到内存的一端，然后清理边界以外的垃圾，从而解决了碎片画的问题。

原理

image.png

优缺点

优缺点同标记清除算法，解决了标记清除算法的碎片化问题，同时，标记压缩算法多了一步，对象移动内存位置的步骤，其效率也有一定的影响。

复制算法

复制算法的核心就是，将原有的内存空间一分为二，每次只用其中的一块，在垃圾回收时，将正在使用的对象复制到；另一个内存空间中，然后将该内存空间清空，交换两个内存的角色，完成垃圾的回收。
如果内存中的垃圾对象较多，需要复制的对象就较少，这种情况下适合使用该方式且效率比较高，反之，则不合适。

image.png

JVM中年轻代内存空间

young GC:
在GC开始的时候，对象只会存在于Eden区和"From"的Survivor区，Survivor区"To"是空的。
紧接着进行GC，Eden区中所有存活的对象都会被复制到“To”,而在“From”区中，仍存活的对象会根据他们的年龄值来决定去向。年龄达到一定值(年龄阈值，可以通过-XX:MaxTenuringThreshold来设置)的对象会被移动到年老代中，没有达到阈值的对象会被复制到“To”区域。
经过这次GC后，Eden区和From区已经被清空。这个时候，“From”和“To”会交换他们的角色，也就是新的“To”就是上次GC前的“From”，新的“From”就是上次GC前的“To”。不管怎样，都会保证名为To的Survivor区域是空的。
GC会一直重复这样的过程，直到“To”区被填满，“To”区被填满之后，会将所有对象移动到年老代中。

优缺点

优点：
在垃圾对象多的情况下，效率较高
清理后，内存无碎片
缺点：在垃圾对象少的情况下，不适用，如：老年代内存
分配的2块内存空间，在同一个时刻，只能使用一半，内存使用率较低。

分代算法

根据回收对象的特点进行选择，在jvm中，年轻代适合使用复制算法，老年代适合使用标记清除或标记压缩算法

垃圾回收机制和调用System.gc()的区别？

1.垃圾手机算法的核心思想

Java语言建立了垃圾收集机制，用以跟踪正在使用的对象和并回收不再使用的对象。
该机制可以有效防范动态内存分配中可能发生的两个危险：因内存垃圾过多而引发的内存耗尽，以及不恰当的内存释放造成的内存非法引用

垃圾收集算法的核心思想是：

对虚拟机可用内存空间，即堆空间中的对象进行识别，如果对象正在被引用，那么称其为存活对象，反之，如果对象不在被引用，则为垃圾对象，可以回收其占据的空间，用于在分配。

2.触发主GC(Garbage Collector)的条件

JVM进行次GC的频率很高，但因为这种GC占用时间极短，所以对系统产生的影响不大。更值得关注的是主GC的触发条件，因为它对系统影响很明显。有以下两个条件会触发主GC:
①当应用程序空闲时，即没有应用线程在运行时，GC会被调用。因为GC在优先级最低的线程中进行，所以当应用忙时，GC线程就不会被调用，但以下条件除外。
②Java堆内存不足时，GC会被调用。当应用线程在运行，并在运行过程中创建对象，若这时内存空间不足，JVM就会强制地调用GC线程，以便回收内存用于新的分配。若GC一次之后仍不能满足内存分配的要求，JVM会进行两次GC作进一步的尝试，若仍无法满足要求，则JVM将报“out of memory”的错误，Java应用将停止。
由于是否进行主GC由JVM根据系统环境决定，而系统环境在不断的变化当中，所以主GC的运行具有不确定性，无法预计它何时必然出现，但可以确定的是对一个长期运行的应用来说，其主GC是反复进行的。

3.减少GC开销的措施

根据上述GC的机制，程序的运行会直接影响系统环境的变化，从而影响GC的触发。(若不针对GC的特点进行设计和编码，就会出现内存驻留等一系列负面影响)
为了避免这些影响，基本的原则就是尽可能地减少垃圾和减少GC过程中的开销。具体措施包括以下几个方面：
(1)不要显示调用System.gc()
此函数建议JVM进行主GC，虽然只是建议而非一定，但很多情况下它会触发主GC，从而增加主GC的频率，也即增加了间歇性停顿的次数。
（2）尽量减少临时对象的使用
临时对象在跳出函数调用后，会成为垃圾，少用临时变量就相当于减少了垃圾的产生，从而延长了出现上述第二个触发条件出现的时间，减少了主GC的机会。
（3）对象不用时最好显示置为Null
一般而言，为Null的对象都会被作为垃圾处理，所以将不用的对象显示地设为Null，有利于GC收集器判定垃圾，从而提高了GC的效率。
（4）尽量使用StringBuffer，而不用String来累加字符串
由于String是固定长度的字符串对象，累加String对象时，并非在一个String对象中扩增，而是重新创建String对象(如Str5 = Str1+Str2+Str3+Str4，这条语句执行过程中会产生多个垃圾对象，因为对次作"+"操作时都必须创建新的String对象，但这些过度对象对系统来说是没有实际意义的，只会增加更多的垃圾)避免这种情况可以改用StringBuffer来累加字符串，因StringBuffer是可以变长的，它在原有基础上进行扩增，不会产生中间对象。
（5）能用基本类型如Int，Long,就不用Integer，Long对象。
基本类型变量占用的内存资源比相应对象占用的少的多，如果没有必要，最好使用基本变量。
（6）尽量少用静态对象变量
静态变量属于全局变量，不会被GC回收，它们会一直占用内存。
（7）分散对象创建或删除的时间
集中在短时间内大量创建新对象，特别是对大对象，会导致突然需要需要大量内存，JVM在面临这种情况时，只能进行主GC，以回收内存或整合内存碎片，从而增加主GC的频率，集中删除对象，道理也是一样的。它使得突然出现了大量的垃圾对象，空闲空间必然减少，从而大大增加了下一次创建新对象时强制主GC的机会。

System.gc()使用介绍：

Java中的内存分配是随着new一个新的对象来实现的，这个很简单，而且女也还是有一些可以“改进”内存回收的机制的，其中最显眼的就是System.gc()函数
其实这个gc()函数的作用只是提醒虚拟机:程序员希望进行一次垃圾回收。但是他不能保证垃圾回收一定会进行，而且具体什么时候进行是取决于具体的虚拟机的，不同的虚拟机有不同的对策。

gc()进行回收的准则是什么？也就是说什么样的对象可以被回收？

简单来说就是:没有被任何可达变量指向的对象，这里的可达意思是能够找到的(没有任何可达变量指向你，你还有活下去的理由吗?你就是那活下去谁能找到你呢？)
所以说，C++中将释放了的指针置为null的习惯要保留到Java中，因为这有可能是你释放内存的唯一途径。
不要频繁使用gc函数。
保持代码健壮（记得将不用的变量置为null），让虚拟机去管理内存。

类加载过程

1.什么是Java的类加载过程

一个Java文件从编码完成到最终执行，一般主要包括编译和运行两个过程
编译：将java文件通过javac命令编译成class文件(字节码)
运行:将class文件交给jvm执行

类加载过程：JVM将字节码中类信息加载进内存，并解析生成对象的class对象的过程(JVM不是一开始就把所有的类都加载进内存中，而是只有第一次遇到某个需要运行的类时才会加载，而且只加载一次)

Java的类加载过程

Java的类加载过程
Java类加载的过程主要分为加载、链接、初始化三个部分，而链接又可以细分为验证、准备、解析

加载

加载是指把class字节码文件从各个来源通过类加载器装载入内存，主要完成以下三件事：
1.通过一个类的全限定名来获取此定义此类的二进制字节流
2.将这个字节流所代表的静态存储结构转化为方法取得运行时数据结构
3.在内存中生成一个代表此类的java.lang.class的对象，作为方法区这个类的访问入口
class字节码来源:
1.本地路径下编译生成class文件
2.jar、war、ear包中的class文件
3.远程网络调用的class文件
4.动态代理实时编译的class文件
类加载器：
1.启动类加载器
2.扩展类加载器
3.应用类加载器
4.用户自定义类加载器

什么是类加载器

通过一个类的全限定名来获取描述此类的二进制字节流，这个动作是在JVM外部实现的，实现这个动作的代码模块称为类加载器(光碟=类，光驱=类加载器);对于任意一个类，都需要由加载它的类加载器和这个类本身一同确立其在JVM中的唯一性，每一个类加载器都拥有一个独立的类名称空间(两个类的内容相同，但类加载器不同，则这两个类就是不同的)

为什么需要自定义类加载器？

1.由于Java代码很容易被反编译，如果需要对自己的代码加密的话，可以对编译后的代码进行加密，然哦户在通过实现自己的自定义类加载器进行解密，最后在加载
2.class文件来源可能不标准，需要自己实现一个类加载器，从指定源进行加载

验证

作用：保证加载进来的字节流符合JVM规范，防止造成安全错误
内容：
1.对文件格式的验证：长两种是否有不被支持的常量?文件中是否有不规范的或者附加的其他信息？
2.对元数据的验证：该类是否继承了被final修饰的类？类中的字段、方法是否与父类冲突？是否出现了不合理的重载
3.对字节码的验证：类型转换时候合理？
4.对符号引用的验证：校验符号引用中通过全限定名是否能找到对应的类？校验符号引用中的方文星是否可被当前类访问？

准备

准备主要是为类变量分配内存，并赋予初始值(并非代码中赋予的值，而是JVM根据不同变量类型的默认初始值，但对于常量类或枚举，会赋予实例化对应的值)

解析

解析是将常量池的符号引用替换为直接引用的过程
符号引用：能够唯一性识别一个方法、变量、类的相关信息的字符串
直接引用：一个内存地址或一个偏移量
如：调用地址为0x2019的hello()方法，hello为符号引用，0x2019为直接引用

初始化

初始化主要完成对类变量的初始化，也就是执行类构造器的过程
该类的父类尚未初始化，也就是执行类构造器的过程
该类的父类尚未初始化，则优先初始化其父类
该类包含多个静态变量和静态代码块，则按照自上而下的顺序依次执行。

双亲委派机制

双亲委派机制是指如果一个类加载器收到了类加载的请求，它首先不会自己去尝试加载这个类，而是把这个请求委派给父类加载器去完成，当父类加载器反馈自己无法完成这个请求时，子类加载器才会尝试自己去加载完成
好处：维护了类环境的稳定和高效运转
实现：在类加载过程中，先检查请求的类是否已经被加载过了，如果没有就调用父类的加载器加载，如果父类加载器为null，就默认使用启动类加载器作为父类加载器，如果父类加载失败，就会抛出classNotFoundException类，在调用自己的findClass方法进行加载

反射

1.什么是反射

反射是在运行状态中，对于任意一个类，都知道这个类的所有属性和方法；对于任意一个类，都能够调用它的任意一个方法和属性；这种动态获取的信息以及动态调用对象的方法的功能称为Java语言的反射机制。

2.哪里用到反射机制？

①JDBC中，利用反射动态加载了数据库驱动程序
②Web服务器中利用反射调用了Servlet的服务方法
③Eclipse等开发工具利用反射动态剖析对象的类型与结构，动态提示对象的属性和方法。
④很多对象都用到反射机制，注入属性，调用方法，如Spring。

3.反射机制的优缺点？

优点：可以动态执行，在运行期间根据业务功能动态执行方法、访问属性，最大限度发挥了java的灵活性。
缺点：对性能有影响，这类操作总是慢于直接执行java代码。

4.动态代理是什么？有哪些应用？

动态代理是运行时动态生成代理类
动态代理的应用有Spring AOP数据查询、测试框架的后端mock、rpc、Java注解对象获取等。

5.怎么实现动态代理？

JDK原生动态代理和cglib动态代理
JDK原生动态代理是基于接口实现的，而cglib是基于继承当前类的子类实现的。

6.如何使用Java的反射？

①通过一个全限类名创建一个对象
Class.forName("全限类名")；例如：com.mysql.jdbc.Driver Driver类已经被加载到jvm中，并且完成了类的初始化工作就行了。
类名.class;获取Class<?>clz对象
对象.getClass();
②获取构造器对象，通过构造器new出一个对象
Ckazz.getConstructor([String.class]);
通过class对象获得一个实例对象(就相当new类名() 无参构造器)
Cls.newInstance();
③通过class对象获得一个属性对象
Field c=cls.getFields()：获得某个类的所有的公共（public）的字段，包括父类中的字段。
Field c=cls.getDeclaredFields()：获得某个类的所有声明的字段，即包括public、private和proteced，但是 不包括父类的声明字段
④通过class对象获得一个方法对象
Cls.getMethod(“方法名”,class……parameaType);（只能获取公共的）
Cls.getDeclareMethod(“方法名”);（获取任意修饰的方法，不能执行私有）
M.setAccessible(true);（让私有的方法可以执行）
让方法执行. Method.invoke(obj实例对象,obj可变参数);-----（是有返回值的）

因简书文字受限，新的知识点请移步新的文章