11_集合

集合框架的概述

开发中能用集合就不要用数组

集合框架概述

• 一方面， 面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象 的操作，就要对对象进行存储。另一方面，使用Array存储对象方面具有一些弊 端，而Java 集合就像一种容器，可以动态地把多个对象的引用放入容器中。

  • 数组在内存存储方面的特点：
    • 数组初始化以后，长度就确定了。
    • 数组声明的类型，就决定了进行元素初始化时的类型
  • 数组在存储数据方面的弊端：
    • 数组初始化以后，长度就不可变了，不便于扩展
    • 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。 同时无法直接获取存储元素的个数
    • 数组存储的数据是有序的、可以重复的。---->存储数据的特点单一

• Java 集合类可以用于存储数量不等的多个对象，还可用于保存具有映射关系的 关联数组。

• Java集合可分类Collection 和 Map 两种体系

  • Collection接口：单列数据，定义了存取一组对象的方法的集合
    • List：元素有序、可重复的集合（也叫动态数组）
    • Set：元素无序、不可重复的集合
  • Map接口：双列数据，保存具有映射关系”key-value“ 的集合

集合与数组存储数据的概述

集合、数组都是对多个数据进行存储操作的结构，简称Java容器。
说明：此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储（.txt,.jpg,.avi，数据库中）

数组存储的特点

• 一旦初始化以后，其长度就确定了。
• 数组一旦定义好，其元素的类型也就确定了。我们也就只能操作指定类型的数据了。
  比如：String[] arr;int[] arr1;Object[] arr2;

数组存储的弊端

• 一旦初始化以后，其长度就不可修改。
• 数组中提供的方法非常有限，对于添加、删除、插入数据等操作，非常不便，同时效率不高。
• 获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
• 数组存储数据的特点：有序、可重复。对于无序、不可重复的需求，不能满足。

集合存储的特点

解决数组存储数据方便的弊端。

集合框架

|----Collection接口：单列集合，用来存储一个一个的对象
         |----List接口：存储有序的、可重复的数据。  -->“动态”数组
             |----ArrayList、LinkedList、Vector
         |----Set接口：存储无序的、不可重复的数据   -->高中讲的“集合”
             |----HashSet、LinkedHashSet、TreeSet
     |----Map接口：双列集合，用来存储一对(key - value)一对的数据   -->高中函数：y = f(x)
             |----HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

单列集合框架结构

双列集合框架

Collection 接口

• Collection 接口是 List、Set 和 Queue 接口的父接口，该接口里定义的方法 既可用于操作 Set 集合，也可用于操作 List 和 Queue 集合。
• JDK不提供此接口的任何直接实现，而是提供更具体的子接口(如：Set和List) 实现。
• 在 Java5 之前，Java 集合会丢失容器中所有对象的数据类型，把所有对象都 当成 Object 类型处理；从 JDK 5.0 增加了泛型以后，Java 集合可以记住容 器中对象的数据类型。

Collection常用的方法

@Test
public void test1(){
  Collection coll = new ArrayList();

  //add(Object e):将元素e添加到集合coll中
  coll.add("AA");
  coll.add("BB");
  coll.add(123);//自动装箱
  coll.add(new Date());

  //size():获取添加的元素的个数
  System.out.println(coll.size());//4

  //addAll(Collection coll1):将coll1集合中的元素添加到当前的集合中
  Collection coll1 = new ArrayList();
  coll1.add(456);
  coll1.add("CC");
  coll.addAll(coll1);

  System.out.println(coll.size());//6
  System.out.println(coll);

  //clear():清空集合元素
  coll.clear();

  //isEmpty():判断当前集合是否为空
  System.out.println(coll.isEmpty());

}

/**
 * Collection接口中声明的方法的测试
 * <p>
 * 结论：
 * 向Collection接口的实现类的对象中添加数据obj时，要求obj所在类要重写equals().
 *
 * @author shkstart
 * @create 2019 上午 10:04
 */
public class CollectionTest {


  @Test
  public void test1() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    //        Person p = new Person("Jerry",20);
    //        coll.add(p);
    coll.add(new Person("Jerry", 20));
    coll.add(new String("Tom"));
    coll.add(false);
    //1.contains(Object obj):判断当前集合中是否包含obj
    //我们在判断时会调用obj对象所在类的equals()。
    boolean contains = coll.contains(123);
    System.out.println(contains);
    System.out.println(coll.contains(new String("Tom")));
    //        System.out.println(coll.contains(p));//true
    System.out.println(coll.contains(new Person("Jerry", 20)));//false -->true

