Day17 集合与数据结构

学习目标

• 能够说出List接口的常用实现类集合的区别
• 能够说出Set接口的常用实现类集合的区别
• 能够说出Map接口的常用实现类集合的区别
• 能够说出Set系列与Map系列集合的关系
• 能够说出Collection系列与Map系列集合的区别
• 能够画出Collection和Map等所有常用集合的关系图
• 掌握Collections集合工具类的使用
• 对常见数据结构有初步了解
• 掌握动态数组的实现方式
• 理解单链表与双链表的实现方式
• 理解哈希表的实现方式

1 数据结构

数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

（1）数据的逻辑结构指反映数据元素之间的逻辑关系，而与他们在计算机中的存储位置无关：

• 散列结构：元素之间除了“同属一个集合” 的相互关系外，别无其他关系；例如：同一个班级的学生信息
• 线性结构：元素存在一对一的相互关系；例如：队列（先进先出）、栈（先进后出）等
• 树形结构：元素存在一对多的相互关系；例如：直系族谱
• 图形结构：元素存在多对多的相互关系；例如：好友关系图

（2）数据的物理结构/存储结构：是描述数据具体在内存中的存储（如：数组结构、链式结构、索引结构、哈希结构）等，一种数据逻辑结构可表示成一种或多种物理存储结构。

• 数组结构：元素在内存中是连续存储的，即元素存储在一整块连续的存储空间中，此时根据索引的查询效率是非常高的，因为可以根据下标索引直接一步到位找到元素位置，如果在数组末尾添加和删除元素效率也非常高。缺点是，如果事先申请足够大的内存空间，可能造成空间浪费，如果事先申请较小的内存空间，可能造成频繁扩容导致元素频繁搬家。另外，在数组中间添加、删除元素操作，就需要移动元素，此时效率也要打折。
• 链式结构：元素在内存中是不要求连续存储的，但是元素是封装在结点当中的，结点中需要存储元素数据，以及相关结点对象的引用地址。结点与结点之间可以是一对一的关系，也可以一对多的关系，比如：链表、树等。遍历链式结构只能从头遍历，对于较长的链表来说查询效率不高，对于树结构来说，查询效率比链表要高一点，因为每次可以确定一个分支，从而排除其他分支，但是相对于数组来说，还是数组[下标]的方式更快。树的实现方式有很多种，无非就是在添加/删除效率 与 查询效率之间权衡。
• 索引结构：元素在内存中是不要求连续存储的，但是需要有单独的一个索引表来记录每一个元素的地址，这种结构根据索引的查询效率很高，但是需要额外存储和维护索引表。
• 哈希结构：元素的存储位置需要通过其hashCode值来计算，查询效率也很高，但是要考虑和解决好哈希冲突问题。

数据结构和算法是一门完整并且复杂的课程。

Java的核心类库中提供很多数据结构对应的集合类型，例如动态数组、双向链表、顺序栈、链式栈、队列、双端队列、红黑树、哈希表等等。

2 动态数组

2.1 动态数组的特点

逻辑结构特点：线性结构

物理结构特点：

• 申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。

• 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。

例如：整型数组

例如：对象数组

2.2 自定义动态数组

