集合框架

一、框架

在程序中，将一些功能进行封装，提供给其他人使用的功能叫做框架。其作用是用来简化开发过程以及代码。

二、集合

实现了类似于数组的功能，将多个对象进行操作的方法进行了定义和封装，在开发时只需要调用即可，简化了数组的使用过程。

与数组的区别：

  • 数组长度固定，集合长度不固定。
  • 数组可以存储基本数据类型和引用数据类型，而集合只能存储引用数据类型。

注意：如果在集合中存储基本数据类型，会自动转换成包装类。

三、集合框架的体系

集合框架常用的主要有两个体系：Collection和Map

3.1 Collection体系

Collection作为整个体系的父接口，能够存储多种类型的对象，特点是无序、无下标、可以迭代（循环）每个元素。其有两个常用的子接口。

  • List，该接口增加下标功能，特点是有序，有下标，且元素可以重复。常用实现类如下：

    • ArrayList，底层使用数组实现
    • LinkedList，底层使用链表实现

  • Set，该接口特点是无序，无下标，且元素不能重复。

    • HashSet，特点是使用HashMap的key来实现。
    • TreeSet，特点是使用tree实现，所以可以排序。

3.2 collection体系常用方法

add：添加对象

addAll：将另一个集合中的所有对象添加到当前集合中

clear：清空集合中所有的对象

contains：判断集合中是否包含某个对象

isEmpty：判断集合是否为空

remove：删除一个对象

size：得到集合中元素的个数

toArray：将集合转换成数组

四、List接口相关

4.1 基本特点

List接口继承自Collection接口，特点是：有序、有下标、元素可以重复，相对于Collection接口，添加一些与下标相关的方法。

add(index, obj)：向指定下标添加元素。

get(index)：获得指定下标的元素。

4.2 有序、无序、排序

有序是指会按照元素添加时的顺序存放。

无序是指添加元素的顺序与最终存放的顺序无关，顺序与用户的理解也无关。

排序是指可以根据程序员要求的特点来进行排序。

4.3 常用实现类

ArrayList（Vector）、LinkedList

Vector与ArrayList具备有几乎相同的结构以及完全相同的用法，区别在于ArrayList不安全，Vector是线程安全的，但是性能非常低下，几乎不会被使用，后面会有其他的性能相对较高的安全的集合来代替。

4.4 数组和链表

  • 数组的特点：连续空间、长度固定。增删慢，遍历速度快。

  • 链表的特点：随机空间、长度不固定。增删快，遍历较慢。

    • 链表如果操作首尾，比操作中间更快
    • 链表有单向和双向之分，单向表示只能向一个方向遍历，双向可以向两边遍历。

4.5 ArrayList的用法

  1. public class TestMain1 {
  2.     // ArrayList用法
  3.     // 使用数组原理实现的集合
  4.     public static void main(String[] args) {
  5.         // 创建一个集合
  6.         ArrayList list = new ArrayList();
  7.         // 添加元素
  8.         list.add("a");
  9.         list.add("b");
  10.         list.add("c");
  11.         list.add("d");
  12.         list.add("e");
  13.         // 通过下标获取元素
  14.         System.out.println(list.get(2));
  15.         // 通过下标遍历
  16.         // size方法获得集合中元素的个数
  17.         for (int i = 0; i < list.size(); i++) {
  18.             System.out.println(list.get(i));
  19.         }
  20.         // 通过foreach遍历
  21.         for (Object object : list) {
  22.             String temp = (String)object;
  23.             System.out.println(temp);
  24.         }
  25.         // 使用迭代器循环
  26.         Iterator it = list.iterator(); // 得到集合中的迭代器
  27.         while(it.hasNext()) { // 如果有下一个
  28.             String str = (String)it.next(); // 获取下一个
  29.             System.out.println(str);
  30.         }
  31.         // 删除
  32.         list.remove(1);// 通过下标删除
  33.         list.remove("e"); // 直接删除元素
  34.         Object [] arr = list.toArray(); // 将集合转换成数组
  35.     }
  36. }

注意：Vector与ArrayList用法完全相同。