    //2.containsAll(Collection coll1):判断形参coll1中的所有元素是否都存在于当前集合中。
    Collection coll1 = Arrays.asList(123, 4567);
    System.out.println(coll.containsAll(coll1));
  }

  @Test
  public void test2() {
    //3.remove(Object obj):从当前集合中移除obj元素。
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add(new Person("Jerry", 20));
    coll.add(new String("Tom"));
    coll.add(false);

    coll.remove(1234);
    System.out.println(coll);

    coll.remove(new Person("Jerry", 20));
    System.out.println(coll);

    //4. removeAll(Collection coll1):差集：从当前集合中移除coll1中所有的元素。
    Collection coll1 = Arrays.asList(123, 456);
    coll.removeAll(coll1);
    System.out.println(coll);


  }

  @Test
  public void test3() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add(new Person("Jerry", 20));
    coll.add(new String("Tom"));
    coll.add(false);

    //5.retainAll(Collection coll1):交集：获取当前集合和coll1集合的交集，并返回给当前集合
    //        Collection coll1 = Arrays.asList(123,456,789);
    //        coll.retainAll(coll1);
    //        System.out.println(coll);

    //6.equals(Object obj):要想返回true，需要当前集合和形参集合的元素都相同。
    Collection coll1 = new ArrayList();
    coll1.add(456);
    coll1.add(123);
    coll1.add(new Person("Jerry", 20));
    coll1.add(new String("Tom"));
    coll1.add(false);

    System.out.println(coll.equals(coll1));


  }

  @Test
  public void test4() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add(new Person("Jerry", 20));
    coll.add(new String("Tom"));
    coll.add(false);

    //7.hashCode():返回当前对象的哈希值
    System.out.println(coll.hashCode());

    //8.集合 --->数组：toArray()
    Object[] arr = coll.toArray();
    for (int i = 0; i < arr.length; i++) {
      System.out.println(arr[i]);
    }

    //拓展：数组 --->集合:调用Arrays类的静态方法asList()
    List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
    System.out.println(list);

    List arr1 = Arrays.asList(new int[]{123, 456});
    System.out.println(arr1.size());//1

    List arr2 = Arrays.asList(new Integer[]{123, 456});
    System.out.println(arr2.size());//2

    //9.iterator():返回Iterator接口的实例，用于遍历集合元素。放在IteratorTest.java中测试

  }
}

Iterator迭代器接口

使用Iterator接口遍历集合元素

集合元素的遍历操作，使用迭代器Iterator接口
1.内部的方法：hasNext() 和  next()
2.集合对象每次调用iterator()方法都得到一个全新的迭代器对象，
默认游标都在集合的第一个元素之前。
3.内部定义了remove(),可以在遍历的时候，删除集合中的元素。此方法不同于集合直接调用remove()

@Test
public void test1(){
  Collection coll = new ArrayList();
  coll.add(123);
  coll.add(456);
  coll.add(new Person("Jerry",20));
  coll.add(new String("Tom"));
  coll.add(false);

  Iterator iterator = coll.iterator();
  //方式一：
  //        System.out.println(iterator.next());
  //        System.out.println(iterator.next());
  //        System.out.println(iterator.next());
  //        System.out.println(iterator.next());
  //        System.out.println(iterator.next());
  //        //报异常：NoSuchElementException
  //        System.out.println(iterator.next());

  //方式二：不推荐
  //        for(int i = 0;i < coll.size();i++){
  //            System.out.println(iterator.next());
  //        }

  //方式三：推荐
  hasNext():判断是否还有下一个元素
  while(iterator.hasNext()){
    //next():①指针下移 ②将下移以后集合位置上的元素返回
    System.out.println(iterator.next());
  }
}

//测试Iterator中的remove()
//如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，
// 再调用remove都会报IllegalStateException。
@Test
public void test3(){
  Collection coll = new ArrayList();
  coll.add(123);
  coll.add(456);
  coll.add(new Person("Jerry",20));
  coll.add(new String("Tom"));
  coll.add(false);

  //删除集合中"Tom"
  Iterator iterator = coll.iterator();
  while (iterator.hasNext()){
    //            iterator.remove();
    Object obj = iterator.next();
    if("Tom".equals(obj)){
      iterator.remove();
      //                iterator.remove();
    }

  }
  //遍历集合
  iterator = coll.iterator();
  while (iterator.hasNext()){
    System.out.println(iterator.next());
  }
}

Jdk5 新增foreach方便我们遍历集合元素

底层还是使用iterator和hasNext()next()然后将next() 的值赋值给局部变量。

/**
 * jdk 5.0 新增了foreach循环，用于遍历集合、数组
 *
 * @author shkstart
 * @create 2019 上午 11:24
 */
public class ForTest {

    @Test
    public void test1(){
        Collection coll = new ArrayList();
        coll.add(123);
        coll.add(456);
        coll.add(new Person("Jerry",20));
        coll.add(new String("Tom"));
        coll.add(false);

        //for(集合元素的类型 局部变量 : 集合对象)
        //内部仍然调用了迭代器。
        for(Object obj : coll){
            System.out.println(obj);
        }
    }

    @Test
    public void test2(){
        int[] arr = new int[]{1,2,3,4,5,6};
        //for(数组元素的类型 局部变量 : 数组对象)
        for(int i : arr){
            System.out.println(i);
        }
    }
}

