学习目的

1. 了解集合的概念
2. 掌握java集合的分类以及作用
3. 掌握java集合的对象创建，以及常用方法的使用
4. 熟悉java每一种集合的使用场景
5. 掌握常见的集合ArrayList、LinkedList、HashSet 、TreeSet、HashMap、Properties、TreeMap
6. 学会查看集合的底层源代码
7. 掌握从集合底层的数据结构与实现来洞悉equals()方法与hashCode()方法的重写

一.集合

1. Java 集合的继承结构体系
   主要分为两大类：Collection 和 Map。

   
   
   集合总结构图.png

2. 集合的主要常用类型

• List：有序集合（存入顺序和取出顺序相同），可以存放重复的数据；
• Set：无序集合（存入顺序和取出顺序不同），不允许存放重复的数据；
• Map：无序集合，以键-值对形式存放数据。集合中包含一个键对象，一个值对象，键对象不允许重复，值对象可以重复。

3. 集合与数据结构
   每一种集合在底层都对应着不同的数据结构，即每一种集合对数据的存储方式都不一样，因此效率和性能也不一样。不同的数据结构，数据存储方式不同。

• 数组：ArrayList，Vector；有序，可重复，查询快；
• 二叉树：TreeSet，TreeMap；无序，可排序；
• 链表：LinkedList；无序，不可重复，增删快；
• 哈希表：HashSet，HashMap，Hashtable；无序，不可重复，增删查询综合较快；
• 图：Map；无序；
• 数组+链表/树：HashSet，HashMap，综合数组、链表、树的特点；
• 栈：Stack；已失效。

4. 集合在程序中的应用

   
   
   集合与数据库数据的底层实现.png
5. 集合的选择

• 以单个方式存储元素：Collection及其子类；
• 以键值对方式存储元素：Map及其子类；
• 线程安全：Hashtable、Properties；
• 非线程安全：ArrayList、HashSet、HashMap。

6. 集合之间的转换

• 查看每个集合底层的源码，查看构造方法，keySet()、entrySet()方法等。

1.1 Collection

1. 概念
   Collection是集合层次结构中的根接口，是 List 和 Set 的父接口，LIst 和 Set都继承了Collection接口的属性和方法。而Collection同时也继承于Iterable接口，并且实现其Iterator()方法，该方法返回得到一个迭代器对象。通过迭代器对象，可以遍历所有的Collection集合中的元素。

2. Collection体系继承结构

   
   
   Collection 集合继承结构图.png
3. 性质特点

• 单个元素存储：在Collection集合中，所有子类集合都是采用 **单个元素方式存储数据；
• 存储地址：所有的Collection子集合存储的元素都是"内存地址"，而不是元素本身，不管该元素是基本类型还是引用类型**。

4. Collection 接口常用方法

• Collection c = new LinkedList()：面向接口编程，创建Collection对象；
• int size() ：返回集合中元素的总个数；
• boolean isEmpty()：判断集合是否为空，底层使用size属性==0判断；
• boolean add(Object o)：往集合中添加单个元素；
• boolean remove(Object o)：从集合中移除单个指定元素；
• void clear()：移除集合对象中的所有元素；
• Object[] toArray() ：将集合对象中所有元素返回为一个数组中；
• boolean contains(Object o)：判断集合中是否包含指定元素；
• boolean equals(Object o)：比较集合对象与指定对象o是否相等。

        //创建一个数组集合对象
        Collection c1 = new ArrayList();
        String s1 = new String("abc");
        String s2 = new String("efg");
        c1.add(s1);
        c1.add(s2);
        System.out.println(c1.size());//输出2
        String x = new String("abc");
        /*c1.add(x);//往集合c中添加重复元素 abc
        System.out.println(c1.size());//输出2
        System.out.println(c1.contains(x));//c集合中是否包含x：true
        /*
        ArrayList底层的contains(Object o)方法中又使用equals()方法
        o.equals(elementData[i]);//判断ArrayList是否已存在元素o
         */

contains方法内存解析.png

• Iterator it = collection.iterator()：最重要的方法，返回一个当前集合的迭代器，遍历当前集合；

//指定元素类型E的迭代器接口
Iterator<E> iterator() ;
//面向接口编程，创建Collection对象
Collection c = new ArrayList();
//创建一个可以在c对象上操作的迭代器对象
Iterator iter = c.iterator();

//迭代器遍历集合，若该集合有元素则输出
while (iter.hasNext()) {
          Integer v = (Integer)iter.next();//对集合c进行迭代遍历得到的元素类型 转型成 Integer类型
          System.out.println(v);
}
//for循环迭代器遍历集合，若该集合有元素则输出
for (Iterator iter1 = c.iterator() ; iter1.hasNext() ; ) {
          Integer v = (Integer)iter1.next();
          System.out.println(v);
}

1.1.1 List<列表>

1. 概念
   List是一个有序接口，意为列表或序列。List底层是数组存储元素，因此可以根据数组下标，对List中的每个元素进行位置插入、访问、搜索等。List是一个存入和输出顺序相同、可以存放重复数据的Collection集合。
2. 分类

• ArrayList：数组列表，有序可重复，查询快；
• LinkedList：链表，有序可重复，增删快；
• Vector：向量，线程安全的ArrayList，但已被ArrayList淘汰；
• Stack：栈，已被LinkedList淘汰。

3. 特点

• 可提供带下标索引的方法（底层是数组）；
• 有序：元素存入和取出是相同的顺序；
• 可重复：可以加入重复的元素；
• 默认在集合的末尾添加元素。

        List list = new ArrayList();
        list.add(123);//在集合中添加元素，默认在集合末尾添加
        list.add(666);
        list.add("abc");
        list.add(123);
        list.add(88.88);
        //在集合指定下标处 添加指定元素
        list.add(4,999);
        //创建在c集合上的迭代器对象，并迭代遍历c的所有元素         
        for ( Iterator it  = list.iterator();it.hasNext();){
            Object o =  it.next();
            System.out.print(o + " ");//加入与输出的顺序：123 666 abc 123 999 88.88 
        }
        for (int i =0;i<list.size();i++){
            //根据下标对list集合进行遍历
            System.out.println(list.get(i));
        }