4.6 LinkedList的基本用法

  1. public class TestMain2 {
  2.     // LinkedList用法
  3.     // 使用数组原理实现的集合
  4.     public static void main(String[] args) {
  5.         // 创建一个集合
  6.         LinkedList list = new LinkedList();
  7.         // 添加元素
  8.         list.add("a");
  9.         list.add("b");
  10.         list.add("c");
  11.         list.add("d");
  12.         list.add("e");
  13.         // 通过下标获取元素
  14.         System.out.println(list.get(2));
  15.         // 通过下标遍历
  16.         // size方法获得集合中元素的个数
  17.         for (int i = 0; i < list.size(); i++) {
  18.             System.out.println(list.get(i));
  19.         }
  20.         // 通过foreach遍历
  21.         for (Object object : list) {
  22.             String temp = (String)object;
  23.             System.out.println(temp);
  24.         }
  25.         // 使用迭代器循环
  26.         Iterator it = list.iterator(); // 得到集合中的迭代器
  27.         while(it.hasNext()) { // 如果有下一个
  28.             String str = (String)it.next(); // 获取下一个
  29.             System.out.println(str);
  30.         }
  31.         // 删除
  32.         list.remove(1);// 通过下标删除
  33.         list.remove("e"); // 直接删除元素
  34.         Object [] arr = list.toArray(); // 将集合转换成数组
  36.         // 除了上面的通用用法以外，还有一些链表特有的用法
  37.         list.addFirst("1"); // 在链表最前面添加
  38.         list.addLast("2"); // 在链表最后面添加
  39.         list.removeFirst(); // 删除最前面的元素
  40.         list.removeLast(); // 删除最后面的元素
  41.     }
  42. }

4.7 ArrayList底层实现

1、当创建一个无参的对象时，默认数据为一个空数组。长度为0

2、当创建的无参对象（空数组）第一次添加元素时，会将长度指定为10，添加元素时，会进行一次扩容。

3、如果元素的个数没有超过数组的空间时，不会扩容。如果添加的下一个元素时超过了数组空间大小时，会进行扩容。注：说明扩容的临界点是当数组元素已满时进行。

4、当进行扩容时，会扩容为原来大小的1.5倍。如果扩容1.5倍时超出了范围，扩容1个空间，保障至少能添加元素。

5、当新的空间大小超出MAX_ARRAY_SIZE时，指定为Integer.MAX_VALUE，如果超过了Integer.MAX_VALUE时，则报错。

  1. // 默认大小
  2. private static final int DEFAULT_CAPACITY = 10;
  3. // 存储数据的
  4. Object[] elementData;
  5. // 当前数组中元素的数量
  6. private int size;
  8. // 无参构造方法
  9. public ArrayList() {
  10.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  11. }
  13. // 通过指定长度来创建集合
  14. public ArrayList(int initialCapacity) {
  15.     if (initialCapacity > 0) {
  16.         // 通过指定长度来创建数组
  17.         this.elementData = new Object[initialCapacity];
  18.         // 如果长度等于0，就直接赋值为一个空数组
  19.     } else if (initialCapacity == 0) {
  20.         this.elementData = EMPTY_ELEMENTDATA;
  21.     } else {
  22.         // 如果是负数就报错
  23.         throw new IllegalArgumentException("Illegal Capacity: "+
  24.                                            initialCapacity);
  25.     }
  26. }
  28. // 添加元素
  29. public boolean add(E e) {
  30.     ensureCapacityInternal(size + 1);  // Increments modCount!!
  31.     //将新添加的元素赋值到数组中，并size加1
  32.     elementData[size++] = e;
  33.     return true;
  34. }
  36. // 判断是否空数组，根据数组情况来设置最小需要的长度
  37. private void ensureCapacityInternal(int minCapacity) {
  38.     // 当通过无参构造方法创建对象时，默认为空数组时
  39.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  40.         // 将数组大小设置为10
  41.         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  42.     }
  44.     ensureExplicitCapacity(minCapacity);
  45. }
  47. private void ensureExplicitCapacity(int minCapacity) {
  48.     modCount++; 
  50.     // overflow-conscious code
  51.     // 当数组元素已经达到数组所容纳的元素上限时
  52.     if (minCapacity - elementData.length > 0)
  53.         // 扩容
  54.         grow(minCapacity);
  55. }
  57. // 扩容
  58. private void grow(int minCapacity) {
  59.     // overflow-conscious code
  60.     // 旧的空间大小，原来数组的长度
  61.     int oldCapacity = elementData.length;
  62.     // 新的空间大小，原来数组大小的1.5倍
  63.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  64.     // 当新的空间-需要的最小空间（size+1）小于0时，新空间直接赋值为最小空间（size+1）
  65.     if (newCapacity - minCapacity < 0)
  66.         newCapacity = minCapacity;
  67.     // 当新的空间如果大于2147483639时
  68.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  69.         // 指定新的空间为巨大的空间
  70.         newCapacity = hugeCapacity(minCapacity);
  71.     // minCapacity is usually close to size, so this is a win:
  72.     // 创建一个新的大小的数组，并将原来的数据复制到新数组中
  73.     elementData = Arrays.copyOf(elementData, newCapacity);
  74. }
  76. private static int hugeCapacity(int minCapacity) {
  77.     // 保障的最小空间都超出了范围，此时直接报错
  78.     if (minCapacity < 0) // overflow
  79.         throw new OutOfMemoryError();
  80.     // 如果需要保障的最小空间超过2147483639，直接指定大小为最大值（2147483647），否则指定为最大数组大小
  81.     return (minCapacity > MAX_ARRAY_SIZE) ?
  82.         Integer.MAX_VALUE :
  83.     MAX_ARRAY_SIZE;
  84. }