Collection子接口

开发中list接口用的比较多，set用得少，了解即可。

Collection子接口之一：List接口

List接口概述

• 鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组
• List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
• List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据 序号存取容器中的元素。
• JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector。

ArrayList的源码分析

 2. ArrayList的源码分析：
 2.1 jdk 7情况下
    ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementData
    list.add(123);//elementData[0] = new Integer(123);
    ...
    list.add(11);//如果此次的添加导致底层elementData数组容量不够，则扩容。
    默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。
    结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)
 2.2 jdk 8中ArrayList的变化：
    ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}.并没有创建长度为10的数组
    list.add(123);//第一次调用add()时，底层才创建了长度10的数组，并将数据123添加到elementData[0]
    ...
    后续的添加和扩容操作与jdk 7 无异。
 2.3 小结：jdk7中的ArrayList的对象的创建类似于单例的饿汉式，而jdk8中的ArrayList的对象
          的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。         

LinkedList的源码分析

3. LinkedList的源码分析：
    LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null。通过first和last两个属性就能确定链表里面的所有元素。
    list.add(123);//将123封装到Node中，创建了Node对象。
    其中，Node定义为：体现了LinkedList的双向链表的说法
    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;
         }
     }

// 向后添加一个元素
/**
* Links e as last element.
*/
void linkLast(E e) {
  final Node<E> l = last;
  final Node<E> newNode = new Node<>(l, e, null);// 前一个元素，当前元素，后一个元素
  last = newNode;
  if (l == null) // 一开始没添加数据的时候，第一个数据就是null(就是集合长度为0的情况)
    first = newNode;
  else // 集合中有元素了。
    l.next = newNode;
  size++;
  modCount++;
}

Vector的源码分析

Vector的源码分析：jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。
 *      在扩容方面，默认扩容为原来的数组长度的2倍。

List接口的常用方法

void add(int index, Object ele):在index位置插入ele元素
boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
Object get(int index):获取指定index位置的元素
int indexOf(Object obj):返回obj在集合中首次出现的位置
int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
Object remove(int index):移除指定index位置的元素，并返回此元素
Object set(int index, Object ele):设置指定index位置的元素为ele
List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合

总结：常用方法
增：add(Object obj)
删：remove(int index) / remove(Object obj)
改：set(int index, Object ele)
查：get(int index)
插：add(int index, Object ele)
长度：size()
遍历：① Iterator迭代器方式
     ② 增强for循环
     ③ 普通的循环

@Test
public void test3(){
  ArrayList list = new ArrayList();
  list.add(123);
  list.add(456);
  list.add("AA");

  //方式一：Iterator迭代器方式
  Iterator iterator = list.iterator();
  while(iterator.hasNext()){
    System.out.println(iterator.next());
  }

  System.out.println("***************");

  //方式二：增强for循环
  for(Object obj : list){
    System.out.println(obj);
  }

  System.out.println("***************");

  //方式三：普通for循环
  for(int i = 0;i < list.size();i++){
    System.out.println(list.get(i));
  }



}


@Test
public void test2(){
  ArrayList list = new ArrayList();
  list.add(123);
  list.add(456);
  list.add("AA");
  list.add(new Person("Tom",12));
  list.add(456);
  //int indexOf(Object obj):返回obj在集合中首次出现的位置。如果不存在，返回-1.
  int index = list.indexOf(4567);
  System.out.println(index);

  //int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置。如果不存在，返回-1.
  System.out.println(list.lastIndexOf(456));

  //Object remove(int index):移除指定index位置的元素，并返回此元素
  Object obj = list.remove(0);
  System.out.println(obj);
  System.out.println(list);

  //Object set(int index, Object ele):设置指定index位置的元素为ele
  list.set(1,"CC");
  System.out.println(list);

  //List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的左闭右开区间的子集合
  List subList = list.subList(2, 4);
  System.out.println(subList);
  System.out.println(list);


}


@Test
public void test1(){
  ArrayList list = new ArrayList();
  list.add(123);
  list.add(456);
  list.add("AA");
  list.add(new Person("Tom",12));
  list.add(456);

  System.out.println(list);

  //void add(int index, Object ele):在index位置插入ele元素
  list.add(1,"BB");
  System.out.println(list);

  //boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
  List list1 = Arrays.asList(1, 2, 3);
  list.addAll(list1);
  //        list.add(list1);
  System.out.println(list.size());//9

  //Object get(int index):获取指定index位置的元素
  System.out.println(list.get(0));

}

Collection子接口之二：set接口

set接口概述

• Set接口是Collection的子接口，set接口没有提供额外的方法
• Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。
• Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法
• HashSet、LinkedHashSet、TreeSet底层是使用Map存储数据的，所以源码请看Map部分。

private static final Object PRESENT = new Object();
public boolean add(E e) {
  // 传入set的值作为key，value是一个全局常量
  return map.put(e, PRESENT)==null;
}