3.1.1.1 ArrayList

1. 概念
   ArrayList是底层采用数组形式 的数据结构进行存储元素的集合，是一个可增长的数组，可以提供快速迭代和随机访问的能力。
2. 特点

• 末尾添加元素：ArrayList底层的源码方法规定，在数组列表的末尾添加元素；
• 检索效率高：每个元素占用空间大小相同，内存地址连续的，知道首元素内存地址和下标，通过数学表达式计算出 元素的内存地址，因此检索效率最高；
• 非线程安全：ArrayList底层的方法都是无synchronized修饰的；
• 自动扩容：当ArrayList增加的元素过多，超出初始化的容量10时，会自动扩容，且每一次扩容是原来的1.5倍。

3. 字段

• int DEFAULT_CAPACITY = 10：创建一个初始默认容量为10的ArrayList对象；
• Object[] EMPTY_ELEMENTDATA = {}：存储元素数据，初始为空元素数据容量的数组；
• Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}：默认空元素数据容量-添加元素后，默认容量=10；
• Object[] elementData：ArrarList底层实际用于存储元素的数组；

4. 常用方法
   对于ArrayList常用的方法，可以到源码的java.util.ArrayList类中查看具体的实现，学会查看源码，理解源码。（其他类的常用方法亦如此）

//带参构造，创建并初始化指定容量大小的ArrayList对象
public ArrayList(int initialCapacity) {  
}
//无参构造，创建默认空元素数据容量的ArrayList对象，添加元素后，默认容量也=10
public ArrayList() {   
}
//返回数组长度-数组中元素的个数
public int size() {   
    return size;   
}
//判断数组是否为空
public boolean isEmpty() {   
    return size == 0;  
}
//判断数组是否包含指定元素--调用同类中的indexOf()方法
public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
//返回指定元素在数组中-第一次出现的下标
public int indexOf(Object o) {
    }
//返回指定元素在数组中-最后一次出现的下标
 public int lastIndexOf(Object o) {
}
//复制一份该数组-浅克隆
public Object clone() {
}
//按顺序+指定长度，将ArrayList中所有的元素-使用数组返回
public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
//返回指定下标的元素
public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
//用指定的元素 替代 指定下标位置的元素
public E set(int index, E element) {
    }
//将指定的元素添加到尾部，此方法限定ArrayList的添加元素特点
public boolean add(E e) {
    }
//在ArrayList中指定位置添加元素
public void add(int index, E element) {
    }
//移除、删除指定下标位置的元素，返回该元素
public E remove(int index) {
    }
//删除指定下标位置的元素
public boolean remove(Object o) {
    }
//清楚列表中的所有元素，清空列表
public void clear() {
    }
//删除列表中指定 [ 范围）内的元素
protected void removeRange(int fromIndex, int toIndex) {
    }

3.1.1.2 LinkedList

1. 概念
   LinkedList是底层采用 双向链表形式的数据结构存储元素，可以提供快速插入删除的能力。
2. 特点

• 增删容易：地址不连续，使用节点保存数据和下一个节点的地址，删除时不需要移动每一个节点元素；
• 非线程安全：
• 由节点组成，节点保存数据和内存地址

3. 链表图解

• 单链表

  
  
  单向链表.png

• 双链表：LinkedList底层的实现原理就是双向链表，采用内部类-节点的形式

  
  
  双向链表.png

4. 字段

• int size = 0：初始化链表长度为0；
• Node<E> first：前一个节点内存地址；
• Node<E> last：后一个节点内存地址；
• class Node<E>：静态内部类，静态内部节点。

5. 常用方法
   LinkedList常用方法与ArrayList常用方法差不多，基本都是创建对象的构造器，往集合中加元素、删元素、和查元素等，可查看底层源码了解方法的具体实现。

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //静态内部类-节点    
    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;
        }
    }
    //无参构造
    public LinkedList() {
    }
    //带参构造
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    //LinkedList底层采用 双向链表 的实现原理    
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
}

3.1.1.3 Vector（非重要）

1. 概念
   Vector**底层采用数组形式 **的数据结构存储元素，意为向量，目前已极少使用。
2. 特点

• 效率慢<性能低>：使用synchronized关键字修饰，需要额外处理安全问题导致直接操作数据的效率低下；
• 线程同步：Vector 中的方法都是使用synchronized关键字修饰的，是线程安全版本的ArrayList；
• 自动扩容：当Vector增加的元素过多，超出初始化的10时，会自动扩容，且每一次扩容是原来的两倍。

3. 字段

• Object[] elementData：底层采用数组形式存储数据 ；
• int elementCount：该集合的总元素个数；
• int capacityIncrement：指定每次自动扩容的容量。

4. 常用方法

public class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    //构造器，可以创建不同形式、不同容量的Vector对象    
    public Vector(int initialCapacity, int capacityIncrement) {  //指定初始化容量，且设定每次自动扩容的大小  
    }
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    public Vector() {
        this(10);
    }
    public Vector(Collection<? extends E> c) {
    }

    //自动扩容实现原理
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

3.1.1.4 Stack（非重要）

1. 概念
   继承 Vector接口 实现的一个栈，结构是后进先出，目前已经被 LinkedList 取代。

3.1.2 Set

1. 概念
   Set的底层采用HashMap形式的数据结构存储元素的一个接口。是一个无序，不允许存放重复数据的集合。也是HashSet和TreeSet的父类接口。
2. 特点

• 无序：无序指的是元素存入和取出的顺序不同。HashMap底层采用的是哈希算法对元素进行存储，哈希算法本身就具有无序的特点（散列性）；
• 不允许重复：底层HashMap存储数据的形式是键值对，键key是无序且不允许重复的。而Set集合中存入元素 == HashMap中存key，因此Set集合与HashMap存储数据的特点是一样的。

3. 常用方法