4.8LinkedList的原理

1、LinkedList是一个双向链表。

2、内置一个Node节点类，来进行链接。

3、会保存链表的首尾节点。

4、当添加元素时，会将元素保存为一个节点（Node），并设置节点相应的前后节点，以及根据情况修改LinkedList首尾节点。

  1. // LinkedList的内部类，用来保存一个节点
  2. private static class Node<E> {
  3.     E item; // 元素
  4.     Node<E> next; // 下一个节点
  5.     Node<E> prev; // 上一个节点
  7.     // 有参构造方法，每次创建对象时必须指定上一个节点，当前元素，下一个节点
  8.     Node(Node<E> prev, E element, Node<E> next) {
  9.         this.item = element;
  10.         this.next = next;
  11.         this.prev = prev;
  12.     }
  13. }
  15. transient Node<E> first; // 第一个节点
  16. transient Node<E> last; // 最后一个节点
  18. // 无参构造方法
  19. public LinkedList() {
  20. }
  22. // 添加，默认在尾部添加
  23. public boolean add(E e) {
  24.     linkLast(e);
  25.     return true;
  26. }
  28. // 在尾部添加
  29. public void addLast(E e) {
  30.     linkLast(e);
  31. }
  33. // 
  34. void linkLast(E e) {
  35.     // 记住最后一个节点
  36.     final Node<E> l = last;
  37.     // 创建一个新的节点，将上一个节点指定为原来的最后一个节点，下一个节点指定为null
  38.     final Node<E> newNode = new Node<>(l, e, null);
  39.     // 将自己指定为当前LinkedList的尾部（最后一个节点）
  40.     last = newNode;
  41.     // 如果上一个节点为空，则将当前节点也设为第一个节点（首部）
  42.     if (l == null)
  43.         first = newNode;
  44.     else
  45.         // 如果上一个节点不为空，则将原来的最后一个节点的下一个节点指定为当前节点
  46.         l.next = newNode;
  47.     size++;
  48.     modCount++;
  49. }

五、泛型以及集合

5.1 泛型

泛型是对类型的一种约束。作用是在使用时会自动转成相应的类型，还会对不是该类型的地方进行检查，会有相应的编译错误提示。

5.2 泛型集合

在集合创建时使用泛型（推荐使用），会在向集合中添加元素时对元素进行检查， 如果类型不一致会出现编译错误的提示，在访问时（获取）会自动转型，避免强制转换的麻烦。

5.3 泛型的语法

泛型分为类泛型和方法泛型。

  • 类泛型

    • 在类定义时使用泛型（可以使用多个），类中的任意位置都可以使用该定义的泛型
  1. // T是一个可变化的类型，用户在使用时传入的是什么类型，就会变化成什么类型
  2. // 如果用户没有传入，则就是Object类型
  3. // 在当前类中，只能当为Object使用，因为不确定用户会传入什么类型
  4. // T也可以使用任意字母代替
  5. // 多个类型之间可以使用逗号隔开
  6. public class MyClass <T, P>{ 
  7.     public T test(T obj) {
  8.         T t;
  9.         return null;
  10.     }
  12.     public T test1(T obj1, P obj2) {
  13.         return null;
  14.     }
  15. }
  17. public class TestMain1 {
  18.     public static void main(String[] args) {
  19.         MyClass<String, Integer> c = new MyClass<String, Integer>();
  20.         String str = c.test("2");
  21.         String str1 = c.test1("2", 3);
  22.     }
  23. }

  • 方法泛型

    • 是指在类上面不定义泛型，但是在方法中定义并使用泛型
  1. public class MyClass1 { 
  2.     // 在方法上定义并使用泛型
  3.     public <T> T test(T obj) {
  4.         T t;
  5.         return null;
  6.     }
  8.     // 在方法中定义的泛型，在其他方法中不能使用
  9. //    public T test1() {
  10. //        
  11. //    }
  12. }
  14. public class TestMain1 {
  15.     public static void main(String[] args) {
  16.         MyClass1 c1 = new MyClass1();
  17.         // 由于在方法中定义了泛型，且要求传入参数与返回值类型一致，所以也可以不需要强制转换，会自动检查类型
  18.         Date str2 = c1.test(new Date());
  19.     }
  20. }