package com.atguigu.array;import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;public class MyArrayList<E> implements Iterable<E>{private Object[] all;private int total;public MyArrayList(){all = new Object[10];}public void add(E e) {ensureCapacityEnough();all[total++] = e;}private void ensureCapacityEnough() {if(total >= all.length){all = Arrays.copyOf(all, all.length + (all.length>>1));}}public void insert(int index, E value) {//添加元素的下标检查addCheckIndex(index);//是否需要扩容ensureCapacityEnough();//是否需要移动元素if(total-index > 0) {System.arraycopy(all, index, all, index+1, total-index);}all[index]=value;total++;}private void addCheckIndex(int index) {if(index<0 || index>total){throw new IndexOutOfBoundsException(index+"越界");}}public void delete(E e) {int index = indexOf(e);if(index==-1){throw new NoSuchElementException(e+"不存在");}delete(index);}public void delete(int index) {//删除元素的下标检查checkIndex(index);//是否需要移动元素if(total-index-1 > 0) {System.arraycopy(all, index+1, all, index, total-index-1);}all[--total] = null;}private void checkIndex(int index) {if(index<0 || index>total){throw new IndexOutOfBoundsException(index+"越界");}}public void update(int index, E value) {//更新修改元素的下标检查checkIndex(index);all[index] = value;}public void update(E old, E value) {int index = indexOf(old);if(index!=-1){update(index, value);}}public boolean contains(E e) {return indexOf(e) != -1;}public int indexOf(E e) {int index = -1;if(e==null){for (int i = 0; i < total; i++) {if(e == all[i]){index = i;break;}}}else{for (int i = 0; i < total; i++) {if(e.equals(all[i])){index = i;break;}}}return index;}public int lastIndexOf(E e) {int index = -1;if(e==null){for (int i = total-1; i >= 0; i--) {if(e == all[i]){index = i;break;}}}else{for (int i = total-1; i >= 0; i--) {if(e.equals(all[i])){index = i;break;}}}return index;}public E get(int index) {//获取元素的下标检查checkIndex(index);return (E) all[index];}public int size() {return total;}public Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private int cursor;@Overridepublic boolean hasNext() {return cursor < total;}@Overridepublic E next() {return (E) all[cursor++];}@Overridepublic void remove() {MyArrayList.this.delete(--cursor);}}
}

测试类：

package com.atguigu.list;import java.util.Iterator;public class TestMyArrayList {public static void main(String[] args) {MyArrayList<String> my = new MyArrayList<>();my.add("hello");my.add("java");my.add("java");my.add("world");my.add(null);my.add(null);my.add("atguigu");my.add("list");my.add("data");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("-------------------------");System.out.println("在[1]插入尚硅谷后：");my.insert(1, "尚硅谷");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("--------------------------");System.out.println("删除[1]位置的元素后：");my.delete(1);System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("删除atguigu元素后：");my.delete("atguigu");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("删除null元素后：");my.delete(null);System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("------------------------------");System.out.println("替换[3]位置的元素为尚硅谷后：");my.update(3, "尚硅谷");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("替换java为JAVA后：");my.update("java", "JAVA");System.out.println("元素个数：" + my.size());for (String s : my) {System.out.println(s);}System.out.println("------------------------------------");System.out.println("是否包含java：" +my.contains("java"));System.out.println("java的位置：" + my.indexOf("java"));System.out.println("haha的位置：" + my.indexOf("haha"));System.out.println("[0]位置元素是：" + my.get(0));System.out.println("------------------------------------");System.out.println("删除字符串长度>4的元素后：");Iterator<String> iterator = my.iterator();while(iterator.hasNext()) {String next = iterator.next();if(next != null && next.length()>4) {iterator.remove();}}System.out.println("元素个数：" + my.size());for (String string : my) {System.out.println(string);}}
}

2.3 ArrayList与Vector的区别？

核心类库中List接口有两个实现类：Vector和ArrayList。它们的底层物理结构都是数组，我们称为动态数组。

（1）ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。

（2）动态数组的扩容机制不同，ArrayList扩容为原来的1.5倍，Vector扩容增加为原来的2倍。

（3）数组的初始化容量，如果在构建ArrayList与Vector的集合对象时，没有显式指定初始化容量，那么Vector的内部数组的初始容量默认为10，而ArrayList在JDK1.6及之前的版本也是10，JDK1.7之后的版本ArrayList初始化为长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。

ArrayList在第1次添加时再创建数组是为了避免浪费。因为很多方法的返回值是ArrayList类型，需要返回一个ArrayList的对象，例如：后期从数据库查询对象的方法，返回值很多就是ArrayList。有可能你要查询的数据不存在，要么返回null，要么返回一个没有元素的ArrayList对象。

（4）Vector因为版本古老，支持Enumeration 迭代器。但是该迭代器不支持快速失败。而Iterator和ListIterator迭代器支持快速失败。如果在迭代器创建后的任意时间从结构上修改了向量（通过迭代器自身的 remove 或 add 方法之外的任何其他方式），则迭代器将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就完全失败，而不是冒着在将来不确定的时间任意发生不确定行为的风险。

2.4 ArrayList部分源码分析

1、JDK1.6构造器

    public ArrayList() {this(10);//指定初始容量为10}public ArrayList(int initialCapacity) {super();//检查初始容量的合法性if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);//数组初始化为长度为initialCapacity的数组this.elementData = new Object[initialCapacity];}

2、JDK1.7构造器

    private static final int DEFAULT_CAPACITY = 10;//默认初始容量10private static final Object[] EMPTY_ELEMENTDATA = {};public ArrayList() {super();this.elementData = EMPTY_ELEMENTDATA;//数组初始化为一个空数组}public boolean add(E e) {//查看当前数组是否够多存一个元素ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {if (elementData == EMPTY_ELEMENTDATA) {//如果当前数组还是空数组//minCapacity按照 默认初始容量和minCapacity中的的最大值处理minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}//看是否需要扩容处理ensureExplicitCapacity(minCapacity);}//...

3、JDK1.8构造器

	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//初始化为空数组}

4、添加与扩容

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public boolean add(E e) {//查看当前数组是否够多存一个元素ensureCapacityInternal(size + 1);  // Increments modCount!!//存入新元素到[size]位置，然后size自增1elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {//如果当前数组还是空数组if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}//查看是否需要扩容ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {modCount++;//修改次数加1// 如果需要的最小容量  比  当前数组的长度  大，即当前数组不够存，就扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//当前数组容量int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组容量是旧数组容量的1.5倍//看旧数组的1.5倍是否够if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//看旧数组的1.5倍是否超过最大数组限制if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//复制一个新数组elementData = Arrays.copyOf(elementData, newCapacity);}public void add(int index, E element) {rangeCheckForAdd(index);//看是否需要扩容ensureCapacityInternal(size + 1);  // Increments modCount!!//将[index]以及后面的元素往右移动System.arraycopy(elementData, index, elementData, index + 1,size - index);//将新元素添加到 elementData[index]elementData[index] = element;//元素个数增加size++;}private void rangeCheckForAdd(int index) {//elementData实际已经存储[0,size-1]//可插入的位置[0,size]if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

5、删除元素

    public boolean remove(Object o) {//先找到o在当前ArrayList的数组中的下标//分o是否为空两种情况讨论if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {//null值用==比较fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {//非null值用equals比较fastRemove(index);return true;}}return false;}private void fastRemove(int index) {modCount++;//修改次数加1//需要移动的元素个数int numMoved = size - index - 1;//如果需要移动元素，就用System.arraycopy移动元素if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);//将elementData[size-1]位置置空，让GC回收空间，元素个数减少elementData[--size] = null; // clear to let GC do its work}

    public E remove(int index) {rangeCheck(index);//检验index是否合法modCount++;//修改次数加1//取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素E oldValue = elementData(index);//需要移动的元素个数int numMoved = size - index - 1;//如果需要移动元素，就用System.arraycopy移动元素if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);//将elementData[size-1]位置置空，让GC回收空间，元素个数减少elementData[--size] = null; // clear to let GC do its workreturn oldValue;}private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

	@Overridepublic boolean removeIf(Predicate<? super E> filter) {Objects.requireNonNull(filter);//filter实参对象不能为nullint removeCount = 0;//记录删除元素的个数final BitSet removeSet = new BitSet(size);//记录要被删除的元素的下标final int expectedModCount = modCount;final int size = this.size;for (int i=0; modCount == expectedModCount && i < size; i++) {@SuppressWarnings("unchecked")final E element = (E) elementData[i];if (filter.test(element)) {//满足删除条件removeSet.set(i);//把i记录到removeSet中removeCount++;//要删除元素个数增加}}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}// shift surviving elements left over the spaces left by removed elementsfinal boolean anyToRemove = removeCount > 0;//有需要删除的元素if (anyToRemove) {final int newSize = size - removeCount;//删除后的元素个数/*如果[i]下标的元素不被删除，那么就正常返回i下标值；如果[i]下标的元素要被删除，那么removeSet.nextClearBit(i)返回[i]后面不被删除的元素的下标。例如：ArrayList中元素总个数有8个。ArrayList中的要删除的元素下标是[1,3,4,6]i=0,j=0i = removeSet.nextClearBit(0);  i=0 i++,j++i = removeSet.nextClearBit(1);  i=2 i++,j++（[1]要被删除）i = removeSet.nextClearBit(2);  i=5 i++,j++（[3,4]要被删除）i = removeSet.nextClearBit(6);  i=5 i++,j++（[3,4]要被删除）elementData[0] = elementData[0];elementData[1] = elementData[2];elementData[2] = elementData[5];elementData[3] = elementData[7];				*/for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {i = removeSet.nextClearBit(i);elementData[j] = elementData[i];}//清空[newSize, size-1]位置的元素for (int k=newSize; k < size; k++) {elementData[k] = null;  // Let gc do its work}this.size = newSize;if (modCount != expectedModCount) {throw new ConcurrentModificationException();}modCount++;}return anyToRemove;}

6、get/set元素

    public E set(int index, E element) {rangeCheck(index);//检验index是否合法//取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最后返回被替换的元素E oldValue = elementData(index);//用element替换[index]位置的元素elementData[index] = element;return oldValue;}public E get(int index) {rangeCheck(index);//检验index是否合法return elementData(index);//返回[index]位置的元素}E elementData(int index) {return (E) elementData[index];}

7、查询元素

    public int indexOf(Object o) {//分为o是否为空两种情况if (o == null) {//从前往后找for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}public int lastIndexOf(Object o) {//分为o是否为空两种情况if (o == null) {//从后往前找for (int i = size-1; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = size-1; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}public boolean contains(Object o) {return indexOf(o, 0) >= 0;}	//从[index]位置开始查询元素下标public synchronized int indexOf(Object o, int index) {if (o == null) {for (int i = index ; i < elementCount ; i++)if (elementData[i]==null)return i;} else {for (int i = index ; i < elementCount ; i++)if (o.equals(elementData[i]))return i;}return -1;}

8、迭代器Itr

	public Iterator<E> iterator() {return new Itr();}//实现了Iterator接口private class Itr implements Iterator<E> {//游标，当前迭代器遍历到动态数组哪个位置了int cursor;       // index of next element to return//上一个迭代的位置int lastRet = -1; // index of last element returned; -1 if no such//后面单独讲int expectedModCount = modCount;public boolean hasNext() {//有效元素的范围[0,size-1]return cursor != size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();//用i记录当前迭代器遍历到动态数组哪个位置了int i = cursor;//加这个判断是以防用户在next()方法之前没有调用hasNext()方法if (i >= size)throw new NoSuchElementException();//用一个变量记录了当前动态数组的elementDataObject[] elementData = ArrayList.this.elementData;//和并发有关if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;//下次访问的元素的下标return (E) elementData[lastRet = i];//i是本次遍历的数组的下标位置，用lastRet记录，对应下一次调用next方法，lastRet就是上次的下标//变量是在remove方法中用到了}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {//删除的是你刚刚调用next()方法取走的位置的元素ArrayList.this.remove(lastRet);cursor = lastRet;//因为删除元素，[cursor]会被往前移动，所以这里要cursor = lastRetlastRet = -1;//因为[lastRet]位置被删除了，然后不存在了，如果连续调用remove()就会报错expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}

2.5 Vector部分源码分析

1、构造器

    public Vector() {this(10);//指定初始容量initialCapacity为10}public Vector(int initialCapacity) {this(initialCapacity, 0);//指定capacityIncrement增量为0}//initialCapacity：初始化容量//capacityIncrement：扩容时的增量public Vector(int initialCapacity, int capacityIncrement) {super();//判断了形参初始容量initialCapacity的合法性if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);//创建了一个Object[]类型的数组this.elementData = new Object[initialCapacity];//默认是10//增量，默认是0，如果是0，后面就按照2倍增加，如果不是0，后面就按照你指定的增量进行增量this.capacityIncrement = capacityIncrement;}

2、添加与扩容

//synchronized意味着线程安全的   public synchronized boolean add(E e) {modCount++;//看是否需要扩容ensureCapacityHelper(elementCount + 1);//把新的元素存入[elementCount]，存入后，elementCount元素的个数增1elementData[elementCount++] = e;return true;}private void ensureCapacityHelper(int minCapacity) {// overflow-conscious code//看是否超过了当前数组的容量if (minCapacity - elementData.length > 0)grow(minCapacity);//扩容}private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//获取目前数组的长度//如果capacityIncrement增量是0，新容量 = oldCapacity的2倍//如果capacityIncrement增量是不是0，新容量 = oldCapacity + capacityIncrement增量;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);//如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容minCapacityif (newCapacity - minCapacity < 0)newCapacity = minCapacity;//如果新容量超过了最大数组限制，那么单独处理if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//把旧数组中的数据复制到新数组中，新数组的长度为newCapacityelementData = Arrays.copyOf(elementData, newCapacity);}

3 链表

3.1 链表的特点

逻辑结构：线性结构

物理结构：不要求连续的存储空间

存储特点：数据必须封装到“结点”中，结点包含多个数据项，数据值只是其中的一个数据项，其他的数据项用来记录与之有关的结点的地址。

例如：以下列出几种常见的链式存储结构（当然远不止这些）

3.2 自定义双链表（选讲）

package com.atguigu.link;import java.util.Iterator;public class MyLinkedList<E> implements Iterable<E>{private Node first;private Node last;private int total;public void add(E e){Node newNode = new Node(last, e, null);if(first == null){first = newNode;}else{last.next = newNode;}last = newNode;total++;}public int size(){return total;}public void delete(Object obj){Node find = findNode(obj);if(find == null){return ;}Node prev = find.prev;Node next = find.next;if(prev != null){prev.next = next;find.prev = null;}else{first = next;}if(next != null){next.prev = prev;find.next = null;}else{last = prev;}find.data = null;total--;}private Node findNode(Object obj){Node node = first;Node find = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}node = node.next;}}return find;}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value){Node find = findNode(old);if(find != null){find.data = value;}}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node node = first;private Node lastVisitNode;@Overridepublic boolean hasNext() {return node!=null;}@Overridepublic E next() {E value = node.data;node = node.next;return value;}@Overridepublic void remove() {MyLinkedList.this.delete(lastVisitNode.data);}}private class Node{Node prev;E data;Node next;Node(Node prev, E data, Node next) {this.prev = prev;this.data = data;this.next = next;}}
}

自定义双链表测试：

package com.atguigu.list;public class TestMyLinkedList {public static void main(String[] args) {MyLinkedList<String> my = new MyLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");my.add("atguigu");System.out.println("一共有：" + my.size());System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的结果：");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替换java,null后：");my.update("java","JAVA");my.update(null,"chai");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("删除hello，JAVA,null，atguigu后：");my.delete("hello");my.delete("JAVA");my.delete(null);my.delete("atguigu");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}}
}

3.3 核心类库中LinkedList源码分析

Java中有双链表的实现：LinkedList，它是List接口的实现类。

1、结点类型

	int size = 0;Node<E> first;//记录第一个结点的位置Node<E> last;//记录最后一个结点的位置private static class Node<E> {E item;//元素数据Node<E> next;//下一个结点Node<E> prev;//前一个结点Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}

2、添加结点

    public boolean add(E e) {linkLast(e);//默认把新元素链接到链表尾部return true;}void linkLast(E e) {final Node<E> l = last;//用l 记录原来的最后一个结点//创建新结点final Node<E> newNode = new Node<>(l, e, null);//现在的新结点是最后一个结点了last = newNode;//如果l==null，说明原来的链表是空的if (l == null)//那么新结点同时也是第一个结点first = newNode;else//否则把新结点链接到原来的最后一个结点的next中l.next = newNode;//元素个数增加size++;//修改次数增加modCount++;}public void add(int index, E element) {checkPositionIndex(index);//检查index范围if (index == size)//如果index==size，连接到当前链表的尾部linkLast(element);elselinkBefore(element, node(index));}Node<E> node(int index) {// assert isElementIndex(index);//如果index<size/2，就从前往后找目标结点if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {//否则从后往前找目标结点Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}//把新结点插入到[index]位置的结点succ前面void linkBefore(E e, Node<E> succ) {//succ是[index]位置对应的结点// assert succ != null;final Node<E> pred = succ.prev; //[index]位置的前一个结点//新结点的prev是原来[index]位置的前一个结点//新结点的next是原来[index]位置的结点final Node<E> newNode = new Node<>(pred, e, succ);//[index]位置对应的结点的prev指向新结点succ.prev = newNode;//如果原来[index]位置对应的结点是第一个结点，那么现在新结点是第一个结点if (pred == null)first = newNode;elsepred.next = newNode;//原来[index]位置的前一个结点的next指向新结点size++;modCount++;}private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}

3、删除结点

    public boolean remove(Object o) {//分o是否为空两种情况if (o == null) {//找到o对应的结点xfor (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);//删除x结点return true;}}} else {//找到o对应的结点xfor (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);//删除x结点return true;}}}return false;}E unlink(Node<E> x) {//x是要被删除的结点// assert x != null;final E element = x.item;//被删除结点的数据final Node<E> next = x.next;//被删除结点的下一个结点final Node<E> prev = x.prev;//被删除结点的上一个结点//如果被删除结点的前面没有结点，说明被删除结点是第一个结点if (prev == null) {//那么被删除结点的下一个结点变为第一个结点first = next;} else {//被删除结点不是第一个结点//被删除结点的上一个结点的next指向被删除结点的下一个结点prev.next = next;//断开被删除结点与上一个结点的链接x.prev = null;//使得GC回收}//如果被删除结点的后面没有结点，说明被删除结点是最后一个结点if (next == null) {//那么被删除结点的上一个结点变为最后一个结点last = prev;} else {//被删除结点不是最后一个结点//被删除结点的下一个结点的prev执行被删除结点的上一个结点next.prev = prev;//断开被删除结点与下一个结点的连接x.next = null;//使得GC回收}//把被删除结点的数据也置空，使得GC回收x.item = null;//元素个数减少size--;//修改次数增加modCount++;//返回被删除结点的数据return element;}

	public E remove(int index) {checkElementIndex(index);//检查index是否合法，合法的位置[0,size-1]return unlink(node(index));}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}Node<E> node(int index) {// assert isElementIndex(index);//index靠左半边，从first开始查找更快if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {//index靠右半边，从last开始查找更快Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}

4、查询结点

	public E get(int index) {checkElementIndex(index);//node()返回了链表的[index]位置的结点return node(index).item;}

3.4 自定义单链表（选讲）

package com.atguigu.link;import java.util.Iterator;public class MyOneWayLinkedList<E>  implements Iterable<E>{private Node head;private int total;public void add(E e){Node newNode = new Node(e, null);if(head == null){head = newNode;}else{Node node = head;while(node.next!=null){node = node.next;}node.next = newNode;}total++;}private Node[] findNodes(Object obj){Node[] result = new MyOneWayLinkedList.Node[2];Node node = head;Node find = null;Node beforeFind = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}beforeFind = node;node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}beforeFind = node;node = node.next;}}result[0] = beforeFind;result[1] = find;return result;}public void delete(Object obj){Node[] nodes = findNodes(obj);Node beforeFind = nodes[0];Node find = nodes[1];if(find != null){if(beforeFind == null){head = find.next;}else {beforeFind.next = find.next;}total--;}}private Node findNode(Object obj){return findNodes(obj)[1];}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value) {Node find = findNode(old);if(find != null){find.data = value;}}public int size() {return total;}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node node = head;private Node lastVisitNode;@Overridepublic boolean hasNext() {return node != null;}@Overridepublic E next() {E value = node.data;lastVisitNode = node;node = node.next;return value;}@Overridepublic void remove() {MyOneWayLinkedList.this.delete(lastVisitNode.data);}}private class Node{E data;Node next;Node(E data, Node next) {this.data = data;this.next = next;}}
}

package com.atguigu.link;public class TestMyOneWayLinkedList{public static void main(String[] args) {MyOneWayLinkedList<String> my = new MyOneWayLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");my.add("atguigu");System.out.println("一共有：" + my.size());System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的结果：");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替换java,null后：");my.update("java","JAVA");my.update(null,"chai");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("删除hello,JAVA,null,atguigu后：");my.delete("hello");my.delete("JAVA");my.delete(null);my.delete("atguigu");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}}
}

3.5 链表与动态数组的区别

动态数组底层的物理结构是数组，因此根据索引访问的效率非常高。但是非末尾位置的插入和删除效率不高，因为涉及到移动元素。另外添加操作时涉及到扩容问题，就会增加时空消耗。

链表底层的物理结构是链表，因此根据索引访问的效率不高，但是插入和删除不需要移动元素，只需要修改前后元素的指向关系即可，而且链表的添加不会涉及到扩容问题。

如果不是根据索引操作，只是根据对象查找的话，效率都比较低，都需要按顺序查找。

链表的增删的效率一定比数组的高？不对，如果是数组末尾位置的插入和删除，效率也挺高的，不需要移动元素。

但是数组的插入可能会涉及到扩容问题。

如果是双向链表，在链表的头和尾位置插入和删除是非常方便的，因为可以直接通过first和last直接定位。

4 栈和队列

4.1 栈

堆栈是一种先进后出（FILO：first in last out）或后进先出（LIFO：last in first out）的结构。

栈只是逻辑结构，其物理结构可以是数组，也可以是链表，即栈结构分为顺序栈和链式栈。

核心类库中的栈结构有Stack和LinkdeList。Stack就是顺序栈，它是Vector的子类。LinkedList是链式栈。

体现栈结构的操作方法：

• peek()方法：查看栈顶元素，不弹出
• pop()方法：弹出栈
• push(E e)方法：压入栈

package com.atguigu.list;import org.junit.Test;import java.util.LinkedList;
import java.util.Stack;public class TestStack {@Testpublic void test1(){Stack<Integer> list = new Stack<>();list.push(1);list.push(2);list.push(3);System.out.println("list = " + list);System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());/*System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/while(!list.empty()){System.out.println("list.pop() =" + list.pop());}}@Testpublic void test2(){LinkedList<Integer> list = new LinkedList<>();list.push(1);list.push(2);list.push(3);System.out.println("list = " + list);System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());/*System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/while(!list.isEmpty()){System.out.println("list.pop() =" + list.pop());}}
}

4.2 队列

队列（Queue）是一种（但并非一定）先进先出（FIFO）的结构。

队列是逻辑结构，其物理结构可以是数组，也可以是链表。队列有普通队列、双端队列、并发队列等等，核心类库中的队列实现类有很多（后面会学到很多），LinkdeList是双端队列的实现类。

Queue除了基本的 Collection操作外，队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null 或 false，具体取决于操作）。Queue 实现通常不允许插入 元素，尽管某些实现（如 ）并不禁止插入 。即使在允许 null 的实现中，也不应该将 插入到 中，因为 也用作 方法的一个特殊返回值，表明队列不包含元素。

	抛出异常	返回特殊值
插入	add(e)	offer(e)
移除	remove()	poll()
检查	element()	peek()

Deque，名称 deque 是“double ended queue==（双端队列）==”的缩写，通常读为“deck”。此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。Deque接口的实现类有ArrayDeque和LinkedList，它们一个底层是使用数组实现，一个使用双向链表实现。

	第一个元素（头部）		最后一个元素（尾部）
	抛出异常	特殊值	抛出异常	特殊值
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
移除	removeFirst()	pollFirst()	removeLast()	pollLast()
检查	getFirst()	peekFirst()	getLast()	peekLast()

此接口扩展了 Queue接口。在将双端队列用作队列时，将得到 FIFO（先进先出）行为。将元素添加到双端队列的末尾，从双端队列的开头移除元素。从 Queue 接口继承的方法完全等效于 Deque 方法，如下表所示：

Queue 方法	等效 Deque 方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

双端队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque 方法，如下表所示：

堆栈方法	等效 Deque 方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

结论：Deque接口的实现类既可以用作FILO堆栈使用，又可以用作FIFO队列使用。

package com.atguigu.queue;import java.util.LinkedList;public class TestQueue {public static void main(String[] args) {LinkedList<String> list = new LinkedList<>();list.addLast("张三");list.addLast("李四");list.addLast("王五");list.addLast("赵六");while (!list.isEmpty()){System.out.println("list.removeFirst()=" + list.removeFirst());}}
}

5 Map

5.1 概述

现实生活中，我们常会看到这样的一种集合：IP地址与主机名，身份证号与个人，系统用户名与系统用户对象等，这种一一对应的关系，就叫做映射。Java提供了专门的集合类用来存放这种对象关系的对象，即java.util.Map<K,V>接口。

我们通过查看Map接口描述，发现Map<K,V>接口下的集合与Collection<E>接口下的集合，它们存储数据的形式不同。

• Collection中的集合，元素是孤立存在的（理解为单身），向集合中存储元素采用一个个元素的方式存储。
• Map中的集合，元素是成对存在的(理解为夫妻)。每个元素由键与值两部分组成，通过键可以找对所对应的值。
• Collection中的集合称为单列集合，Map中的集合称为双列集合。
• 需要注意的是，Map中的集合不能包含重复的键，值可以重复；每个键只能对应一个值（这个值可以是单个值，也可以是个数组或集合值）。

5.2 Map常用方法

1、添加操作

• V put(K key,V value)：添加一对键值对
• void putAll(Map<? extends K,? extends V> m)：添加一组键值对

2、删除

• void clear()：清空map
• V remove(Object key)：根据key删除一对键值对
• default boolean remove(Object key,Object value)：删除匹配的(key,value)

3、修改value（JDK1.8新增）

• default V replace(K key, V value)：找到目标key，替换value
• default boolean replace(K key,V oldValue,V newValue)：找到目标(key,value)，替换value
• default void replaceAll(BiFunction<? super K,? super V,? extends V> function)：按照指定要求替换value

4、元素查询的操作

• V get(Object key)：根据key返回value
• boolean containsKey(Object key)：判断key是否存在
• boolean containsValue(Object value)：判断value是否存在
• boolean isEmpty()：判断map是否为空
• int size()：获取键值对的数量

package com.atguigu.map;import org.junit.Test;import java.util.HashMap;
import java.util.function.BiFunction;public class TestMapMethod {@Testpublic void test1(){//创建 map对象HashMap<String, String> map = new HashMap<String, String>();//添加元素到集合map.put("黄晓明", "杨颖");map.put("文章", "马伊琍");map.put("文章", "姚笛");map.put("邓超", "孙俪");System.out.println(map.size());System.out.println(map);}@Testpublic void test2(){HashMap<String, String> map = new HashMap<String, String>();//添加模范夫妻map.put("黄晓明", "杨颖");map.put("文章", "马伊琍");map.put("邓超", "孙俪");System.out.println(map);//删除键值对map.remove("文章");System.out.println(map);map.remove("黄晓明","杨颖");System.out.println(map);}@Testpublic void test3(){HashMap<String, String> map = new HashMap<String, String>();//添加夫妻map.put("黄晓明", "杨颖");map.put("文章", "马伊琍");map.put("邓超", "孙俪");map.put("张三", null);System.out.println(map);//修改valuemap.replace("文章","姚笛");System.out.println(map);map.replace("黄晓明","杨颖", "angelababy");System.out.println(map);map.replaceAll(new BiFunction<String, String, String>() {@Overridepublic String apply(String key, String value) {return value == null ? "如花" : value;}});System.out.println(map);}@Testpublic void test4(){HashMap<String, String> map = new HashMap<String, String>();//添加元素到集合map.put("黄晓明", "杨颖");map.put("文章", "马伊琍");map.put("邓超", "孙俪");// 想要查看 谁的媳妇 是谁System.out.println(map.get("黄晓明"));System.out.println(map.get("邓超"));}
}

5.3 Map集合的遍历

Collection集合的遍历：（1）foreach（2）通过Iterator对象遍历

Map的遍历，不能支持foreach，因为Map接口没有继承java.lang.Iterable接口，也没有实现Iterator iterator()方法。只能用如下方式遍历：

（1）分开遍历：

• 单独遍历所有key：Set keySet()
• 单独遍历所有value：Collection values()

（2）成对遍历：

• 遍历所有键值对：Set<Map.Entry<K,V>> entrySet()
• 遍历的是映射关系Map.Entry类型的对象，Map.Entry是Map接口的内部接口。每一种Map内部有自己的Map.Entry的实现类。在Map中存储数据，实际上是将Key---->value的数据存储在Map.Entry接口的实例中，再在Map集合中插入Map.Entry的实例化对象，如图示：

package com.atguigu.map;import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class TestMapIterate {public static void main(String[] args) {HashMap<String,String> map = new HashMap<>();map.put("许仙", "白娘子");map.put("董永", "七仙女");map.put("牛郎", "织女");map.put("许仙", "小青");System.out.println("所有的key:");Set<String> keySet = map.keySet();for (String key : keySet) {System.out.println(key);}System.out.println("所有的value：");Collection<String> values = map.values();for (String value : values) {System.out.println(value);}System.out.println("所有的映射关系");Set<Map.Entry<String,String>> entrySet = map.entrySet();for (Map.Entry<String,String> entry : entrySet) {
//			System.out.println(entry);System.out.println(entry.getKey()+"->"+entry.getValue());}}
}

5.4 Map的实现类们

Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和Properties。其中HashMap是 Map 接口使用频率最高的实现类。

1、HashMap和Hashtable

HashMap和Hashtable都是哈希表。HashMap和Hashtable判断两个 key 相等的标准是：两个 key 的hashCode 值相等，并且 equals() 方法也返回 true。因此，为了成功地在哈希表中存储和获取对象，用作键的对象必须实现 hashCode 方法和 equals 方法。

• Hashtable是线程安全的，任何非 null 对象都可以用作键或值。

• HashMap是线程不安全的，并允许使用 null 值和 null 键。

示例代码：添加员工姓名为key，薪资为value

package com.atguigu.map;import org.junit.Test;import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
import java.util.Set;public class TestHashMap {@Testpublic void test01(){HashMap<String,Double> map = new HashMap<>();map.put("张三", 10000.0);//key相同，新的value会覆盖原来的value//因为String重写了hashCode和equals方法map.put("张三", 12000.0);map.put("李四", 14000.0);//HashMap支持key和value为null值String name = null;Double salary = null;map.put(name, salary);Set<Map.Entry<String, Double>> entrySet = map.entrySet();for (Map.Entry<String, Double> entry : entrySet) {System.out.println(entry);}}@Testpublic void test02(){Hashtable<String,Double> map = new Hashtable<>();map.put("张三", 10000.0);//key相同，新的value会覆盖原来的value//因为String重写了hashCode和equals方法map.put("张三", 12000.0);map.put("李四", 14000.0);//Hashtable不支持key和value为null值/*String name = null;Double salary = null;map.put(name, salary);*/Set<Map.Entry<String, Double>> entrySet = map.entrySet();for (Map.Entry<String, Double> entry : entrySet) {System.out.println(entry);}}
}

2、LinkedHashMap

LinkedHashMap 是 HashMap 的子类。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。

示例代码：添加员工姓名为key，薪资为value

package com.atguigu.map;import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;public class TestLinkedHashMap {public static void main(String[] args) {LinkedHashMap<String,Double> map = new LinkedHashMap<>();map.put("张三", 10000.0);//key相同，新的value会覆盖原来的value//因为String重写了hashCode和equals方法map.put("张三", 12000.0);map.put("李四", 14000.0);//HashMap支持key和value为null值String name = null;Double salary = null;map.put(name, salary);Set<Map.Entry<String, Double>> entrySet = map.entrySet();for (Map.Entry<String, Double> entry : entrySet) {System.out.println(entry);}}
}

3、TreeMap

基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

代码示例：添加员工姓名为key，薪资为value

package com.atguigu.map;import java.util.Comparator;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;import org.junit.Test;public class TestTreeMap {@Testpublic void test1() {TreeMap<String,Integer> map = new TreeMap<>();map.put("Jack", 11000);map.put("Alice", 12000);map.put("zhangsan", 13000);map.put("baitao", 14000);map.put("Lucy", 15000);//String实现了Comparable接口，默认按照Unicode编码值排序Set<Entry<String, Integer>> entrySet = map.entrySet();for (Entry<String, Integer> entry : entrySet) {System.out.println(entry);}}@Testpublic void test2() {//指定定制比较器Comparator，按照Unicode编码值排序，但是忽略大小写TreeMap<String,Integer> map = new TreeMap<>(new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return o1.compareToIgnoreCase(o2);}});map.put("Jack", 11000);map.put("Alice", 12000);map.put("zhangsan", 13000);map.put("baitao", 14000);map.put("Lucy", 15000);Set<Entry<String, Integer>> entrySet = map.entrySet();for (Entry<String, Integer> entry : entrySet) {System.out.println(entry);}}
}

4、Properties

Properties 类是 Hashtable 的子类，Properties 可保存在流中或从流中加载。属性列表中每个键及其对应值都是一个字符串。

存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法。

代码示例：

package com.atguigu.map;import org.junit.Test;import java.util.Properties;public class TestProperties {@Testpublic void test01() {Properties properties = System.getProperties();String fileEncoding = properties.getProperty("file.encoding");//当前源文件字符编码System.out.println("fileEncoding = " + fileEncoding);}@Testpublic void test02() {Properties properties = new Properties();properties.setProperty("user","chai");properties.setProperty("password","123456");System.out.println(properties);}}

5.5 Set集合与Map集合的关系

Set的内部实现其实是一个Map。即HashSet的内部实现是一个HashMap，TreeSet的内部实现是一个TreeMap，LinkedHashSet的内部实现是一个LinkedHashMap。LinkedHashSet是HashSet的子类，它在HashSet的基础上，在结点中增加两个属性before和after维护了结点的前后添加顺序，这样就可以体现元素是添加顺序。

• HashSet：不可重复+元素无序（遍历顺序和添加顺序无关）
• TreeSet：不可重复+元素按照大小排序
• LinkedHashSet：不可重复+元素有序（遍历顺序和添加顺序一致）

部分源代码摘要：

HashSet源码：

    public HashSet() {map = new HashMap<>();}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);}//这个构造器是给子类LinkedHashSet调用的HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}

LinkedHashSet源码：

    public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);//调用HashSet的某个构造器}public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);//调用HashSet的某个构造器}public LinkedHashSet() {super(16, .75f, true);}public LinkedHashSet(Collection<? extends E> c) {super(Math.max(2*c.size(), 11), .75f, true);//调用HashSet的某个构造器addAll(c);}

TreeSet源码：

    public TreeSet() {this(new TreeMap<E,Object>());}public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));}public TreeSet(Collection<? extends E> c) {this();addAll(c);}public TreeSet(SortedSet<E> s) {this(s.comparator());addAll(s);}