1. Set接口的框架：
|----Collection接口：单列集合，用来存储一个一个的对象
         |----Set接口：存储无序的、不可重复的数据   -->高中讲的“集合”
             |----HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
                 |----LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历
                                     对于频繁的遍历操作，LinkedHashSet效率高于HashSet.
             |----TreeSet：可以按照添加对象的指定属性，进行排序。
 1. Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法。
 2. 要求：向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()
    要求：重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列码
     重写两个方法的小技巧：对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。
     

一、Set：存储无序的、不可重复的数据
    以HashSet为例说明：
    1. 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。

    2. 不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。

重写 hashCode() 方法的基本原则

• 在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。
• 当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode() 方法的返回值也应相等。
• 对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

重写 equals() 方法的基本原则

以自定义的Customer类为例，何时需要重写equals()？

• 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候，总是 要改写hashCode()，根据一个类的equals方法（改写后），两个截然不 同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法， 它们仅仅是两个对象。

• 因此，违反了“相等的对象必须具有相等的散列码”。

• 结论：复写equals方法的时候一般都需要同时复写hashCode方法。通 常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

Eclipse/IDEA工具里hashCode()的重写

以Eclipse/IDEA为例，在自定义类中可以调用工具自动重写equals和hashCode。 问题：为什么用Eclipse/IDEA复写hashCode方法，有31这个数字？

• 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的 “冲突”就越少，查找起来效率也会提高。（减少冲突）
• 并且31只占用5bits,相乘造成数据溢出的概率较小。
• 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。（提高算法效 率）
• 31是一个素数，素数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结 果只能被素数本身和被乘数还有1来整除！(减少冲突)

HashSet

• HashSet 是 Set 接口的典型实现，大多数时候使用 Set 集合时都使用这个实现类。

• HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除 性能。

• HashSet 具有以下特点：

  • 不能保证元素的排列顺序
  • HashSet 不是线程安全的
  • 集合元素可以是 null

• HashSet 集合判断两个元素相等的标准：两个对象通过 hashCode() 方法比较相 等，并且两个对象的 equals() 方法返回值也相等。

• 对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

向HashSet中添加元素的过程

添加元素的过程：以HashSet为例：
        我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，
        此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置），判断
        数组此位置上是否已经有元素：
            如果此位置上没有其他元素，则元素a添加成功。 --->情况1
            如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值：
                如果hash值不相同，则元素a添加成功。--->情况2
                如果hash值相同，进而需要调用元素a所在类的equals()方法：
                       equals()返回true,元素a添加失败
                       equals()返回false,则元素a添加成功。--->情况3

# 链表存储方式
对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。
jdk 7 :元素a放到数组中，指向原来的元素。
jdk 8 :原来的元素在数组中，指向元素a
总结：七上八下

# HashSet底层：数组+链表的结构。

LinkedHashSet

• LinkedHashSet 是 HashSet 的子类

• LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置， 但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入 顺序保存的。

• LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。

• LinkedHashSet 不允许集合元素重复。

• 想看源码的话，可以debug一下LinkedHashSet添加一个String对象的过程。

  @Test
  public void test2(){
    Set set = new LinkedHashSet();
    set.add("AA"); // 在这里debug一下。
  }
  

//LinkedHashSet的使用
//LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个
//数据和后一个数据。
//优点：对于频繁的遍历操作，LinkedHashSet效率高于HashSet
@Test
public void test2(){
  Set set = new LinkedHashSet();
  set.add(456);
  set.add(123);
  set.add(123);
  set.add("AA");
  set.add("CC");
  set.add(new User("Tom",12));
  set.add(new User("Tom",12));
  set.add(129);

  Iterator iterator = set.iterator();
  while(iterator.hasNext()){
    System.out.println(iterator.next());
  }
}

TreeSet(了解即可)

• TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。

• TreeSet底层使用红黑树结构存储数据

• 新增的方法如下： (了解)

  Comparator comparator() 
  Object first() 
  Object last() 
  Object lower(Object e) 
  Object higher(Object e) 
  SortedSet subSet(fromElement, toElement) 
  SortedSet headSet(toElement) 
  SortedSet tailSet(fromElement)
  

• TreeSet 两种排序方法：自然排序和定制排序。默认情况下，TreeSet 采用自然排序。

1.向TreeSet中添加的数据，要求是相同类的对象。
2.两种排序方式：自然排序（实现Comparable接口） 和 定制排序（Comparator）
3.自然排序中，比较两个对象是否相同的标准为：compareTo()返回0.不再是equals().
4.定制排序中，比较两个对象是否相同的标准为：compare()返回0.不再是equals().

TreeSet排序