• int size()：获取set集合中元素的个数；
• boolean isEmpty()：判断集合是否为空，底层使用siz() == 0判断；
• boolean contains(Object o)：判断集合中是否包含指定元素o；
• Iterator<E> iterator()：产生一个在该set集合上的迭代器对象；
• Object[] toArray()：将set集合中所有的算数转换成数组输出；
• boolean add(E e)：往set集合中添加指定元素；
• boolean remove(Object o)：从set集合中移除指定元素；
• void clear()：清楚set集合中所有的元素；
• boolean equals(Object o)：判断指定对象是否与该set集合对象相等。

public interface Set<E> extends Collection<E> {
    // Query Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);

    // Modification Operations
    boolean add(E e);
    boolean remove(Object o);

    // Bulk Operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();

    // Comparison and hashing
    boolean equals(Object o);
    int hashCode();
}

3.1.2.2 HashSet

1. 概念
   HashSet即Hash + Set，使用哈希算法存储数据的Set集合。HashSet 底层使用的是HashMap[]存储数据。HashSet 中的数据是无序的，不可存放重复的数据，原因同Set。
2. 特点

• 无序：数据存入顺序和读出顺序不相同，HashSet按照哈希算法存取数据，综合了数组和链表的特点，具有非常好的性能；
• 不可重复数据：底层采用HashMap存储元素，存入的元素 == HashMap中的key，key不能重复。

3. 工作原理
   当向 HashSet 中插入数据时，先调用对象的 hashCode() 方法得到该对象的哈希码，然后根据 哈希码 计算出该对象插入到集合中的位置。
4. 代码解释

         //面向接口编程，创建一个HashSet对象          
         Collection c = new HashSet();
        //创建在c集合上的迭代器对象
        Iterator it ;
        c.add(123);//同理依次往Collection集合c中add()：666 abc 456 new Object() 123 efg 456 88.88 efg
        c.add(666);
        //测试HashSet的无序（元素存入和取出是不同的顺序），以及不可重复（元素不能重复）
        for (it = c.iterator();it.hasNext();){
            Object o =  it.next();//迭代遍历c集合上的所有元素
            System.out.print(o + " ");
            //存入和输出顺序：abc efg 456 java.lang.Object@4554617c 666 88.88 123 
        }

3.1.2.3 SortedSet

1. 概念
   SortedSet是一个继承于Set的接口，继承了Set接口的特性-无序，不可重复。但是存放到SortedSet集合中的元素<key部分>可以按照大到小的顺序自动排序，排序的元素需实现Comparable接口（重写compareTo()方法）或实现Comparator接口（重写compare()方法）。

3.1.2.4 TreeSet

1. 概念
   TreeSet底层采用 TreeMap[ ]形式 的数据结构存储数据的集合，TreeMap底层又是二叉树（红黑二叉树）。TreeSet 是可以对 Set 集合<key部分> 进行自动排序的一种集合，默认自动升序<从小到大升序>，但不可存放重复的数据。
2. 特点

• 不可重复：因为TreeSet存入元素 = TreeMap的key，key不可重复；
• 对排序的 Set集合的元素类型只能是一种类型排序。如：Set集合中元素是 int 类型时，不能加入 String字符串类型，否则将无法排序；
• 无序，但可排序：无序指的是存入元素的顺序和取出来的顺序不一样，但是存入的元素会按照从小到大排序，也就是说排序后的顺序可能还是和存入的顺序不一样。

3. 代码示例

public static void main(String[] args) {
        Set set = new TreeSet();
        set.add("a");//同理往set集合中add()：aa d f bb c aa f
        //foreach增强循环遍历set集合
        for (Object s:set) {
            System.out.print(s + " ");//输出a aa bb c d f
        }
}

4. 扩展
   TreeSet集合中添加自定义类型的元素，有两种方法：

• 自定义类紧密实现Comparable接口，并重写其compareTo()方法，在方法内部写明比较规则。创建TreeSet集合时调用无参构造，初始化comparator对象为null。

        Person p1 = new Person();
        //构造器底层初始化Comparator对象为null
        TreeSet<Person> h = new TreeSet<>();
        h.add(p1);
//实现Comparable接口并重写compareTo()方法
class Person implements Comparable<Person>{
     public int compareTo(Person p) {  //比较规则 }
}

• 自定义类分离实现Comparator接口，并重写其compare()方法，在方法内部写明比较规则。创建TreeSet集合时调用带参构造，初始化comparator对象为new Comparator。