但是，咱们存到Set中只有一个元素，又是怎么变成(key,value)的呢？

以HashSet中的源码为例：

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

原来是，把添加到Set中的元素作为内部实现map的key，然后用一个常量对象PRESENT对象，作为value。

这是因为Set的元素不可重复和Map的key不可重复有相同特点。Map有一个方法keySet()可以返回所有key。

6 集合框架

7 Collections工具类

参考操作数组的工具类：Arrays。

Collections 是一个操作 Set、List 和 Map 等集合的工具类。Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法：

• public static boolean addAll(Collection<? super T> c,T… elements)将所有指定元素添加到指定 collection 中。
• public static int binarySearch(List<? extends Comparable<? super T>> list,T key)在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且必须是可比较大小的，即支持自然排序的。而且集合也事先必须是有序的，否则结果不确定。
• public static int binarySearch(List<? extends T> list,T key,Comparator<? super T> c)在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且集合也事先必须是按照c比较器规则进行排序过的，否则结果不确定。
• public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)在coll集合中找出最大的元素，集合中的对象必须是T或T的子类对象，而且支持自然排序
• public static T max(Collection<? extends T> coll,Comparator<? super T> comp)在coll集合中找出最大的元素，集合中的对象必须是T或T的子类对象，按照比较器comp找出最大者
• public static void reverse(List<?> list)反转指定列表List中元素的顺序。
• public static void shuffle(List<?> list) List 集合元素进行随机排序，类似洗牌
• public static <T extends Comparable<? super T>> void sort(List list)根据元素的自然顺序对指定 List 集合元素按升序排序
• public static void sort(List list,Comparator<? super T> c)根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
• public static void swap(List<?> list,int i,int j)将指定 list 集合中的 i 处元素和 j 处元素进行交换
• public static int frequency(Collection<?> c,Object o)返回指定集合中指定元素的出现次数
• public static void copy(List<? super T> dest,List<? extends T> src)将src中的内容复制到dest中
• public static boolean replaceAll(List list，T oldVal，T newVal)：使用新值替换 List 对象的所有旧值
• Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题
• Collections类中提供了多个unmodifiableXxx()方法，该方法返回指定 Xxx的不可修改的视图。