经典面试题：

为什么说Java中的泛型是伪（假）泛型？

1、Java中的泛型仅对传入的参数进行编译检查，不会真的对参数进行处理。

2、Java中的泛型仅对对象使用时进行强制转换，不会真的对对象进行转型处理。

3、在对象真正使用的过程中，仍旧是Object类型。

5.4 泛型中的super和extends

当作为参数时，传入的参数根据extends和super的不同，可以传入更宽泛的类型。

? extends B 表示可以传入B类或者B类的子类 ，称为上界限定符

? super B 表示可以传入B类或者B类的父类，称为下界限定符

在使用时，上界不存，下界不取

使用上界时，该集合不能存储数据，可以取值

使用下界时，集合不能取值，但是可以存储数据

  1. public class TestMain2 {
  2.     public static void main(String[] args) {
  3.         ArrayList<B> list = new ArrayList<B>();
  4.         addAll(list);
  5.     }
  7.     // ? extends B 表示B类或者B类的子类  上界限定符
  8.     // ? super B 表示B类或者B类的父类  下界限定符
  9.     // 相对于直接写B类，类型会宽泛一些
  10.     // 上界不存，下界不取
  11.     // 使用上界时，集合不能存储数据，可以取值
  12.     // 使用下界时，集合不能取值，但是可以存储数据
  13.     public static void addAll(ArrayList<? super B> c) {
  14.         // 添加元素（存）
  15. //        c.add(new B());
  16.         // 循环（取）
  17. //        for (B b : c) {
  18. //            System.out.println(b);
  19. //        }
  20.     }
  21. }

六、Collections工具类

Collections针对于集合的帮助类，相当于Arrays是针对于数组的帮助类。

主要是对集合的排序、打乱、截取等操作。

  1. public class TestMain3 {
  2.     public static void main(String[] args) {
  3.         // sort
  4.         ArrayList<Integer> list = new ArrayList<>();
  5.         list.add(23);
  6.         list.add(35);
  7.         list.add(12);
  8.         list.add(8);
  9.         list.add(10);
  10.         list.add(45);
  11.         list.add(14);
  12.         Collections.sort(list); // 对集合进行排序
  13.         System.out.println(list);
  14.         Collections.reverse(list); // 对集合进行反转
  15.         System.out.println(list);
  16.         Collections.shuffle(list);// 随机打乱一个集合
  17.         System.out.println(list);
  19.         // 如果已知元素，可以使用asList方法将其转换成集合，但是不能强转成ArrayList，因为它是List接口 
  20.         // 一般用作循环使用
  21.         List<Integer> list1 =  Arrays.asList(23, 35, 12, 8, 10, 45, 14);
  22.         System.out.println(list1);
  23.         Collections.sort(list1); // 对集合进行排序
  24.         System.out.println(list1);
  25.         Collections.reverse(list1); // 对集合进行反转
  26.         System.out.println(list1);
  27.         Collections.shuffle(list1);// 随机打乱一个集合
  28.         System.out.println(list1);
  29.     }
  30. }

面试题：

Collection与Collections的区别：

Collection是List和Set的父接口，无序，无下标。

Collections是一个集合的帮助类。提供一系列的静态方法对集合进行操作。

七、Set集合

无序、无下标，元素不能重复。

7.1 HashSet

通过hashCode实现元素不可重复。

当存入的元素hashCode相同时，会使用equals方法来判断是否相同元素，如果不相同，则可以存入。

注意：

HashSet判断不同对象的步骤是：

1、先判断hashCode是否相同，如果不同，直接认定是不同对象，如果相同，进行第二步。

2、判断equals是否相同，如果不同，才认定是不同对象，如果相同，认定为相同对象，会直接放弃添加。

所以，在使用Hashset时，如果要存入实体类的对象，一定要对该实体类进行重写equals和hashCode方法。