@Test
public void test1(){
  TreeSet set = new TreeSet();

  //失败：不能添加不同类的对象
  //        set.add(123);
  //        set.add(456);
  //        set.add("AA");
  //        set.add(new User("Tom",12));

  //举例一：
  //        set.add(34);
  //        set.add(-34);
  //        set.add(43);
  //        set.add(11);
  //        set.add(8);

  //举例二：
  set.add(new User("Tom",12));
  set.add(new User("Jerry",32));
  set.add(new User("Jim",2));
  set.add(new User("Mike",65));
  set.add(new User("Jack",33));
  set.add(new User("Jack",56));


  Iterator iterator = set.iterator();
  while(iterator.hasNext()){
    System.out.println(iterator.next());
  }

}

@Test
public void test2(){
  Comparator com = new Comparator() {
    //按照年龄从小到大排列
    @Override
    public int compare(Object o1, Object o2) {
      if(o1 instanceof User && o2 instanceof User){
        User u1 = (User)o1;
        User u2 = (User)o2;
        return Integer.compare(u1.getAge(),u2.getAge());
      }else{
        throw new RuntimeException("输入的数据类型不匹配");
      }
    }
  };

  //        TreeSet set1 = new TreeSet();
  TreeSet set = new TreeSet(com);
  set.add(new User("Tom",12));
  set.add(new User("Jerry",32));
  set.add(new User("Jim",2));
  set.add(new User("Mike",65));
  set.add(new User("Mary",33));
  set.add(new User("Jack",33));
  set.add(new User("Jack",56));


  Iterator iterator = set.iterator();
  while(iterator.hasNext()){
    System.out.println(iterator.next());
  }
}

Map接口

Map接口概述

• Map与Collection并列存在。用于保存具有映射关系的数据:key-value
• Map 中的 key 和 value 都可以是任何引用类型的数据
• Map 中的 key 用Set来存放，不允许重复，即同一个 Map 对象所对应 的类，须重写hashCode()和equals()方法
• 常用String类作为Map的“键”
• key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到 唯一的、确定的 value
• Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和 Properties。其中，HashMap是 Map 接口使用频率最高的实现类

一、Map的实现类的结构：
 |----Map:双列数据，存储key-value对的数据   ---类似于高中的函数：y = f(x)
        |----HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
             |----LinkedHashMap:保证在遍历map元素时，可以按照添加的顺序实现遍历。
                     原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
                     对于频繁的遍历操作，此类执行效率高于HashMap。
        |----TreeMap:保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
                     底层使用红黑树
        |----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
             |----Properties:常用来处理配置文件。key和value都是String类型
     HashMap的底层：数组+链表  （jdk7及之前）
                   数组+链表+红黑树 （jdk 8）

Map结构特点

 二、Map结构的理解：
   Map中的key:无序的、不可重复的，使用Set存储所有的key  ---> key所在的类要重写equals()和hashCode() （以HashMap为例）
   Map中的value:无序的、可重复的，使用Collection存储所有的value --->value所在的类要重写equals()
   一个键值对：key-value构成了一个Entry对象。
   Map中的entry:无序的、不可重复的，使用Set存储所有的entry

源码分析

三、HashMap的底层实现原理？以jdk7为例说明：
     HashMap map = new HashMap():
     在实例化以后，底层创建了长度是16的一维数组Entry[] table。
     ...可能已经执行过多次put...
     map.put(key1,value1):
     首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。
     如果此位置上的数据为空，此时的key1-value1添加成功。 ----情况1
     如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据
     的哈希值：
             如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。----情况2
             如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：
                     如果equals()返回false:此时key1-value1添加成功。----情况3
                     如果equals()返回true:使用value1替换value2。
      补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。
     在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。
     jdk8 相较于jdk7在底层实现方面的不同：
     1. new HashMap():底层没有创建一个长度为16的数组
     2. jdk 8底层的数组是：Node[],而非Entry[]
     3. 首次调用put()方法时，底层创建长度为16的数组
     4. jdk7底层结构只有：数组+链表。jdk8中底层结构：数组+链表+红黑树。
        4.1 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
        4.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。
     DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
     DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
     threshold：扩容的临界值，=容量*填充因子：16 * 0.75 => 12
     TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树:8
     MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量:6

JDK7HashMap底层源码分析

HashMap的底层实现原理？以jdk7为例说明：
     HashMap map = new HashMap():
     在实例化以后，底层创建了长度是16的一维数组Entry[] table。
     ...可能已经执行过多次put...
     map.put(key1,value1):
     首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。
     如果此位置上的数据为空，此时的key1-value1添加成功。 ----情况1
     如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值：
             如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。----情况2
             如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：
                     如果equals()返回false:此时key1-value1添加成功。----情况3
                     如果equals()返回true:使用value1替换value2。
      补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。
     在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

public HashMap() {
  // 默认初始化容量 16，0.75f
  this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR);
}