package com.atguigu.collections;import org.junit.Test;import java.text.Collator;
import java.util.*;public class TestCollections {@Testpublic void test11(){/*public static <T> boolean replaceAll(List<T> list，T oldVal，T newVal)：使用新值替换 List 对象的所有旧值*/List<String> list = new ArrayList<>();Collections.addAll(list,"hello","java","world","hello","hello");Collections.replaceAll(list, "hello","chai");System.out.println(list);}@Testpublic void test10(){List<Integer> list = new ArrayList<>();for(int i=1; i<=5; i++){//1-5list.add(i);}List<Integer> list2 = new ArrayList<>();for(int i=11; i<=13; i++){//11-13list2.add(i);}list.addAll(list2);System.out.println(list);//[1, 2, 3, 4, 5, 11, 12, 13]}@Testpublic void test09(){/** public static <T> void copy(List<? super T> dest,List<? extends T> src)将src中的内容复制到dest中*/List<Integer> list = new ArrayList<>();for(int i=1; i<=5; i++){//1-5list.add(i);}List<Integer> list2 = new ArrayList<>();for(int i=11; i<=13; i++){//11-13list2.add(i);}Collections.copy(list, list2);System.out.println(list);List<Integer> list3 = new ArrayList<>();for(int i=11; i<=20; i++){//11-20list3.add(i);}Collections.copy(list, list3);//java.lang.IndexOutOfBoundsException: Source does not fit in destSystem.out.println(list);}@Testpublic void test08(){/*public static int frequency(Collection<?> c,Object o)返回指定集合中指定元素的出现次数*/List<String> list = new ArrayList<>();Collections.addAll(list,"hello","java","world","hello","hello");int count = Collections.frequency(list, "hello");System.out.println("count = " + count);}@Testpublic void test07(){/*public static void swap(List<?> list,int i,int j)将指定 list 集合中的 i 处元素和 j 处元素进行交换*/List<String> list = new ArrayList<>();Collections.addAll(list,"hello","java","world");Collections.swap(list,0,2);System.out.println(list);}@Testpublic void test06() {/** public static <T extends Comparable<? super T>> void sort(List<T> list)根据元素的自然顺序对指定 List 集合元素按升序排序* public static <T> void sort(List<T> list,Comparator<? super T> c)根据指定的 Comparator 产生的顺序对 List 集合元素进行排序*/List<Man> list = new ArrayList<>();list.add(new Man("张三",23));list.add(new Man("李四",24));list.add(new Man("王五",25));Collections.sort(list);System.out.println(list);Collections.sort(list, new Comparator<Man>() {@Overridepublic int compare(Man o1, Man o2) {return Collator.getInstance(Locale.CHINA).compare(o1.getName(),o2.getName());}});System.out.println(list);}@Testpublic void test05(){/*public static void shuffle(List<?> list) List 集合元素进行随机排序，类似洗牌，打乱顺序*/List<String> list = new ArrayList<>();Collections.addAll(list,"hello","java","world");Collections.shuffle(list);System.out.println(list);}@Testpublic void test04(){/*public static void reverse(List<?> list)反转指定列表List中元素的顺序。*/List<String> list = new ArrayList<>();Collections.addAll(list,"hello","java","world");System.out.println(list);Collections.reverse(list);System.out.println(list);}@Testpublic void test03(){/** public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)*      <T extends Object & Comparable<? super T>>：要求T必须继承Object，又实现Comparable接口，或者T的父类实现Comparable接口*      在coll集合中找出最大的元素，集合中的对象必须是T或T的子类对象，而且支持自然排序* public static <T> T max(Collection<? extends T> coll,Comparator<? super T> comp)*      在coll集合中找出最大的元素，集合中的对象必须是T或T的子类对象，按照比较器comp找出最大者**/List<Man> list = new ArrayList<>();list.add(new Man("张三",23));list.add(new Man("李四",24));list.add(new Man("王五",25));/*Man max = Collections.max(list);//要求Man实现Comparable接口，或者父类实现System.out.println(max);*/Man max = Collections.max(list, new Comparator<Man>() {@Overridepublic int compare(Man o1, Man o2) {return o2.getAge()-o2.getAge();}});System.out.println(max);}@Testpublic void test02(){/** public static <T> int binarySearch(List<? extends Comparable<? super T>> list,T key)*      要求List集合的元素类型 实现了 Comparable接口，这个实现可以是T类型本身也可以T的父类实现这个接口。*      说明List中的元素支持自然排序功能。*      在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且必须是可比较大小的，即支持自然排序的。而且集合也事先必须是有序的，否则结果不确定。* public static <T> int binarySearch(List<? extends T> list,T key,Comparator<? super T> c)*      说明List集合中元素的类型<=T，Comparator<? super T>说明要传入一个Comparator接口的实现类对象，实现类泛型的指定要求>=T*      例如：List中存储的是Man（男）对象，T可以是Person类型，实现Comparator的时候可以是 Comparator<Person>*      例如：List中存储的是Man（男）对象，T可以是Man类型，实现Comparator的时候可以是 Comparator<Person>*     在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且集合也事先必须是按照c比较器规则进行排序过的，否则结果不确定。** 二分查找要求数组或List必须是“有大小顺序”。* 二分查找的思路： 和[mid]元素比较，如果相同，就找到了，不相同要看大小关系，决定去左边还是右边继续查找。*/List<Man> list = new ArrayList<>();list.add(new Man("张三",23));list.add(new Man("李四",24));list.add(new Man("王五",25));//        int index = Collections.binarySearch(list, new Man("王五", 25));//要求实现Comparable接口
//        System.out.println(index);int index = Collections.binarySearch(list, new Man("王五", 25), new Comparator<Person>() {@Overridepublic int compare(Person o1, Person o2) {return o1.getAge() - o2.getAge();}});System.out.println(index);}@Testpublic void test01(){/*public static <T> boolean addAll(Collection<? super T> c,T... elements)将所有指定元素添加到指定 collection 中。Collection的集合的元素类型必须>=T类型*/Collection<Object> coll = new ArrayList<>();Collections.addAll(coll, "hello","java");Collections.addAll(coll, 1,2,3,4);Collection<String> coll2 = new ArrayList<>();Collections.addAll(coll2, "hello","java");
//        Collections.addAll(coll2, 1,2,3,4);//String和Integer之间没有父子类关系}
}

8 二叉树了解

二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

8.1 二叉树的遍历

• 前序遍历：中左右（根左右）
• 中序遍历：左中右（左根右）
• 后序遍历：左右中（左右根）

前序遍历：ABDHIECFG

中序遍历：HDIBEAFCG

后序遍历：HIDEBFGCA

8.2 经典二叉树

1、满二叉树： 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方，总的结点个数是2的n次方-1

2、完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。

3、平衡二叉树：平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树， 但不要求非叶节点都有两个子结点 。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。例如红黑树的要求：

• 节点是红色或者黑色

• 根节点是黑色

• 每个叶子的节点都是黑色的空节点（NULL）

• 每个红色节点的两个子节点都是黑色的。

• 从任意节点到其每个叶子的所有路径都包含相同的黑色节点数量。

当我们插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理：

1、recolor ：将某个节点变红或变黑

2、rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）

使得它继续满足以上的5个要求。

例如：插入了结点21之后，红黑树处理成：

8.3 二叉树及其结点的表示

普通二叉树：

public class BinaryTree<E>{private TreeNode root; //二叉树的根结点private int total;//结点总个数private class TreeNode{//至少有以下几个部分TreeNode parent;TreeNode left;E data;TreeNode right;public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {this.parent = parent;this.left = left;this.data = data;this.right = right;}}
}

TreeMap红黑树：

public class TreeMap<K,V> {private transient Entry<K,V> root;private transient int size = 0;static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK;/*** Make a new cell with given key, value, and parent, and with* {@code null} child links, and BLACK color.*/Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}}
}