        User u4 = new User();
        UserComparator us = new UserComparator();//创建Comparator比较器对象
        TreeSet<User> ts = new TreeSet<>(us);//构造器底层初始化Comparator
        ts.add(u4);

class User{  }
//实现Comparator接口并重写compare()方法
class UserComparator implements Comparator<User>{
    @Override
    public int compare(User u1, User u2) {  //比较规则}
}

3.2 Comparable 接口<TreeSet排序>

1. 概念
   当需要将自定义类型的元素放入到TreeSet集合中存储时，那么自定义类型的类 就必须要实现Comparable 接口，并且重写实现Comparable 接口的compareTo()方法。在compareTo()方法内重写的内容就是关于自定义类进行比较的规则。
2. 实现Comparable接口的作用

• 对基本类型元素排序： TreeSet 会对放入集合中的元素进行排序，如基本类型的包装类和 String 在底层都实现了 Comparable 接口，自动实现升序排序；
• 对自定义类型元素排序：Comparable 接口还可以对TreeSet中的自定义数据类型进行排序，但需要实现Comparable接口。未实现而放入TreeSet 中时，会出现ClassCastException类型转换异常--自定义类型不能转换为comparator类型。

3. 典型方法

• int compareTo(Object o) ：自定义类重写compareTo() 后，根据其返回值确定自定义类的排序顺序；
• 返回 = 0：表示添加到TreeSet中的元素相等，不需要更换顺序；
• 返回 > 0：表示添加到TreeSet中的元素，左边大于右边，升序排序；
• 返回 < 0：表示添加到TreeSet中的元素，左边小于右边，降序排序；

4. 代码示例

//自定义类 和 Comparable接口紧密实现
class Person implements Comparable {
         String name;
         int age;
         //重写compareTo方法，实现自定义类的比较规则，返回值0表示相等，返回-1表示降序排序，返回>0表示升序排序
         public int compareTo(Object o) {
               if (o instanceof Person) {
                   Person p = (Person)o;
                   //return (this.age - p.age);//升序
                   return (p.age - this.age);//降序
              }
                throw new IllegalArgumentException("非法参数：o=" + o);
          } 
}

3.3 Comparator比较器 接口<TreeSet排序>

1. 概念
   Comparator是用于比较两个元素的比较器，实现该接口的类，可以使用该接口特有的方法或比较规则 进行类的比较。
2. 使用位置
   TreeSet的add()方法底层调用TreeMap的put()方法；TreeMap底层的put()方法的实现采用Comparator作为比较器，用于比较TreeMap中的两个元素。
3. 自定义类与Comparator分离

public static void main(String[] args) {
           Person p1 = new Person( "张三",20);
           Person p3 = new Person( "张三",40);
           Person p2 = new Person( "李四",30);
           //创建比较器接口，比较两个对象(可能多属性)是否相等，然后排序
           Comparator personComparator = new PersonComparator(); 
           //创建set对象，同时初始化set集合的比较器(指定比较器对象)
           Set set = new TreeSet(personComparator);
           set.add(p1);  
           set.add(p2);  
           set.add(p3);
           //循环遍历迭代器，每个集合都实现了迭代器接口
           for (Iterator iter=set.iterator(); iter.hasNext();) {
                      Person p = (Person)iter.next();
                      System.out.println("name=" + p.name + ", age=" + p.age);
            } 
      } 
}
class Person {
          String name;
          int age;
          public Person( String name,int age){
                this.name = name;
                this.age = age;
          }
}
//Person实现Comparator比较器，可完成Person类的大小比较
class PersonComparator implements Comparator {
      public int compare(Object o1, Object o2) {
            if (!(o1 instanceof Person)) {
                    throw new IllegalArgumentException("非法参数：o1=" + o1);
            }
            if (!(o2 instanceof Person)) {
                    throw new IllegalArgumentException("非法参数：o2=" + o2);
            }
             Person p1 = (Person)o1;
             Person p2 = (Person)o2;
             return p1.age - p2.age;//根据Person的年龄排序
        }
}

四.Iterator接口

1. 概念
   Iterator 称为迭代接口，实现了Iterator接口的类，表示该类是可以被迭代的。同时Iterable接口中的iterator()方法返回的就是在一个集合元素的迭代器，以证明可以遍历集合中的数据。
   迭代：即遍历，可以循环输出集合中的元素。

• 迭代输出：将集合中的元素一个个的使用hasNext()方法进行判断，判断是否有内容，如果有内容就使用next()方法把内容输出。

2. 性质特点
   Iterator 是一种遍历查询模式，主要可以统一数据结构的访问元素的方式，不用关心各个数据结构 的具体实现。
3. 主要方法

• boolean hasNext()：判断该集合中是否有元素，如果仍有元素可以迭代，则返回 true；
• Object next()：返回可以迭代的下一个元素；
• void remove()：利用迭代器 从基础集合中移除迭代返回的最后一个元素，不会改变迭代集合的结构。若在集合的迭代过程中使用集合的remove()方法移除集合元素，会改变当前迭代器的迭代结构。

    public static void main(String[] args) {
        Collection c = new ArrayList();
        //在集合添加元素之前得到的迭代器，迭代集合时会发生异常：ConcurrentModificationException
        //Iterator it = c.iterator();
        c.add(1);//add加入的是Object类型数据，已使用自动装箱，1已装成Integer
        c.add(2);
        c.add(3);
        //在集合添加元素后得到的迭代器，遍历的集合结构会不一样
        Iterator it = c.iterator();
        while (it.hasNext()){
            it.next();
            //c.remove(1);//不能使用集合对象在迭代过程中remove元素，会改变迭代器迭代集合的结构，抛出异常：ConcurrentModificationException
            it.remove();//迭代过程中使用迭代器进行remove删除元素不会改变迭代集合的结构
        }
    }

4. 迭代器的执行原理

   
   
   迭代的实现原理.png

五.Map<图>

1. 概念
   Map是一个无序、采用键值对的形式存储数据的图。Map中的每一个元素包含一个键对象 和 一个值对象，即Map元素 = 键对象 + 值对象。键对象不允许重复，值对象可以重复<如：身份证号—姓名>。
2. 性质特点

• 键值对key-value：在Map中，所有子类都是采用键值对的方式存储元素，和Collection集合毫无关联关系；
• 无序：map中存入元素和取出元素的顺序不相同，put()添加元素的底层实现，采用hash()算法对key进行位置存储处理；
• key键不可重复：所有Map中存储的键key都是无序不可重复的，Map的key和Set集合存储元素的特点相同；
• key-Set转换：Set集合存元素在底层是put到map中的key部分，而map中的key也可以通过keySet()方法返回一个set集合。

3. 继承关系
   Map无继承父类和实现接口。和Collection同级，但和Collection、Iterator都无关，被HashMap、SortedMap<TreeMap>、HashTable等子类实现。
4. 使用特点

• Map的实现类较常用的是HashMap，HashMap对键的存取和HashSet 一样采用哈希算法；
• 如果使用自定义类<引用数据类型>作为 Map 的键对象，自定义类必须重写 equals() 和 hashCode()方法。

5. Map继承结构体系

   
   
   Map继承结构图.png
6. 特殊点
   Map中使用静态内部类Entry，将map中的键值对关系抽取出来形成set集合中存储的元素关系。
7. map遍历

• Set<K> keySet()方法：将所有key抽取出来到一个set集合中，对set集合迭代遍历，再使用get(key)方法获取得到对应的value，该方法将map中key-value的形式变成set中"key=value"的形式；
• Set<Map.Entry<K, V>> entrySet()：将所有的key和value全部抽出来到set集合中，而该set集合使用map的内部类map.entry<>作为集合元素类型。对set集合遍历后，使用get(key)和get(value)就可以获取对应的值。

8. 常用方法

• map.put(k,v)：往map中添加元素，key和value都只能存储引用数据类型-存地址
• map.size()：获取Map中存在的键值对数量；
• map.isEmpty()：判断map是否为空，底层调用size看键值对数是否为0；
• map.get(key)：根据key获取对应的value；
• map.containsKey(key)：判断是否包含指定key；
• map.containsValue(value)：判断是否包含指定value；
• map.remove(key)：根据指定键key删除一个数据；
• map.replace(key,newValue)：根据指定key，使用指定的新value替换旧value；
• map.keySet()：获取map中所有的key，并将获得key存到set集合中；
• map.clear()：清空map中的所有键值对