注意：HashSet底层使用的HashMap，创建HashSet时会创建一个HashMap，每次添加元素时，就是向HashMap的key上面进行添加。

  1. public class TestMain {
  2.     public static void main(String[] args) {
  3.         ArrayList<String> list = new ArrayList<>();
  4.         // 六个都会存入
  5.         list.add("c");
  6.         list.add("b");
  7.         list.add("a");
  8.         list.add("a");
  9.         list.add("b");
  10.         list.add("c");
  11.         System.out.println(list);
  13.         HashSet<String> set = new HashSet<String>();
  14.         // 只存入了A、B、C
  15.         set.add("B");
  16.         set.add("C");
  17.         set.add("A");
  18.         set.add("B");
  19.         set.add("C");
  20.         set.add("A");
  21.         System.out.println(set);
  22.     }
  23. }
  25. public class Student {
  26.     private String name;
  28.     public Student(String name) {
  29.         super();
  30.         this.name = name;
  31.     }
  33.     @Override
  34.     public String toString() {
  35.         return "Student [name=" + name + "]";
  36.     }
  37.     // 如果hashCode和equals都相同，无论是否同一个对象，都会认定为同一个，不会存入
  38.     @Override
  39.     public int hashCode() {
  40.         return 1;
  41.     }
  43.     @Override
  44.     public boolean equals(Object obj) {
  45.         return true;
  46.     }
  47. }
  49. public class TestMain1 {
  50.     public static void main(String[] args) {
  51.         HashSet<Student> set = new HashSet<Student>();
  52.         // 当hashCode和equals都认定相同时，只会存入张三
  53.         set.add(new Student("张三"));
  54.         set.add(new Student("李四"));
  55.         System.out.println(set);
  56.     }
  57. }

7.2 LinkedHashSet

LinkedHashSet继承自HashSet。

HashSet一般情况下使用HashMap作为底层，而LinkedHashSet使用的LinkedHashMap作为底层，在HashMap的基础上添加了链表的结构，来保存了添加的顺序。

  1. public class TestMain2 {
  2.     public static void main(String[] args) {
  3.         LinkedHashSet<String> set = new LinkedHashSet<>();
  4.         set.add("B");
  5.         set.add("C");
  6.         set.add("A");
  7.         // 输出结果为：B-->C-->A
  8.         for (String string : set) {
  9.             System.out.println(string);
  10.         }
  11.     }
  12. }

7.3 TreeSet

实现了SortedSet接口，自动排序，根据自定的方式（基于Comparable接口）排序。

注意：使用TreeSet来存储元素时一定要指定排序的方式，否则会报错。

二叉树：

一个节点，最多只能有两个直接的子节点。

TreeSet进行排序的规则要求实现Comparable接口，如果是自定义的类，要将对象放入到TreeSet中，必须实现该接口，否则会出现ClassCastException。

  1. public class Student implements Comparable<Student>{
  2.     private String name;
  3.     private int age;
  5.     public Student(String name) {
  6.         super();
  7.         this.name = name;
  8.     }
  10.     public Student(String name, int age) {
  11.         super();
  12.         this.name = name;
  13.         this.age = age;
  14.     }
  17.     @Override
  18.     public String toString() {
  19.         return "Student [name=" + name + ", age=" + age + "]";
  20.     }
  22.     // 如果hashCode和equals都相同，无论是否同一个对象，都会认定为同一个，不会存入
  23.     @Override
  24.     public int hashCode() {
  25.         return 1;
  26.     }
  28.     @Override
  29.     public boolean equals(Object obj) {
  30.         return true;
  31.     }
  33.     @Override
  34.     public int compareTo(Student o) {
  35. //        if(this.age - o.age < 0) {
  36. //            return -1;
  37. //        }else if(this.age - o.age > 0) {
  38. //            return 1;
  39. //        }
  40. //        return 0;
  41.         return this.age - o.age;
  42.     }
  43. }
  1. public class TestMain3 {
  2.     public static void main(String[] args) {
  3.         TreeSet<Integer> set = new TreeSet<Integer>();
  4.         set.add(20);
  5.         set.add(15);
  6.         set.add(30);
  7.         set.add(18);
  8.         set.add(12);
  9.         set.add(14);
  10.         set.add(10);
  11.         set.add(30); // 与前面添加的30相等，放弃添加，保证元素不重复
  12.         System.out.println(set);
  14.         // 要使用TreeSet来添加自定义类的对象，需要实现比较接口
  15.         TreeSet<Student> set1 = new TreeSet<Student>();
  16.         set1.add(new Student("张三", 20));
  17.         set1.add(new Student("李四", 18));
  18.         set1.add(new Student("王五", 19));
  19.         set1.add(new Student("赵六", 22));
  20.         System.out.println(set1);
  21.     }
  22. }