9 哈希表

HashMap和Hashtable都是哈希表。

9.1 hashCode值

hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意大小的数据映射到一个固定大小的序列上，这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的，唯一性是指相同的“对象”产生的hash code永远是一样的。

9.2 哈希表的物理结构

HashMap和Hashtable是散列表，其中维护了一个长度为2的幂次方的Entry类型的数组table，数组的每一个元素被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到了某个table[index]桶中。使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]。

1、数组元素类型：Map.Entry

JDK1.7：

映射关系被封装为HashMap.Entry类型，而这个类型实现了Map.Entry接口。HashMap.Entry类型是个结点类型，即table[index]下的映射关系可能串起来一个链表。因此我们把table[index]称为“桶bucket"，表示table[index]下可能有多个元素。

public class HashMap<K,V>{transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;//...省略}//...
}

JDK1.8：

映射关系被封装为HashMap.Node类型或HashMap.TreeNode类型，它俩都直接或间接的实现了Map.Entry接口。储到table数组的可能是Node结点对象，也可能是TreeNode结点对象，它们也是Map.Entry接口的实现类。即table[index]下的映射关系可能串起来一个链表或一棵红黑树。

public class HashMap<K,V>{transient Node<K,V>[] table;static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;//...省略}static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;boolean red;//是红结点还是黑结点//...省略}//....
}