         //面向接口编程，创建一个map对象，并使用泛型指定map中存储的元素类型  
         Map<Integer,String> map = new HashMap();
        //往map中添加元素,key和value都只能存储引用数据类型-存地址
        map.put(1,"aaa");
        map.put(2,"bbb");
        map.put(3,"ccc");
        map.put(4,"dddd");
        map.put(5,"hahahah");
        map.put(5,"dududu");//key不能重复，往相同的key存储value时，会使用后面的value替换前面的value
        System.out.println(map.size());
        System.out.println(map.get(5));

        //获取map中所有的key存到set集合中
        Set<Integer> keys = map.keySet();
        //遍历Set中的key和value
        for (int i = 0;i<map.size();i++){
            System.out.println(map.get(i));
        }
        //for-each遍历
        for (Integer key:keys) {
            System.out.println(map.get(key));
        }
        //迭代器遍历
        Iterator<Integer> iterator = keys.iterator();
        while (iterator.hasNext()){
            Integer key = iterator.next();
            System.out.println(map.get(key));
        }

       //将map中所有的key和value抽取出来到set集合中，由(key,value) ---变成---> "key=value"
        Set<Map.Entry<Integer, String>> sets = map.entrySet();
        //对sets集合for-each遍历，泛型就是元素类型 = Map.Entry<Integer, String>
        for (Map.Entry<Integer, String> entry:sets) {
            System.out.println(entry.getKey() + "==" + entry.getValue());
        }
        //迭代器遍历
        Iterator<Map.Entry<Integer,String>> iterator1 = sets.iterator();
        while (iterator1.hasNext()){
            //遍历得到的元素类型就是指定的泛型Map.Entry<Integer,String>     
            Map.Entry<Integer,String> entry = iterator1.next();
            System.out.println(entry.getKey() + "==" + entry.getValue());
        }

5.1 哈希表

1. 概念
   哈希表是一种数据结构，能够提供快速存取操作<通过数组元素的值，可以换算出数据元素的下标，通过下标就可以快速定位数组元素>。
2. 性质特点
   哈希表是基于数组和哈希算法的，因此存在一旦创建将不能扩展，并且无序（哈希算法的散列特点）。

3. 实质
   哈希表 = 数组元素的值 + 元素值对应的下标（下标由元素值经过哈希算法得到）

   
   
   哈希表示例图.png

5.2 HashMap

1. 概念
   HashMap即Hash+Map，使用哈希算法存储数据的Map<键，值>集合。底层采用哈希表的数据结构存储数据，因此存入元素是无序不可重复的。HashMap的方法是无synchronized修饰的，因此是线程不安全的。
2. 静态接口Map.Entry<K,V>
   Map.Entry<K,V>是Map中的内部接口，HashMap实现了该内部接口，意为图的条目（所有键值对的个数）。该接口主要存储了Map中所有的key和value，并将该接口作为一个set集合的泛型，相当于将map中所有键值对存到set集合中，方便查询。

3. HashMap实现

   
   
   HashMap底层图解.png
4. 字段

• int size：map中键值对的个数；
• int DEFAULT_INITIAL_CAPACITY = 1 << 4：默认初始化容量为16，1 << 4表示 二进制数1左移4为得到二进制数16；
• int MAXIMUM_CAPACITY = 1 << 30：左移30位最大容量；
• float DEFAULT_LOAD_FACTOR = 0.75f：默认加载因子，当HashMap集合底层数组容量达到75%时，Node<>[]数组开始扩容；
• int TREEIFY_THRESHOLD = 8：默认临界值，当数组元素下的单向链表节点数超过8个时，链表变成红黑树；
• int UNTREEIFY_THRESHOLD = 6：取消临界值，当红黑树的节点个数小于6个时，将节点变成单向链表；
• int MIN_TREEIFY_CAPACITY = 64：最小树容量。

5. 常用方法

• K getKey()：获取map中的key；
• V getValue()：获取map中的value；
• String toString() ：
• int hashCode() ：获取当前map的hashCode()内存地址；
• V setValue(V newValue) ：使用新的value替换旧value；
• boolean equals(Object o)：判断map中的key是否与指定o相等；
• int hash(Object key)：获取指定key的哈希值，即key在数组中的下标；
• map.put(k,v)：添加键值对元素；
• v = map.get(k)：根据指定key获取对应的value值；
• 遍历Map：先取出key，再根据key获取value；
• 遍历Map：将key和value都取出，直接获取对应的key和value。

6. 底层实现

    //Node<>实现Map的内部接口，将key和value保存为一个泛型-元素类型   
    //HashMap底层存储形式Node<>[]的自我实现     
    static class Node<K,V> implements Map.Entry<K,V> {
    //该hash是key调用hashCode()得出哈希值，将哈希值通过哈希算法得到的数组下标
        final int hash;// hash == 下标
        final K key;//key键
        V value;//键对应的value值
        Node<K,V> next;//下一个节点(de内存地址)
        //内部类构造方法        
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

    //HashMap底层存储元素的形式就是数组，而该Node<>[]数组在HashMap内部已自己实现（如前面显示）
    transient Node<K,V>[] table;
    //HashMap底层的内部接口，用于实现entrySet()方法    
    transient Set<Map.Entry<K,V>> entrySet;
}

5.1.1 HashMap与红黑树

1. 关系
   在HashMap的底层实现中，HashMap使用 Node<>[]数组 + 链表的组合形式进行存储数据的，每个数组元素下挂着一条单向链表。HashMap规定了当链表的节点个数超过8个时，该单向链表变成红黑树；而当红黑树的节点个数少于6个时，该红黑树变成单向链表。
2. 原因
   当HashMap中存储的元素过多时，不管是Node<>[]还是数组下的链表，都会影响执行效率，因此改变单向链表结构为成红黑树时，可以提高数据的查询检索效率。

5.2 SortedMap

1. 概念
   SortedMap是一个可以排序的Map集合，实现SortedMap的子类可以完成对key的自动升序排序。

5.2.1 自平衡二叉树

1. 概念
   自平衡二叉是一种完全二叉树，始终遵循左小右大的原则，即左子树永远小于右子树，左节点数小于右节点数。

2. 图解

   
   