public V put(K key, V value) {
  if (key == null)
    return putForNullKey(value); // 可以存放key 为null 
  int hash = hash(key); // 计算key的hash值
  int i = indexFor(hash, table.length); // 通过hashCode计算出，在Entry[] 中的存放位置
  for (Entry<K,V> e = table[i]; e != null; e = e.next) { //如果数组中这个位置的元素不为null，就取出来做比较；又因为Entry里面的next属性列表的下一个元素是谁，从而实现遍历了数组的这个位置里所有链表的元素。
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 如果当前遍历的链表元素key和新添加的key一样的请款
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  modCount++; 
  addEntry(hash, key, value, i); // 如果当前key，没有重复就执行这个方法。
  return null;

static int indexFor(int h, int length) {
  return h & (length-1); // 默认length是16，length - 1就是15，二进制也就是...0001111，通过&运算保证index在0~length之间。
}

void addEntry(int hash, K key, V value, int bucketIndex) {
  // threshold = capacity * load factor 
  // 如果当前entry[] 数组的长度大于临界值 且 当前Entry[] 索引位置有数据了，即不为空时
  if ((size >= threshold) && (null != table[bucketIndex])) { 
    resize(2 * table.length); // 扩容，扩容成2倍
    hash = (null != key) ? hash(key) : 0; // 重新计算当前key的hash值
    bucketIndex = indexFor(hash, table.length); // 重新计算当前元素要插入的位置。
  }

  // 扩不扩容都会创建一个新的entry
  createEntry(hash, key, value, bucketIndex); 
}

void createEntry(int hash, K key, V value, int bucketIndex) {
  Entry<K,V> e = table[bucketIndex]; 
  // 将当前位置的元素，放到我们新entry的下一个位置
  // 简称七上八下
  table[bucketIndex] = new Entry<>(hash, key, value, e);
  size++;
}

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;
  V value;
  Entry<K,V> next;
  int hash;

  /**
   * Creates new entry.
  */
  Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
  }
}

JDK8HashMap底层源码分析

public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

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

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; // 第一次put，调用resize() 方法初始化数组（长度16），临界值（threshold= 16*0.75 = 12）
  if ((p = tab[i = (n - 1) & hash]) == null) // 插入到数组中的位置是否有元素了
    tab[i] = newNode(hash, key, value, null); // 没有，直接插入
  else {
    Node<K,V> e; K k;
    if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
      e = p; // 如果有，但是hash值相等且地址值一样 或者 （key!=null 且equals一样）
    else if (p instanceof TreeNode) // 如果是红黑树
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else { // 都不是
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) { // 看看当前数组中的元素下一个元素是不是null，是就直接放到下一个
          p.next = newNode(hash, key, value, null);
          if (binCount >= TREEIFY_THRESHOLD - 1) // 当链表长度超过8也就是9个元素的时候（数组位置有一个， 1 + (7-0)+1 = 9），满足条件，进入treeifyBin()方法判断是否改变链表的结构
            treeifyBin(tab, hash);
          break; // 退出
        }
        // 虽然下一个元素不是null 但是和新加入的key的hashcode equals 一样，就替换
        if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
          break;
        // 如果都不满足，循环赋值，实现遍历出这个链表的所有元素
        p = e;
      }
    }
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length; // 第一次put元素的时候满足 oldTab == null
  int oldThr = threshold;
  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)
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  else {               // zero initial threshold signifies using defaults
    // 使用默认值初始化HashMap的容量和临界值
    newCap = DEFAULT_INITIAL_CAPACITY; // 16
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75
  }
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.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;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
  int n, index; Node<K,V> e;
  // 虽然链表长度大于等于8，我们还得判断map的数组长度是否大于64，小于64就进行扩容操作，不改变存储结构
  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    TreeNode<K,V> hd = null, tl = null;
    do {
      TreeNode<K,V> p = replacementTreeNode(e, null);
      if (tl == null)
        hd = p;
      else {
        p.prev = tl;
        tl.next = p;
      }
      tl = p;
    } while ((e = e.next) != null);
    if ((tab[index] = hd) != null)
      hd.treeify(tab);
  }
}

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
  // ....
}

LinkedHashMap(了解即可)

• LinkedHashMap 是 HashMap 的子类
• 在HashMap存储结构的基础上，使用了一对双向链表来记录添加 元素的顺序
• 与LinkedHashSet类似，LinkedHashMap 可以维护 Map 的迭代 顺序：迭代顺序与 Key-Value 对的插入顺序一致

LinkedHashMap的底层实现原理（了解） */
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
// put方法就是HashMap 的put方法，只不过，LinkedHashMap重写了newNode() 方法
  
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  linkNodeLast(p);
  return p;
}
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);
  }
}

Map中常用的方法

总结：常用方法：
添加：put(Object key,Object value)
删除：remove(Object key)
修改：put(Object key,Object value)
查询：get(Object key)
长度：size()
遍历：keySet() / values() / entrySet()

/*
     添加、删除、修改操作：
     Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
     void putAll(Map m):将m中的所有key-value对存放到当前map中
     Object remove(Object key)：移除指定key的key-value对，并返回value
     void clear()：清空当前map中的所有数据
     */