public class LinkedHashMap<K,V>{static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}//...
}

2、数组的长度始终是2的n次幂

table数组的默认初始化长度：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

如果你手动指定的table长度不是2的n次幂，会通过如下方法给你纠正为2的n次幂。

JDK1.7：

HashMap处理容量方法：

    private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}

Integer包装类：

    public static int highestOneBit(int i) {// HD, Figure 3-1i |= (i >>  1);i |= (i >>  2);i |= (i >>  4);i |= (i >>  8);i |= (i >> 16);return i - (i >>> 1);}

JDK1.8：

    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;}

如果数组不够了，扩容了怎么办？扩容了还是2的n次幂，因为每次数组扩容为原来的2倍

JDK1.7：

    void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);//扩容为原来的2倍hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}

JDK1.8：

    final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap原来的容量int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//newCap = oldCap << 1  新容量=旧容量扩容为原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//......此处省略其他代码}

3、那么HashMap是如何决定某个映射关系存在哪个桶的呢？

因为hash值是一个整数，而数组的长度也是一个整数，有两种思路：

①hash 值 % table.length会得到一个[0,table.length-1]范围的值，正好是下标范围，但是用%运算效率没有位运算符&高。

②hash 值 & (table.length-1)，任何数 & (table.length-1)的结果也一定在[0, table.length-1]范围。

hashCode值是   ？
table.length是10
table.length-1是9？   ????????
9	 00001001
&_____________00000000	[0]00000001	[1]00001000	[8]00001001	[9]一定[0]~[9]

hashCode值是   ？
table.length是16
table.length-1是15？   ????????
15	 00001111
&_____________00000000	[0]00000001	[1]00000010	[2]00000011	[3]...00001111    [15]范围是[0,15]，一定在[0,table.length-1]范围内

JDK1.7：

    static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1); //此处h就是hash}

JDK1.8：

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)  // i = (n - 1) & hashtab[i] = newNode(hash, key, value, null);//....省略大量代码
}

那么为什么要保持table数组一直是2的n次幂呢？

因为如果数组的长度为2的n次幂，那么table.length-1的二进制就是一个高位全是0，低位全是1的数字，这样才能保证每一个下标位置都有机会被用到。

4、hash是hashCode的再运算

不管是JDK1.7还是JDK1.8中，都不是直接用key的hashCode值直接与table.length-1计算求下标的，而是先对key的hashCode值进行了一个运算，JDK1.7和JDK1.8关于hash()的实现代码不一样，但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果，尽量的均匀分布。

JDK1.7：

    final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

JDK1.8：

	static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

虽然算法不同，但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或，然高位二进制参与到index的计算中。

为什么要hashCode值的二进制的高位参与到index计算呢？

因为一个HashMap的table数组一般不会特别大，至少在不断扩容之前，那么table.length-1的大部分高位都是0，直接用hashCode和table.length-1进行&运算的话，就会导致总是只有最低的几位是有效的，那么就算你的hashCode()实现的再好也难以避免发生碰撞，这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。

5、解决[index]冲突问题

虽然从设计hashCode()到上面HashMap的hash()函数，都尽量减少冲突，但是仍然存在两个不同的对象返回的hashCode值相同，或者hashCode值就算不同，通过hash()函数计算后，得到的index也会存在大量的相同，因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办？