上面使用的Collections.sort方法进行排序时，如果是自定义对象，也需要实现Comparable接口。

  1. public class TestMain3 {
  2.     public static void main(String[] args) {    
  3.         ArrayList<Student> list = new ArrayList<Student>();
  4.         list.add(new Student("张三", 20));
  5.         list.add(new Student("李四", 18));
  6.         list.add(new Student("王五", 19));
  7.         list.add(new Student("赵六", 22));
  8.         Collections.sort(list);
  9.         System.out.println(list);
  10.     }
  11. }

注意：Comparable接口中的compareTo方法，返回负数会放到树的左边，正数放到树的右边，返回0表示元素相等，会放弃添加。

八、Map体系

8.1 Map结构

Map是一个顶层接口，常用的实现类有HashMap、TreeMap等。

Map结构特点是：使用键值（key，value）对来存放数据。key键要求不能重复，value值可以重复。

  1. // 常用方法：
  2. put(Object key, Object value); // 添加
  3. Object get(Object key); // 获取元素
  4. Set keySet(); // 返回所有的键集
  5. Collection values(); // 返回所有的值

注意：map存取元素时，需要使用key来访问，key可以是任意类型，但是推荐使用字符串。当使用相同的key存放时，会覆盖原来的内容。

8.2 HashMap基本使用

  1. public class TestMain {
  2.     // HashMap的用法
  3.     public static void main(String[] args) {
  4.         // 创建对象
  5.         HashMap<String, Student> map = new HashMap<String, Student>();
  6.         // 添加元素
  7.         map.put("a", new Student("1", "张三", 20));
  8.         map.put("b", new Student("2", "李四", 21));
  9.         map.put("c", new Student("3", "王五", 22));
  10.         // 获取元素
  11.         Student stu = map.get("b");
  12.         System.out.println(stu);
  13.         // 遍历元素
  14.         // 1、借助遍历key来遍历值
  15.         // 得到keys键集
  16.         Set<String> set = map.keySet();
  17.         for (String key : set) {
  18.             System.out.println("key为：" + key + "，对应的值为：" + map.get(key));
  19.         }
  20.         // 2、直接获取值集合
  21.         Collection<Student> colls = map.values();
  22.         for (Student student : colls) {
  23.             System.out.println("值为：" + student);
  24.         }
  25.         // 3、在遍历时获得键值
  26.         Set<Map.Entry<String, Student>> entrySet = map.entrySet();
  27.         for (Map.Entry<String, Student> entry : entrySet) {
  28.             System.out.println("key为：" + entry.getKey() + "，对应的值为：" + entry.getValue());
  29.         }
  30.         // 删除元素
  31.         map.remove("a");
  32.         int size = map.size(); // 得到元素个数
  33.         System.out.println(size);
  34.     }
  35. }

经典面试题：

HashMap与Hashtable的区别：（相同点：使用方法基本一样）

1、HashMap性能较高，但是线程不安全，Hashtable线程安全，性能极低，基本不使用。

2、HashMap键和值都可以为null，但是键不能重复，会覆盖。Hashtable键和值都不能为null。

8.3 HashMap的底层原理

既有比较快的查找性能，又有较好的增删性能。

采用数组+链表+红黑树（JDK1.8后）的结构。

1、创建HashMap时，指定了扩容因子为0.75

2、在第一次添加元素时，才会创建数组，大小为16，设置临界点12

3、添加元素时，如果key相同，会覆盖值，会根据key的hash计算，并与数组的长度求模，得到该元素存放的下标，如果该下标上有元素，就直接放到链表最后一个元素，如果此时链表数量大于等于7，变化为红黑树。

注意：红黑树的变化条件有两个：1、元素总数量大于64，2、链表上的元素大于等于7

4、当元素添加到临界点时，再添加元素时，会进行扩容，扩容为原来的2倍，临界点重新设置为数组大小*0.75