   自平衡二叉树的实现.png
3. 自平衡二叉树遍历方式

• 先序遍历：根-左-右
  先遍历数的根节点root，
  再遍历左节点（左节点若有分支也是从根节点开始，然后左节点，到右节点），
  再遍历右节点（右节点若有分支也是从根节点开始，然后左节点，到右节点）
• 中序遍历：左-根- 右(TreeSet和TreeMap默认中序遍历)
  先遍历左子树（若左子树有分支，也是先遍历左节点，到根节点，然后右节点），
  再遍历根节点root，
  再遍历右子树（若左子树有分支，也是先遍历左节点，到根节点，然后右节点）
• 后序遍历：左-右-根
  先遍历左子树（若左子树有分支，也是先遍历左节点，到右节点，然后根节点），
  再遍历右子树（若左子树有分支，也是先遍历左节点，到右节点，然后根节点），
  再到根节点root

5.3TreeMap

1. 概念
   TreeMap即Tree + Map，TreeMap首先是一颗二叉树，而二叉树中的每一个节点是Map<>类型。TreeMap是可以对 Map中的键key 进行排序的集合。底层采用二叉树的数据结构存储元素。
2. 要求

• 基本数据类型或String类型：TreeMap底层可以自动对基本数据类型和String类型的元素进行自动排序，且排为升序。
• 自定义类型：若 map 中的 key 采用的是自定义的引用数据类型，那自定义的引用类需要实现Comaprable 或 Comparator 接口完成排序。

3. 字段

• Comparator<? super K> comparator：Comparator比较器，使用于put方法的实现中，完成对元素的排序；
• Entry<K,V> root：二叉树的root根节点；
• int size = 0：二叉树节点个数；
• int modCount = 0：用于统计的变量，初始为0；
• 内部类：在TreeMap的底层实现中，定义了许多静态内部类、成员内部类等，满足底层自我需求。

4. 常用方法

• int size()：获取TreeMap中二叉树节点的个数；
• boolean containsKey(Object key)：判断是否包含指定key的节点；
• boolean containsValue(Object value)：判断是否包含指定value的节点；
• V get(Object key)：根据指定key返回对应的value值；
• Comparator<? super K> comparator()：获取当前TreeMap中元素的比较器；
• K firstKey()：获取二叉树中的第一个key；
• K lastKey()：获取二叉树中的最后一个key；
• Entry<K,V> getEntry(Object key)：
• V put(K key, V value)：给指定key替换新的value值，返回旧的value值；
• V remove(Object key)：根据指定key删除节点，返回被删除key对应的value值；
• void clear()：清楚所有键值对，底层直接将size置0，根节点root置null；
• Object clone()：复制一份当前TreeMap对象，可能使用深克隆；
• Map.Entry<K,V> firstEntry()：
• Set<K> keySet()：获取二叉树中所有节点的key，并将其返回到set集合中；
• Collection<V> values()：获取二叉树中所有节点的value，并将其返回到Collection集合中；
• Set<Map.Entry<K,V>> entrySet()：获取二叉树中所有节点的key和value，并返回到set集合中；
• V replace(K key, V value)：使用新的value值替换指定key的旧value值；
• void forEach()：在当前TreeMap上进行for-each增强循环，调用该方法即可循环，不需要手动编写for-each循环。

5. 底层部分关键源码实现

//TreeMap底层实现了
public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
  
    //无参构造，创建TreeMap对象时，comparator比较器初始化为null
    public TreeMap() {
        comparator = null;
    }
    //带参构造，创建TreeMap对象时，初始化comparator比较器对象为comparator的实现类
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    //根据指定键key获取二叉树结点    
    final Entry<K,V> getEntry(Object key) {
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
}

5.4 Hashtable<哈希表、散列表>

1. 概念
   Hashtable底层采用哈希表的数据结构存储数据，因散列点的特点具有无序性。且Hashtable中的方法都是由synchronized修饰，因此是线程安全的。
2. 实现
   Hashtable是根据关键码-值<键值对>而直接访问的数据结构，通过把关键码映射到表中一个位置来访问元素。通过hash()算法得到key的下标来读取元素值value。
3. 性质特点
   哈希表就是将数组 和 链表两者结合的产物，查找容易<数组的特点>，插入删除也很快<单向链表的特点>。

• 数组的特点：查找容易，插入删除困难；
• 链表的特点：查找困难，但是插入删除容易。

4. Hashtable实现原理

   
   
   Hashtable图解.png
5. Hashtable实现关键

• hashCode()方法：重写hashCode()方法可以得到key在哈希表数组部分的下标；
• equals()方法：重写equals()方法可以匹配目标key和原链表key是否相等，也因key匹配的不一定就是数组下标的key，可能是数组元素下链表中的key，因此Hashtable和HashMap存入顺序与读取顺序是不一样的。HashSet也是如此。

5.4.1 Properties

1. 概念
   Properties是继承于Hashtable的一个子类，底层也是采用键值对的形式存储数据，而且存储的键和值只能是 String字符串类型的，加上Properties中所有的方法都是synchronized修饰的，因此Properties也是线程安全的。
2. 性质特点

• 线程安全：Properties存储的key和value都只能是String类型的；Properties的方法都是synchronized修饰的

3. 常用方法

• String setProperty("key","value")：往Properties中存入数据，存入的key和value只能是String类型；
• String getProperty("key")：从Properties取出数据，取出的key只能是String类型。

六. java.util.Collections 工具类

1. 概念
   Collections类完全由 在collection上进行操作或返回collection的静态方法组成，是collection功能的扩展类。
2. 特点
   提供一系列实用的方法，可以完成对collection集合排序，对集合中的内容查找等。
3. 常用方法

• 排序方法 Collections.sort(集合对象)：对一个集合进行排序，只能对List类型的集合排序；
• 二分查找 int Collections.binarySearch(集合对象, 目标元素)：返回一个目标元素的下标；
• 反转字符串 Collections.reverse(集合对象)：将一个字符串的顺序反转；
• synchronizedCollection(集合对象)：将非线程安全的集合通过外挂将其变成线程安全的。