@Test
public void test3(){
  Map map = new HashMap();
  //添加
  map.put("AA",123);
  map.put(45,123);
  map.put("BB",56);
  //修改
  map.put("AA",87);

  System.out.println(map);

  Map map1 = new HashMap();
  map1.put("CC",123);
  map1.put("DD",123);

  map.putAll(map1);

  System.out.println(map);

  //remove(Object key)
  Object value = map.remove("CC");
  System.out.println(value);
  System.out.println(map);

  //clear()
  map.clear();//与map = null操作不同
  System.out.println(map.size());
  System.out.println(map);
}

/*
     元素查询的操作：
     Object get(Object key)：获取指定key对应的value
     boolean containsKey(Object key)：是否包含指定的key
     boolean containsValue(Object value)：是否包含指定的value
     int size()：返回map中key-value对的个数
     boolean isEmpty()：判断当前map是否为空
     boolean equals(Object obj)：判断当前map和参数对象obj是否相等
     */
@Test
public void test4(){
  Map map = new HashMap();
  map.put("AA",123);
  map.put(45,123);
  map.put("BB",56);
  // Object get(Object key)
  System.out.println(map.get(45));
  //containsKey(Object key)
  boolean isExist = map.containsKey("BB");
  System.out.println(isExist);

  isExist = map.containsValue(123);
  System.out.println(isExist);

  map.clear();

  System.out.println(map.isEmpty());

}

/*
 元视图操作的方法：
 Set keySet()：返回所有key构成的Set集合
 Collection values()：返回所有value构成的Collection集合
 Set entrySet()：返回所有key-value对构成的Set集合

     */


@Test
public void test5(){
  Map map = new HashMap();
  map.put("AA",123);
  map.put(45,1234);
  map.put("BB",56);

  //遍历所有的key集：keySet()
  Set set = map.keySet();
  Iterator iterator = set.iterator();
  while(iterator.hasNext()){
    System.out.println(iterator.next());
  }
  System.out.println();
  //遍历所有的value集：values()
  Collection values = map.values();
  for(Object obj : values){
    System.out.println(obj);
  }
  System.out.println();
  //遍历所有的key-value
  //方式一：entrySet()
  Set entrySet = map.entrySet();
  Iterator iterator1 = entrySet.iterator();
  while (iterator1.hasNext()){
    Object obj = iterator1.next();
    //entrySet集合中的元素都是entry
    Map.Entry entry = (Map.Entry) obj;
    System.out.println(entry.getKey() + "---->" + entry.getValue());

  }
  System.out.println();
  //方式二：
  Set keySet = map.keySet();
  Iterator iterator2 = keySet.iterator();
  while(iterator2.hasNext()){
    Object key = iterator2.next();
    Object value = map.get(key);
    System.out.println(key + "=====" + value);

  }

}

TreeMap

• TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。 TreeMap 可以保证所有的 Key-Value 对处于有序状态。

• TreeSet底层使用红黑树结构存储数据

• TreeMap 的 Key 的排序：

  • 自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有 的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException
  • 定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口

• TreeMap判断两个key相等的标准：两个key通过compareTo()方法或 者compare()方法返回0。

• 向TreeMap中添加key-value，要求key必须是由同一个类创建的对象

• 因为要按照key进行

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

@Test
    public void test1(){
        TreeMap map = new TreeMap();
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",32);
        User u3 = new User("Jack",20);
        User u4 = new User("Rose",18);

        map.put(u1,98);
        map.put(u2,89);
        map.put(u3,76);
        map.put(u4,100);

        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "---->" + entry.getValue());

        }
    }

    //定制排序
    @Test
    public void test2(){
        TreeMap map = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof User && o2 instanceof User){
                    User u1 = (User)o1;
                    User u2 = (User)o2;
                    return Integer.compare(u1.getAge(),u2.getAge());
                }
                throw new RuntimeException("输入的类型不匹配！");
            }
        });
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",32);
        User u3 = new User("Jack",20);
        User u4 = new User("Rose",18);

        map.put(u1,98);
        map.put(u2,89);
        map.put(u3,76);
        map.put(u4,100);

        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "---->" + entry.getValue());

        }
    }

HashTable

• Hashtable是个古老的 Map 实现类，JDK1.0就提供了。不同于HashMap， Hashtable是线程安全的。
• Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询 速度快，很多情况下可以互用。
• 与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value 与HashMap一样，Hashtable 也不能保证其中 Key-Value 对的顺序
• Hashtable判断两个key相等、两个value相等的标准，与HashMap一致。

Properties

• Properties 类是 Hashtable 的子类，该对象用于处理属性文件
• 由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型
• 存取数据时，建议使用setProperty(String key,String value)方法和 getProperty(String key)方法

public class PropertiesTest {