5、当扩容时，数组大小大于2^30，则指定int的最大值。

  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始大小
  2. static final int MAXIMUM_CAPACITY = 1 << 30; // 最大空间2^30
  3. static final float DEFAULT_LOAD_FACTOR = 0.75f; // 扩容因子
  4. static final int TREEIFY_THRESHOLD = 8; // 变成树的临界值
  5. static final int UNTREEIFY_THRESHOLD = 6; // 变成链表的临界值
  6. static final int MIN_TREEIFY_CAPACITY = 64; // 变成的最小大小
  8. // map中的链表结构（单向链表）
  9. static class Node<K,V> implements Map.Entry<K,V> {
  10.     final int hash; // 哈希值
  11.     final K key;
  12.     V value;
  13.     Node<K,V> next;
  15.     Node(int hash, K key, V value, Node<K,V> next) {
  16.         this.hash = hash;
  17.         this.key = key;
  18.         this.value = value;
  19.         this.next = next;
  20.     }
  22.     public final K getKey()        { return key; }
  23.     public final V getValue()      { return value; }
  24.     public final String toString() { return key + "=" + value; }
  26.     public final int hashCode() {
  27.         return Objects.hashCode(key) ^ Objects.hashCode(value);
  28.     }
  30.     public final V setValue(V newValue) {
  31.         V oldValue = value;
  32.         value = newValue;
  33.         return oldValue;
  34.     }
  36.     public final boolean equals(Object o) {
  37.         if (o == this)
  38.             return true;
  39.         if (o instanceof Map.Entry) {
  40.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  41.             if (Objects.equals(key, e.getKey()) &&
  42.                 Objects.equals(value, e.getValue()))
  43.                 return true;
  44.         }
  45.         return false;
  46.     }
  47. }
  49. transient Node<K,V>[] table; // map中存放数据的数组，每个元素都是一个链表
  51. // hash计算
  52. static final int hash(Object key) {
  53.     int h;
  54.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  55. }
  57. // 无参构造
  58. public HashMap() {
  59.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  60. }
  62. public V put(K key, V value) {
  63.     return putVal(hash(key), key, value, false, true);
  64. }
  66. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  67.                    boolean evict) {
  68.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  69.     // 如果是第一次添加元素（table为null），或者table中的元素数量为0
  70.     if ((tab = table) == null || (n = tab.length) == 0)
  71.         // 设置n为16
  72.         n = (tab = resize()).length;
  73.     // hash值求模运算，如果原来的数组的首元素为空，直接赋值
  74.     if ((p = tab[i = (n - 1) & hash]) == null)
  75.         tab[i] = newNode(hash, key, value, null);
  76.     else {
  77.         Node<K,V> e; K k;
  78.         // 如果首元素不为空，则判断key的hash与equals是否相同
  79.         if (p.hash == hash &&
  80.             ((k = p.key) == key || (key != null && key.equals(k))))
  81.             // 相同则覆盖元素
  82.             e = p;
  83.         // 如果不同，并且为树形结构
  84.         else if (p instanceof TreeNode)
  85.             // 向树型结构中添加元素
  86.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  87.         else {
  88.             // 向链表中添加元素
  89.             for (int binCount = 0; ; ++binCount) {
  90.                 if ((e = p.next) == null) {
  91.                     p.next = newNode(hash, key, value, null);
  92.                     // 如果当前桶上元素数量大于等于7，转成红黑树
  93.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  94.                         treeifyBin(tab, hash);
  95.                     break;
  96.                 }
  97.                 // key相同则停止循环
  98.                 if (e.hash == hash &&
  99.                     ((k = e.key) == key || (key != null && key.equals(k))))
  100.                     break;
  101.                 p = e;
  102.             }
  103.         }
  104.         // 
  105.         if (e != null) { // existing mapping for key
  106.             V oldValue = e.value;
  107.             if (!onlyIfAbsent || oldValue == null)
  108.                 e.value = value;
  109.             afterNodeAccess(e);
  110.             return oldValue;
  111.         }
  112.     }
  113.     ++modCount;
  114.     // 如果size大于临界点
  115.     if (++size > threshold)
  116.         resize(); // 扩容
  117.     afterNodeInsertion(evict);
  118.     return null;
  119. }
  121. final Node<K,V>[] resize() {
  122.     // 记住原来的数组
  123.     Node<K,V>[] oldTab = table;
  124.     // 如果原来的数组为空，长度即为0，否则为原来的长度
  125.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  126.     // 记住原来的临界点空间大小
  127.     int oldThr = threshold;
  128.     // 新的大小暂为0
  129.     int newCap, newThr = 0;
  130.     // 如果原来的大小大于0
  131.     if (oldCap > 0) {
  132.         // 如果原来的大小大于最大大小，直接赋值为最大值
  133.         if (oldCap >= MAXIMUM_CAPACITY) {
  134.             threshold = Integer.MAX_VALUE;
  135.             return oldTab;
  136.         }
  137.         // 如果原来的大小扩容1倍后小于最大大小并且原来的大小大于等于16
  138.         // 大小扩容1倍
  139.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  140.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  141.             // 临界点扩容1倍
  142.             newThr = oldThr << 1; // double threshold
  143.     }
  144.     // 原来的临界点大于0
  145.     else if (oldThr > 0) // initial capacity was placed in threshold
  146.         newCap = oldThr; // 新的空间等于老的临界点
  147.     else {               // zero initial threshold signifies using defaults
  148.         newCap = DEFAULT_INITIAL_CAPACITY; // 新的空间大小设置为16
  149.         // 新的临界点为12
  150.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  151.     }
  152.     // 处理极限值
  153.     if (newThr == 0) {
  154.         float ft = (float)newCap * loadFactor;
  155.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  156.                   (int)ft : Integer.MAX_VALUE);
  157.     }
  158.     threshold = newThr; // 将计算的临界值保存属性中
  159.     @SuppressWarnings({"rawtypes","unchecked"})
  160.     // 创建新的数组大小
  161.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  162.     table = newTab; // 保存新的数组到属性中
  163.     // 如果原来的数组元素不为空，则重新计算位置
  164.     if (oldTab != null) {
  165.         for (int j = 0; j < oldCap; ++j) {
  166.             Node<K,V> e;
  167.             if ((e = oldTab[j]) != null) {
  168.                 oldTab[j] = null;
  169.                 if (e.next == null)
  170.                     newTab[e.hash & (newCap - 1)] = e;
  171.                 else if (e instanceof TreeNode)
  172.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  173.                 else { // preserve order
  174.                     Node<K,V> loHead = null, loTail = null;
  175.                     Node<K,V> hiHead = null, hiTail = null;
  176.                     Node<K,V> next;
  177.                     do {
  178.                         next = e.next;
  179.                         if ((e.hash & oldCap) == 0) {
  180.                             if (loTail == null)
  181.                                 loHead = e;
  182.                             else
  183.                                 loTail.next = e;
  184.                             loTail = e;
  185.                         }
  186.                         else {
  187.                             if (hiTail == null)
  188.                                 hiHead = e;
  189.                             else
  190.                                 hiTail.next = e;
  191.                             hiTail = e;
  192.                         }
  193.                     } while ((e = next) != null);
  194.                     if (loTail != null) {
  195.                         loTail.next = null;
  196.                         newTab[j] = loHead;
  197.                     }
  198.                     if (hiTail != null) {
  199.                         hiTail.next = null;
  200.                         newTab[j + oldCap] = hiHead;
  201.                     }
  202.                 }
  203.             }
  204.         }
  205.     }
  206.     return newTab;
  207. }