        //创建一个List对象，Collections.sort()中只能对List类型集合排序      
        List<Integer> list = new ArrayList<>();
        list.add(234);
        list.add(678);
        list.add(856);
        list.add(444);
        list.add(91);
        Collections.sort(list);
        for (Integer i:list) {
            System.out.println(i);
        }

        int n = Collections.binarySearch(list,234);//234的下标：n = 1
        List<String> l = new ArrayList<>();
        l.add("Are you ok");
        Collections.reverse(l);

七.泛型<E>

1. 概念
   在java程序编码中，泛型指的是一些 包含类型参数的类。泛型参数只可以代表类的种类/种型，不能代表个别对象。
2. 实质
   泛型就是 泛参数类型，属于引用数据类型，泛型 = 集合/数组中元素的类型。
3. 作用特点

• 泛型就是元素的类型，泛型限定了集合的元素类型，能更早的发现错误。如ClassCastException 类型转换异常，jvm通常在运行期才会现；如果使用泛型，jvm在编译期就会发现错误。
• 发现错误越早，越容易调试，越容易减少成本；
• 泛型定义后，该泛型的类型集合中 不能存储与泛型不同的参数数据；
• 泛型实现功能与 instanceOf字符类似，使用泛型后，可以不用进行强制转换。

7.1 泛型的类型

1. 类-泛型
   使用类泛型，可以指定方法的返回结果是自定义类的泛型，而不是一般的Object类型。使用字母T表示类泛型，T表示所有类型的公共高级接口，包括原始类型、参数化类型、数组类型、类型变量和基本类型等。

class My<T>{
    public T doMy(){
        return null;
    }
}

2. 方法参数-泛型
   使用方法形参泛型，可以指定方法的参数类型。

public class AutoGeneric<autoString> {
    //基本类型参数
    public void dosome(int i){
        System.out.println(i);
    }
    //泛型类型的参数
    public void domore(autoString str){
        System.out.println(str);
    }
}

7.2 自定义泛型

1. 概念
   使用自定义的 引用数据类型(即自定义类)作为泛型，限定集合中只能存储自定义类类型的元素，从而满足实际的开发需求。
2. 特点
   通常情况下，自定义泛型一般使用 T 和 E 表示。

• T：type，表示所有类型的公共高级接口。它们包括原始类型、参数化类型、数组类型、类型变量和基本类型；
• E：element，表示一个程序元素，如包、类、方法；

3. 作用
   使用泛型可以指定自定义泛型类中方法的参数类型、方法的返回结果类型都是泛型；不使用泛型时，方法的返回结果类型通常都是Object类型。

class My<T>{
    public T doMy(){
        return null;
    }
}
class AutoGeneric<autoString> {
    public void dosome(int i){
        System.out.println(i);
    }
    public void domore(autoString str){
        System.out.println(str);
    }