  //Properties:常用来处理配置文件。key和value都是String类型
  public static void main(String[] args)  {
    FileInputStream fis = null;
    try {
      Properties pros = new Properties();

      fis = new FileInputStream("jdbc.properties");
      pros.load(fis);//加载流对应的文件

      String name = pros.getProperty("name");
      String password = pros.getProperty("password");

      System.out.println("name = " + name + ", password = " + password);
    } catch (IOException e) {
      e.printStackTrace();
    } finally {
      if(fis != null){
        try {
          fis.close();
        } catch (IOException e) {
          e.printStackTrace();
        }

      }
    }

  }
}

Collections工具类

• Collections:操作Collection、Map的工具类

reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection，Comparator)
int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
void copy(List dest,List src)：将src中的内容复制到dest中
boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值

测试API

@Test
public void test1(){
  List list = new ArrayList();
  list.add(123);
  list.add(43);
  list.add(765);
  list.add(765);
  list.add(765);
  list.add(-97);
  list.add(0);

  System.out.println(list);

  //        Collections.reverse(list);
  //        Collections.shuffle(list);
  //        Collections.sort(list);
  //        Collections.swap(list,1,2);
  int frequency = Collections.frequency(list, 123);

  System.out.println(list);
  System.out.println(frequency);

}

同步控制

@Test
public void test2(){
  List list = new ArrayList();
  list.add(123);
  list.add(43);
  list.add(765);
  list.add(-97);
  list.add(0);

  //报异常：IndexOutOfBoundsException("Source does not fit in dest")
  //        List dest = new ArrayList();
  //        Collections.copy(dest,list);
  //正确的：
  List dest = Arrays.asList(new Object[list.size()]);
  System.out.println(dest.size());//list.size();
  Collections.copy(dest,list);

  System.out.println(dest);


  /*
        Collections 类中提供了多个 synchronizedXxx() 方法，
        该方法可使将指定集合包装成线程同步的集合，从而可以解决
        多线程并发访问集合时的线程安全问题

         */
  //返回的list1即为线程安全的List
  List list1 = Collections.synchronizedList(list);


}

面试题

foreach 和 for

   //练习题
    @Test
    public void test3(){

        String[] arr = new String[]{"MM","MM","MM"};

//        //方式一：普通for赋值
//        for(int i = 0;i < arr.length;i++){
//            arr[i] = "GG"; // 输出是GG
//        }

        //方式二：增强for循环
        for(String s : arr){
            s = "GG"; // 输出是MM
        }

        for(int i = 0;i < arr.length;i++){
            System.out.println(arr[i]);
        }


    }

ArrayList、LinkedList、Vector三者的异同？

public class ListExer {
    /*
    区分List中remove(int index)和remove(Object obj)
     */
    @Test
    public void testListRemove() {
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        updateList(list);
        System.out.println(list);//
    }

    private void updateList(List list) {
//        list.remove(2);
        list.remove(new Integer(2));
    }

}

@Test
public void test3() {
  HashSet set = new HashSet();

  Person p1 = new Person(1001, "AA");

  Person p2 = new Person(1002, "BB");

  set.add(p1);
  set.add(p2);

  p1.name = "CC";

  set.remove(p1); // bb、cc 。存的时候根据1001,AA计算的hashCode然后确定在数组中的位置，现在改成1001，CC计算的hashCode然后得出的数组位置可能不一样。所以删除失败
  System.out.println(set);

  set.add(new Person(1001, "CC")); // bb cc cc

  System.out.println(set);
  set.add(new Person(1001,"AA")); // bb cc cc aa
  System.out.println(set);
}

// 在List内去除重复数字值，要求尽量简单
public static List duplicateList(List list) {
  HashSet set = new HashSet();
  set.addAll(list);
  return new ArrayList(set);
}

public static void main(String[] args) {
  List list = new ArrayList();
  list.add(new Integer(1));
  list.add(new Integer(2));
  list.add(new Integer(2));
  list.add(new Integer(4));
  list.add(new Integer(4));
  List list2 = duplicateList(list);
  for (Object integer : list2) {
    System.out.println(integer);
  }

}

Map主要实现类

|----Map:双列数据，存储key-value对的数据   ---类似于高中的函数：y = f(x)
        |----HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
             |----LinkedHashMap:保证在遍历map元素时，可以按照添加的顺序实现遍历。
                     原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
                     对于频繁的遍历操作，此类执行效率高于HashMap。
        |----TreeMap:保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
                     底层使用红黑树
        |----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
             |----Properties:常用来处理配置文件。key和value都是String类型
     HashMap的底层：数组+链表  （jdk7及之前）
                   数组+链表+红黑树 （jdk 8）

谈谈你对HashMap中put/get方法的认识？如果了解再谈谈 HashMap的扩容机制？默认大小是多少？什么是负载因子( 或填充比)？什么是吞吐临界值(或阈值、threshold)？

负载因子值的大小，对HashMap有什么影响

• 负载因子的大小决定了HashMap的数据密度。
• 负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长, 造成查询或插入时的比较次数增多，性能会下降。
• 负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的 几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性 能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建 议初始化预设大一点的空间。
• 按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此 时平均检索长度接近于常数。