8.4 Properties

Properties继承自Hashtable，但是添加了setProperty和getProperty方法，只能够操作字符串。

作用是用来加载系统的配置文件。所以里面还添加了load方法，专门用来加载配置。

public class TestMain2 {
    // Properties的用法，用来加载资源文件
    public static void main(String[] args) {
        Properties prop = new Properties();
        // 设置值
        prop.setProperty("username", "root");
        prop.setProperty("password", "root");
        prop.setProperty("url", "数据库的url");
        // 获取值
        System.out.println(prop.getProperty("username"));
    }
}

8.5 TreeMap

TreeMap使用树的方式来存放数据，需要对Key对应的类实现Comparable接口。当添加后，会自动排序。

public class Student implements Comparable<Student>{
    private String id;
    private String name;
    private int age;
    public Student(String id, String name, int age) {
        super();
        this.id = id;
        this.name = name;
        this.age = age;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((id == null) ? 0 : id.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Student other = (Student) obj;
        if (id == null) {
            if (other.id != null)
                return false;
        } else if (!id.equals(other.id))
            return false;
        return true;
    }
    @Override
    public String toString() {
        return "Student [id=" + id + ", name=" + name + ", age=" + age + "]";
    }
    @Override
    public int compareTo(Student o) {
        return this.id.hashCode() - o.id.hashCode();
    }
}

public class TestMain3 {
    // TreeMap的用法
    public static void main(String[] args) {
        TreeMap<Student, String> map = new TreeMap<Student, String>();
        map.put(new Student("2", "张三2", 21), "aaa");
        map.put(new Student("1", "张三1", 22), "bbb");
        map.put(new Student("4", "张三4", 23), "ccc");
        map.put(new Student("3", "张三3", 24), "ddd");
        System.out.println(map);
    }
}