    public static void main(String[] args) {
        //使用泛型创建对象        
        AutoGeneric<String> ag = new AutoGeneric<>();
        ag.domore("autoString type");//IDEA提示参数类型是autoString泛型
        ag.dosome(23);//IDEA提示参数类型是int类型

        //不使用泛型创建对象
        AutoGeneric aug = new AutoGeneric();
        aug.domore("Object type");//提示参数类型是Object类型
        ag.dosome(88);//提示参数类型是int类型

        My m = new My();
        m.doMy();//调用方法时，IDEA提示返回的结果是Object类型
        My<Integer> my = new My<Integer>();
        my.doMy();//调用方法时，IDEA提示返回的结果是Integer类型
    }
}

7.3 自动类型推断机制

1. 概念
   自动类型推断机制又称钻石表达式。在集合的泛型中，jvm支持自动类型推断，当子类型集合没有写明泛型时，可自动根据父类型的泛型推断出子类型集合的元素类型。
2. 示例

public static void main(String[] args) {
        // ArrayList<此泛型类型自动推断>()，JDK8之后才允许
        List<Animal> myList = new ArrayList<>();
        //List<> list1 = new ArrayList<Animal>();//支持父类型泛型自动推断出子类型，不支持子类型泛
        myList.add(new Animal());
        myList.add(new Cat());
        myList.add(new Bird());
        // 遍历
        Iterator<Animal> it = myList.iterator();
        while(it.hasNext()){
            Animal a = it.next();
            a.move();
        }

        List<String> strList = new ArrayList<>();
        /*类型不匹配
        strList.add(new Cat());
        strList.add(123);
        */
        //自动类型推断参数类型为String            
        strList.add("http://www.126.com");
    }

7.4 for-each循环增强遍历机制

1. 优缺点

• 优点：语法格式简洁，对于集合或数组可以快速遍历
• 缺点：遍历时无下标，因此在使用下标遍历的需求中不合适

2. 示例

public static void main(String[] args) {
        // 创建List集合
        List<String> strList = new ArrayList<>();
        // 添加元素
        strList.add("hello");
        strList.add("world!");
        strList.add("kitty!");
        // 遍历，使用迭代器方式
        Iterator<String> it = strList.iterator();
        while(it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        // 使用下标方式（只针对于有下标的集合）
        for(int i = 0; i < strList.size(); i++){
            System.out.println(strList.get(i));
        }
        // 使用foreach
        for(String s : strList){ //泛型使用的是String类型，所以返回也是String 
            System.out.println(s);
        }
    }

常见面试题

1. 为什么重写hashCode()方法的同时需要重写equals()方法？
   答：

• 因为在Map中，数据是以键值对的形式存在的。
• 而在Hashtable中，Hashtable底层是使用Node<>[ ]数组+链表的组合形式存储数据的，数组的同一个下标之下有一条单向链表。
• 重写hashCode()只能得到key在数组中的下标，但是并未能确定key在链表的具体位置，也不能确定key是否之前已经存在。
• 因此还需要重写equals()方法，可以更加确定key的位置，并且判断key是否已存在。
• 同一个数组下有一条链表，链表中存储了多个不同的key，因此hashCode相同只能得到相同的key数组下标，不能判断key对应的value就一定相等。
• 重写的hashCode()方法也因此不能只返回一个固定值。

2. 这么多的集合中，你用哪个集合最多？
   答：ArrayList集合。
   因为往数组添加元素，实则在它的末尾添加元素，效率不受影响。另外，我们在实际运用中，搜索和查找某个元素的操作比较多，数组查找元素的效率高。
   检索效率比较高（每个元素占用空间大小相同，数组的内存地址是连续的，知道首元素内存地址，知道下标，通过数学表达式计算出元素的内存地址，所以检索效率最高）。

3. 使用集合模拟单向链表的实现？
   答：单向链表的特点，以节点为基础单元，每个节点包含数据部分+指向下一个节点的地址组成。可以将节点当作一个对象，而链表就是由多个节点组成。

//节点类
public class Node {
    int data;//节点的数据
    Node next = null;//指向下一节点的内存地址,起初都为空
    public Node() {
    }
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}
//链表
public class Link {
    private Node head = null;//链表头节点,初始为空
    private int size;//链表长度
    //创建节点
    public Link() {
    }
    public Link(Node head) {
        this.head = head;
    }

    public int size(){
        size = 0;//链表初始长度为0
        Node currentNode;//创建新节点-指向当前节点
        currentNode = head;//size=0时，头节点为当前节点
        while (currentNode != null){
            size++;//
            currentNode = currentNode.next;//将下一个节点的内存地址赋给当前节点保存
        }
        return size;
    }
    //添加节点：找到链表的末尾节点，把新的数据节点添加在后面
    public void addNode(int data){
        //创建要添加的节点对象
        Node newnode = new Node(data);
        if (head == null) {     //判断头结点是否为空--遍历从头到尾
            head = newnode;//头节点为空，直接保存新节点
            return;
        } else {
            /*
            Node currentNode = head;
            currentNode.next = newnode;//将要添加的节点作为下一个节点
             */
            Node currentNode = head;
            while (currentNode.next != null) {  //找到下一个节点直至末尾
                currentNode = currentNode.next;//将下一个节点的内存地址赋给当前节点
            }
            currentNode.next = newnode;//将要添加的节点作为下一个节点
        }
    }
    //删除节点：根据下标找到相应的节点,将删除节点的前一节点 指向 删除节点的下一节点
    //由 前-> 删除-> 后  ===变成===>  前-> 后
    public boolean deleteNode(int index){
        if (index < 1 || index > size()) {
            System.out.println("删除的元素下标超出范围");
            return false;
        }
        if (index == 1) {
            head = head.next;
            return true;
        }
        Node pre_node = head;//前节点
        Node cur_node = pre_node.next;//要删除的节点
        int i = 2;//
        while (pre_node != null) {
            if (i == index) {
                pre_node.next = cur_node.next;//删除当前节点，将删除节点的下一个节点内存地址 赋给 前一节点
                return true;
            } else {//向下遍历链表
                pre_node = pre_node.next;
                cur_node = cur_node.next;
                i++;
            }
        }
        return true;
    }
    //查询节点,根据数据data查找节点，返回节点的下标
    public int selectNode(int data){
        Node node = head;//从头开始遍历链表
        int index = 0;//从下标0开始遍历链表
        while (node != null){
            if (node.data == data){
                return index;
            }
            node = node.next;//遍历下一个节点
            index++;
        }
        return -1;//
    }
   //修改节点
    public boolean updateNode(int Index,int data){
        Node node = head;//从头开始遍历链表
        int index = 0;
        while (node != null){
            if(index == Index){
                node.data = data;
                return true;
            }
            node = node.next;//遍历下一个节点
            index++;
        }
        return false;
    }
    //遍历输出节点
    public void printLink() {
        Node node = head;//从头开始遍历链表
        while (node != null) {
            System.out.print(node.getData() + " ");
            node = node.next;//遍历下一个节点
        }
        System.out.println();
    }
}
//测试

3. 简单描述一下泛型机制？
   答：

4. 讲述以下HashMap和Hashtable的区别？
   答：

• HashMap：底层是哈希表的数据结构，采用数组存储元素。HashMap的方法无synchronized修饰，是非线程安全的；HashMap允许存入的key或value都为null；HashMap初始化容量为16，扩容的容量为原来的两倍(超过75%就扩容)；
• Hashtable：底层是哈希表的数据结构，采用数组存储元素。Hashtable的方法采用synchronized修饰，是线程安全的；Hashtable不允许存入的key或value任何一个为null，Hashtable在使用put()方法存入元素时，底层都调用了equals()方法判断存入的值是否为空；Hashtable初始化容量为11，扩容的容量为原来的两倍+1。

2. Comparator 和 Comparable 的区别？
   答：

• Comparable是默认的比较接口，Comparable 和需要比较的对象紧密结合到一起；
• Comparator 可以分离比较规则，更具灵活性。
  一个类实现了 Camparable 接口则表明这个 类的对象 之间是可以相互比较的，这个类对象组成的集合也就可以直接使用 sort 方法排序。
  Comparator 可以看成一种算法的实现，将算法和数据分离<对象 和 对象的比较实现>

3. 请使用两种方法完成从一个数组中查找得到一个目标数据，并讲明原理。
   冒泡排序
   选择排序

4. 说一下数组和链表的认识，查询效率更高的是哪个？修改删除效率更高的是哪个？说明原因。
   答：
   第一：空间存储上，内存地址是连续的。
   第二：每个元素占用的空间大小相同。
   第三：知道首元素的内存地址。
   第四：通过下标可以计算出偏移量。
   通过一个数学表达式，就可以快速计算出某个下标位置上元素的内存址，直接通过内存地址定位，效率非常高。

优点：检索效率高。
缺点：随机增删效率较低，数组无法存储大数据量。
注意：数组最后一个元素的增删效率不受影响。