JDK1.8之间使用：数组+链表的结构。

JDK1.8之后使用：数组+链表/红黑树的结构。

即hash相同或hash&(table.lengt-1)的值相同，那么就存入同一个“桶”table[index]中，使用链表或红黑树连接起来。

6、为什么JDK1.8会出现红黑树和链表共存呢？

因为当冲突比较严重时，table[index]下面的链表就会很长，那么会导致查找效率大大降低，而如果此时选用二叉树可以大大提高查询效率。

但是二叉树的结构又过于复杂，如果结点个数比较少的时候，那么选择链表反而更简单。

所以会出现红黑树和链表共存。

7、什么时候树化？什么时候反树化？

static final int TREEIFY_THRESHOLD = 8;//树化阈值
static final int UNTREEIFY_THRESHOLD = 6;//反树化阈值
static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量

• 树化

  • 当某table[index]下的链表的结点个数达到8，并且table.length>=64，那么如果新Entry对象还添加到该table[index]中，那么就会将table[index]的链表进行树化。

• 反树化

  • 当删除table[index]下的树结点时，满足根结点的左右结点有null，或根结点的左结点的左结点为null，会反树化
  • 当table[index]下的树结点个数少于等于6个后，又重新添加新的映射关系到map中，导致了map重新扩容了，这个时候如果table[index]下面还是小于等于6的个数，那么会反树化

package com.atguigu.hashtable;public class MyKey {int num;public MyKey(int num) {super();this.num = num;}@Overridepublic int hashCode() {if(num<=20){return 1;}else{final int prime = 31;int result = 1;result = prime * result + num;return result;}}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;MyKey other = (MyKey) obj;if (num != other.num)return false;return true;}
}

package com.atguigu.hashtable;import org.junit.Test;import java.util.HashMap;public class TestHashMap {@Testpublic void test1(){//这里为了演示的效果，我们造一个特殊的类，这个类的hashCode（）方法返回固定值1//因为这样就可以造成冲突问题，使得它们都存到table[1]中HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);//树化演示}}@Testpublic void test2(){HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);}for (int i = 1; i <=11; i++) {map.remove(new MyKey(i));}//树结点个数还有5个时，继续删除下一个结点的过程中满足判断根结点的左左结点为null，反树化}@Testpublic void test3(){//演示反树化的过程HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);}for (int i = 11; i >=7; i--) {map.remove(new MyKey(i));}//table[1]下剩余6个结点for (int i = 21; i <= 100; i++) {map.put(new MyKey(i), "value"+i);//添加到扩容时，反树化}}@Testpublic void test4(){//演示扩容不反树化的过程HashMap<MyKey, String> map = new HashMap<>();for (int i = 1; i <= 11; i++) {map.put(new MyKey(i), "value"+i);}//table[1]下超过6个结点for (int i = 21; i <= 100; i++) {map.put(new MyKey(i), "value"+i);//添加到扩容时， 不 反树化}}
}

8、数组扩容相关问题

（1）数组什么时候扩容

JDK1.7版：当要添加新Entry对象时发现（1）size达到threshold（2）table[index]!=null时，两个条件同时满足会扩容

JDK1.8版：当要添加新Entry对象时发现（1）size达到threshold（2）当table[index]下的结点个数达到8个需要树化（链表转红黑树）但是table.length又没有达到64。

几个常量和变量：
（1）DEFAULT_LOAD_FACTOR：默认加载因子 0.75
（2）size：记录有效映射关系的对数，也是Entry对象的个数
（3）int threshold：阈值，当size达到阈值时，考虑扩容
（4）double loadFactor：加载因子，影响扩容的频率threshold = loadFactor * table.lengthsize >= threshold就会扩容，再添加就会扩容

package com.atguigu.hashtable;import org.junit.Test;import java.util.HashMap;public class TestTableGrow {@Testpublic void test1(){HashMap<Integer,Integer> map = new HashMap<>();for(int i=0; i<=20; i++){map.put(i,i);}/*JDK8：当size达到12，继续添加就会扩容JDK7：当size达到16，继续添加才会扩容*/}
}

（2）负载因子的值大小有什么关系？

• 如果太大，threshold就会很大，那么如果冲突比较严重的话，就会导致table[index]下面的结点个数很多，影响效率。

• 如果太小，threshold就会很小，那么数组扩容的频率就会提高，数组的使用率也会降低，那么会造成空间的浪费。

（3）数组扩容后，(key,value)的位置会变化吗

注意：不管哪个版本，数组一旦扩容都会导致所有映射关系重新调整存储位置，但是位置不会乱调，要么保存不动，要么从n的位置调整到(n+扩容前table.length)的位置。

hashCode值是   ？
table.length是16
table.length-1是15？   ????????
15	 00001111
&_____________0000xxxxtable.length是32
table.length-1是31   ？   ????????
15	 00011111
&_____________0000xxxx  位置不变0001xxxx  16 + xxxx

9.3 JDK1.7的put方法源码分析

1、构造器

    public HashMap() {//DEFAULT_INITIAL_CAPACITY：默认初始容量16//DEFAULT_LOAD_FACTOR：默认加载因子0.75this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}public HashMap(int initialCapacity, float loadFactor) {//校验initialCapacity合法性if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +//校验initialCapacity合法性                                       initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//校验loadFactor合法性if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);//加载因子，初始化为0.75this.loadFactor = loadFactor;// threshold 初始为初始容量                                  threshold = initialCapacity;init();}

2、put方法

public V put(K key, V value) {//如果table数组是空的，那么先创建数组if (table == EMPTY_TABLE) {//threshold一开始是初始容量的值inflateTable(threshold);}//如果key是null，单独处理，存储到table[0]中，如果有另一个key为null，value覆盖if (key == null)return putForNullKey(value);//对key的hashCode进行干扰，算出一个hash值/*hashCode值      xxxxxxxxxxtable.length-1   000001111hashCode值 xxxxxxxxxx  无符号右移几位和原来的hashCode值做^运算，使得hashCode高位二进制值参与计算，也发挥作用，降低index冲突的概率。*/int hash = hash(key);//计算新的映射关系应该存到table[i]位置，//i = hash & table.length-1，可以保证i在[0,table.length-1]范围内int i = indexFor(hash, table.length);//检查table[i]下面有没有key与我新的映射关系的key重复，如果重复替换valuefor (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//添加新的映射关系addEntry(hash, key, value, i);return null;}private void inflateTable(int toSize) {// Find a power of 2 >= toSizeint capacity = roundUpToPowerOf2(toSize);//容量是等于toSize值的最接近的2的n次方//计算阈值 = 容量 * 加载因子threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//创建Entry[]数组，长度为capacitytable = new Entry[capacity];initHashSeedAsNeeded(capacity);}//如果key是null，直接存入[0]的位置private V putForNullKey(V value) {//判断是否有重复的key，如果有重复的，就替换valuefor (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;//把新的映射关系存入[0]的位置，而且key的hash值用0表示addEntry(0, null, value, 0);return null;}void addEntry(int hash, K key, V value, int bucketIndex) {//判断是否需要库容//扩容：（1）size达到阈值（2）table[i]正好非空if ((size >= threshold) && (null != table[bucketIndex])) {//table扩容为原来的2倍，并且扩容后，会重新调整所有映射关系的存储位置resize(2 * table.length);//新的映射关系的hash和index也会重新计算hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}//存入table中createEntry(hash, key, value, bucketIndex);}void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];//原来table[i]下面的映射关系作为新的映射关系nexttable[bucketIndex] = new Entry<>(hash, key, value, e);size++;//个数增加}

1、put(key,value)

（1）当第一次添加映射关系时，数组初始化为一个长度为16的**HashMap$Entry\ast \ast 的数组，这个HashMap$Entry类型是实现了java.util.Map.Entry接口

（2）特殊考虑：如果key为null，index直接是[0],hash也是0

（3）如果key不为null，在计算index之前，会对key的hashCode()值，做一个hash(key)再次哈希的运算，这样可以使得Entry对象更加散列的存储到table中

（4）计算index = table.length-1 & hash;

（5）如果table[index]下面，已经有映射关系的key与我要添加的新的映射关系的key相同了，会用新的value替换旧的value。

（6）如果没有相同的，会把新的映射关系添加到链表的头，原来table[index]下面的Entry对象连接到新的映射关系的next中。

（7）添加之前先判断if(size >= threshold && table[index]!=null)如果该条件为true，会扩容

if(size >= threshold  &&  table[index]!=null){①会扩容②会重新计算key的hash③会重新计算index}

（8）size++

9.4 JDK1.8的put方法源码分析

1、几个常量和变量

几个常量和变量：
（1）DEFAULT_INITIAL_CAPACITY：默认的初始容量 16
（2）MAXIMUM_CAPACITY：最大容量  1 << 30
（3）DEFAULT_LOAD_FACTOR：默认加载因子 0.75
（4）TREEIFY_THRESHOLD：默认树化阈值8，当链表的长度达到这个值后，要考虑树化
（5）UNTREEIFY_THRESHOLD：默认反树化阈值6，当树中的结点的个数达到这个阈值后，要考虑变为链表
（6）MIN_TREEIFY_CAPACITY：最小树化容量64当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容
（7）Node<K,V>[] table：数组
（8）size：记录有效映射关系的对数，也是Entry对象的个数
（9）int threshold：阈值，当size达到阈值时，考虑扩容
（10）double loadFactor：加载因子，影响扩容的频率

2、构造器

    public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted，其他字段都是默认值}

3、put方法

    public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//目的：干扰hashCode值static final int hash(Object key) {int h;//如果key是null，hash是0//如果key非null，用key的hashCode值 与 key的hashCode值高16进行异或//		即就是用key的hashCode值高16位与低16位进行了异或的干扰运算/*index = hash & table.length-1如果用key的原始的hashCode值  与 table.length-1 进行按位与，那么基本上高16没机会用上。这样就会增加冲突的概率，为了降低冲突的概率，把高16位加入到hash信息中。*/return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; //数组Node<K,V> p; //一个结点int n, i;//n是数组的长度   i是下标//tab和table等价//如果table是空的if ((tab = table) == null || (n = tab.length) == 0){n = (tab = resize()).length;/*tab = resize();n = tab.length;*//*如果table是空的，resize()完成了①创建了一个长度为16的数组②threshold = 12n = 16*/}//i = (n - 1) & hash ，下标 = 数组长度-1 & hash//p = tab[i] 第1个结点//if(p==null) 条件满足的话说明 table[i]还没有元素if ((p = tab[i = (n - 1) & hash]) == null){//把新的映射关系直接放入table[i]tab[i] = newNode(hash, key, value, null);//newNode（）方法就创建了一个Node类型的新结点，新结点的next是null}else {Node<K,V> e; K k;//p是table[i]中第一个结点//if(table[i]的第一个结点与新的映射关系的key重复)if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))){e = p;//用e记录这个table[i]的第一个结点}else if (p instanceof TreeNode){//如果table[i]第一个结点是一个树结点//单独处理树结点//如果树结点中，有key重复的，就返回那个重复的结点用e接收，即e!=null//如果树结点中，没有key重复的，就把新结点放到树中，并且返回null，即e=nulle = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);}else {//table[i]的第一个结点不是树结点，也与新的映射关系的key不重复//binCount记录了table[i]下面的结点的个数for (int binCount = 0; ; ++binCount) {//如果p的下一个结点是空的，说明当前的p是最后一个结点if ((e = p.next) == null) {//把新的结点连接到table[i]的最后p.next = newNode(hash, key, value, null);//如果binCount>=8-1，达到7个时if (binCount >= TREEIFY_THRESHOLD - 1){ // -1 for 1st//要么扩容，要么树化treeifyBin(tab, hash);}break;}//如果key重复了，就跳出for循环，此时e结点记录的就是那个key重复的结点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))){break;}p = e;//下一次循环，e=p.next，就类似于e=e.next，往链表下移动}}//如果这个e不是null，说明有key重复，就考虑替换原来的valueif (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null){e.value = value;}afterNodeAccess(e);//什么也没干return oldValue;}}++modCount;//元素个数增加//size达到阈值if (++size > threshold){resize();//一旦扩容，重新调整所有映射关系的位置}afterNodeInsertion(evict);//什么也没干return null;}	final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//oldTab原来的table//oldCap：原来数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldThr：原来的阈值int oldThr = threshold;//最开始threshold是0//newCap，新容量//newThr：新阈值int newCap, newThr = 0;if (oldCap > 0) {//说明原来不是空数组if (oldCap >= MAXIMUM_CAPACITY) {//是否达到数组最大限制threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY){//newCap = 旧的容量*2 ，新容量<最大数组容量限制//新容量：32,64，...//oldCap >= 初始容量16//新阈值重新算 = 24，48 ....newThr = oldThr << 1; // double threshold}}else if (oldThr > 0){ // initial capacity was placed in thresholdnewCap = oldThr;}else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;//新容量是默认初始化容量16//新阈值= 默认的加载因子 * 默认的初始化容量 = 0.75*16 = 12newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;//阈值赋值为新阈值12，24.。。。//创建了一个新数组，长度为newCap，16，32,64.。。@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {//原来不是空数组//把原来的table中映射关系，倒腾到新的table中for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {//e是table下面的结点oldTab[j] = null;//把旧的table[j]位置清空if (e.next == null)//如果是最后一个结点newTab[e.hash & (newCap - 1)] = e;//重新计算e的在新table中的存储位置，然后放入else if (e instanceof TreeNode)//如果e是树结点//把原来的树拆解，放到新的table((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;/*把原来table[i]下面的整个链表，重新挪到了新的table中*/do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}	Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {//创建一个新结点return new Node<>(hash, key, value, next);}final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;//MIN_TREEIFY_CAPACITY：最小树化容量64//如果table是空的，或者  table的长度没有达到64if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();//先扩容else if ((e = tab[index = (n - 1) & hash]) != null) {//用e记录table[index]的结点的地址TreeNode<K,V> hd = null, tl = null;/*do...while，把table[index]链表的Node结点变为TreeNode类型的结点*/do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;//hd记录根结点else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);//如果table[index]下面不是空if ((tab[index] = hd) != null)hd.treeify(tab);//将table[index]下面的链表进行树化}}	

1、添加过程

A. 先计算key的hash值，如果key是null，hash值就是0，如果为null，使用(h = key.hashCode()) ^ (h >>> 16)得到hash值；

B. 如果table是空的，先初始化table数组；

C. 通过hash值计算存储的索引位置index = hash & (table.length-1)

D. 如果table[index]==null，那么直接创建一个Node结点存储到table[index]中即可

E. 如果table[index]!=null

​ a) 判断table[index]的根结点的key是否与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），如果是那么用e记录这个根结点

​ b) 如果table[index]的根结点的key与新的key“不相同”，而且table[index]是一个TreeNode结点，说明table[index]下是一棵红黑树，如果该树的某个结点的key与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），那么用e记录这个相同的结点，否则将(key,value)封装为一个TreeNode结点，连接到红黑树中

​ c) 如果table[index]的根结点的key与新的key“不相同”，并且table[index]不是一个TreeNode结点，说明table[index]下是一个链表，如果该链表中的某个结点的key与新的key“相同”，那么用e记录这个相同的结点，否则将新的映射关系封装为一个Node结点直接链接到链表尾部，并且判断table[index]下结点个数达到TREEIFY_THRESHOLD(8)个，如果table[index]下结点个数已经达到，那么再判断table.length是否达到MIN_TREEIFY_CAPACITY(64)，如果没达到，那么先扩容，扩容会导致所有元素重新计算index，并调整位置，如果table[index]下结点个数已经达到TREEIFY_THRESHOLD(8)个并table.length也已经达到MIN_TREEIFY_CAPACITY(64)，那么会将该链表转成一棵自平衡的红黑树。

F. 如果在table[index]下找到了新的key“相同”的结点，即e不为空，那么用新的value替换原来的value，并返回旧的value，结束put方法

G. 如果新增结点而不是替换，那么size++，并且还要重新判断size是否达到threshold阈值，如果达到，还要扩容。

if(size > threshold ){①会扩容②会重新计算key的hash③会重新计算index}

2、remove(key)

（1）计算key的hash值，用这个方法hash(key)

（2）找index = table.length-1 & hash;

（3）如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就删除它，把它前面的Entry的next的值修改为被删除Entry的next

（4）如果table[index]下面原来是红黑树，如果当删除table[index]下的树结点时，最后这个根结点的左右结点有null，或根结点的左结点的左结点为null，会反树化

9.5 关于映射关系的key是否可以修改？

映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。所以实际开发中，经常选用String，Integer等作为key，因为它们都是不可变对象。

这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。

JDK1.7：

public class HashMap<K,V>{transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash; //记录Entry映射关系的key的hash(key.hashCode())值//...省略}//...
}

JDK1.8：

public class HashMap<K,V>{transient Node<K,V>[] table;static class Node<K,V> implements Map.Entry<K,V> {final int hash;//记录Node映射关系的key的hash(key.hashCode())值final K key;V value;Node<K,V> next;//...省略}//....
}

示例代码：

package com.atguigu.map;public class ID{private int id;public ID(int id) {super();this.id = id;}@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + id;return result;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;ID other = (ID) obj;if (id != other.id)return false;return true;}public int getId() {return id;}public void setId(int id) {this.id = id;}}

测试类

package com.atguigu.map;import java.util.HashMap;public class TestHashMapID{public static void main(String[] args) {HashMap<ID,String> map = new HashMap<>();ID i1 = new ID(1);ID i2 = new ID(2);ID i3 = new ID(3);map.put(i1, "haha");map.put(i2, "hehe");map.put(i3, "xixi");System.out.println(map.get(i1));//hahai1.setId(10);System.out.println(map.get(i1));//null}
}