集合

一、数组与集合的特点

  1. 1、数组的特点：初始化时就要指定长度，类型，有序（索引），可重复。
  3. 2、 数组的弊端：
  1.         * 一旦初始化以后，长度就不可以修改。
  2.         * 方法很少，增删改操作非常不便，同时效率也不高。
  3.         * 数组没有现成的属性或方法得到数组中实际元素的个数
  4.         * 对于无序、不可重复的需求不能满足。
  1. 3、集合的特点：解决数组的弊端。

二、单列集合框架

1、Collection接口

1.1 集合—-》数组

  1. Object[] arr = coll.toArray();
  2. for(int i = 0;i < arr.length;i++){
  3.     System.out.println(arr[i]);
  4. }

1.2 数组—》集合

  1. List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
  2. System.out.println(list);
  4. List arr1 = Arrays.asList(new int[]{123, 456});
  5. System.out.println(arr1.size());//1
  7. List arr2 = Arrays.asList(new Integer[]{123, 456});
  8. System.out.println(arr2.size());//2

注意：这里转换时，必须要用Integer才能转换成集合中的对象，否则他会把int[] 看成一个对象。

1.3遍历Collection的两种方式

  1.     ①迭代器
  1. Iterator iterator = coll.iterator();//指向集合的前一个位置
  2. //hasNext():判断是否还下一个元素
  3. while(iterator.hasNext()){
  4.     //next():①指针下移 ②将下移以后集合位置上的元素返回
  5.     System.out.println(iterator.next());
  6. }
  1.     ②for-each
  1. for(Object obj : coll){
  2.         System.out.println(obj);
  3.     }

2、List接口（父接口：Collection）

  • 特点：存储有序的，可重复的。（常用实现类:ArrayList，LinkedList、Vector）
  • ArrayList：作为List接口的主要实现类，线程不安全，效率高，底层使用Object[]
  • LinkedList：一般用于频繁的插入、删除，线程安全，效率低，底层使用双向链表。
  • Vector：古老实现类，线程安全呢，效率低，底层使用Object[]

2.1 ArrayList源码分析

  1. ①jdk7情况下：
  1. ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementData
  2. *      list.add(123);//elementData[0] = new Integer(123);
  3. *      ...
  4. *      list.add(11);//如果此次的添加导致底层elementData数组容量不够，则扩容。
  5. *      默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。
  6. *
  7. *      结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)
  1. ②jdk8情况下：
  1. ArrayList list = new ArrayList();//底层Object[] elementData初始化为{},没有给长度
  2. *      list.add(123);//elementData[0] = new Integer(123)，长度设为10
  3. *      ...
  4. *      list.add(11);//后续添加扩容和jdk7一样。
  1. 两种jdk的结论：jdk7时，ArrayList的对象的创建类似于单例模式的饿汉式。jdk8相当于单例模式的懒汉式，节省内存。

2.2 LinkedList的源码分析

  1. *      LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null
  2. *      list.add(123);//将123封装到Node中，创建了Node对象。
  3. *
  4. *      其中，Node定义为：体现了LinkedList的双向链表的说法
  5. *      private static class Node<E> {
  6.             E item;
  7.             Node<E> next;
  8.             Node<E> prev;
  10.             Node(Node<E> prev, E element, Node<E> next) {
  11.             this.item = element;
  12.             this.next = next;
  13.             this.prev = prev;
  14.             }
  15.         }

2.3 Vector的源码分析：

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

2.4 存储元素的要求

  1. 添加的对象，所在的类要重写equals（）方法。

3、Set接口（父接口：Collection）

  • 特点：存储无序的、不可重复的数据
  • HashSet：作为Set接口的主要，线程不安全，可以存储null值
    • LinkedHashSet：作为HashSet的子类，遍历其内部数据时，可以按照添加的顺序遍历。再添加数据的同时，每个数据还维护了前后两个引用，对于频繁的遍历，LinkedHashSet效率高。
  • TreeSet：可以按照添加对象的指定属性，进行排序。（涉及自然排序，定制排序）

3.1 HashSet（jdk7 数组+链表，jdk8，数组+链表+红黑树）

  1. 1、存储的数据特点：无序性，不可重复性。
  3.     ①无序性：指不按照数组索引的顺序添加，是由哈希值决定的。
  5.     ②不可重复性：保证添加的元素按照equals（）判断时，不能返回true，相同的只能添加一个。
  7. 2、元素的添加过程：
  9.     ①首先调用添加元素a所在类的hashCode（）方法，计算元素a的哈希值，根据某种算法计算出在HashSet底层数组的存放位置。并判断这个位置上是否已经有元素
  11.     ②.1 如果没有，则添加成功----------》情况1
  13.     ②.2 如果有其他元素（一个或者以链表形式存放的多个），比较a与其他元素的的hash值
  15.         ②.2.1如果hash不相同，则元素a添加成功----------》情况2
  17.         ②.2.2如果hash相同，进而调用a所在类的equals（)方法
  19.                 如果equals（）返回true，则元素a添加失败
  21.                 如果equals（）返回false，则元素添加成功----》情况3
  23.     注意：对于情况2、3而言，jdk7时，元素a放到数组中，执行原来的元素。jdk8时，原来的元素放在数组中，指向元素a。 ---------------》七上八下
  25. 3、存储对象所在类的要求：
  27.         HashSet/LinkedHashSet都一样：
  29.             重写hashCode（）、equals（）方法，尽量用快捷键。

3.2 TreeSet（天然排序）

  1. 1、使用说明：
  3.     ①向TreeSet中添加的数据，要求是相同类的对象。
  5.     ②两种排序方式：自然排序、定制排序

2、两种方式的代码：

  1. public void test1(){
  2.         TreeSet set = new TreeSet();
  4.         //失败：不能添加不同类的对象
  5. //        set.add(123);
  6. //        set.add(456);
  7. //        set.add("AA");
  8. //        set.add(new User("Tom",12));
  10.             //举例一：
  11. //        set.add(34);
  12. //        set.add(-34);
  13. //        set.add(43);
  14. //        set.add(11);
  15. //        set.add(8);
  17.         //举例二：
  18.         set.add(new User("Tom",12));
  19.         set.add(new User("Jerry",32));
  20.         set.add(new User("Jim",2));
  21.         set.add(new User("Mike",65));
  22.         set.add(new User("Jack",33));
  23.         set.add(new User("Jack",56));
  26.         Iterator iterator = set.iterator();
  27.         while(iterator.hasNext()){
  28.             System.out.println(iterator.next());
  29.         }
  31.     }
  33. //方式二：定制排序
  34.     @Test
  35.     public void test2(){
  36.         Comparator com = new Comparator() {
  37.             //照年龄从小到大排列
  38.             @Override
  39.             public int compare(Object o1, Object o2) {
  40.                 if(o1 instanceof User && o2 instanceof User){
  41.                     User u1 = (User)o1;
  42.                     User u2 = (User)o2;
  43.                     return Integer.compare(u1.getAge(),u2.getAge());
  44.                 }else{
  45.                     throw new RuntimeException("输入的数据类型不匹配");
  46.                 }
  47.             }
  48.         };
  50.         TreeSet set = new TreeSet(com);
  51.         set.add(new User("Tom",12));
  52.         set.add(new User("Jerry",32));
  53.         set.add(new User("Jim",2));
  54.         set.add(new User("Mike",65));
  55.         set.add(new User("Mary",33));
  56.         set.add(new User("Jack",33));
  57.         set.add(new User("Jack",56));
  60.         Iterator iterator = set.iterator();
  61.         while(iterator.hasNext()){
  62.             System.out.println(iterator.next());
  63.         }
  64.     }

三、双列集合框架：Map

1、常用实现类结构：

  • Map：双列数据，key-value
    • HashMap：作为Map的主要实现类:线程不安全，效率高，可以存储null的key和value，
      • LinkedHashMap：子类，保证在遍历map元素时，可以照添加的顺序实现遍历
        原因：在HashMap的底层结构上添加了一对指针，指向前一个元素和后一个原色。
      • TreeMap：保证按照key-value进行排序，实现排序遍历，此时考虑key和value的自然排序或者定制排序。底层实现红黑树。
      • Hashtable：作为古老的实现类：线程安全的，效率低，不能存储null的key和value
        * Properties：常用来畜类配置文件：ksy和value都是String类型。
  • HashMap的底层：数组+链表（jdk8以前）
    数组+链表+红黑树（jdk8及以后）

2、存储结构的理解：

  1. * key：无序的，不可重复的，使用Set存储所有的key--》key所在的类要重写equals（）和hashCode（）。
  2. * value：无序的，可重复的，使用Collection存储所有的value---》value所在的类要重写equals（0方法。
  3. * 一个key-value构成了一个Entry对象
  4. * Entry：无序的，不可重复的，使用Set存储所有的entry。

3、底层实现原理：

  • HashMap在jdk7中的实现原理：
    • Hash Map = new HashMap(); 底层创建了长度为16的一位数组Entry[] table.
      • 多次map.put(key1,value1)
  • put 首先调用key1所在类的hashCode（）计算key1哈希值，次哈希值经过某种算法计算后得到其在Entry[]数组中的存放位置。
    • 如果此位置上的数据为空，此时的key1-value1添加成功—-》情况1
    • 如果此位置上的数据不为空（意味着此位置上存在一个或多个数据，链表形式存在），比较key1和已经存在的一个或多个数据的哈希值：
      • 如果key1和存在这个位置的所有数据的哈希值都不相同，添加成功，以链表存储 —》情况2
      • 如果key1和其中某个位置的数据的哈希值相同：
        调用key1所在类的equals方法，返回true，value1替换之前的value。
         调用key1所在类的equals方法，返回false，添加成功。以链表存储—》情况3
  1.   -  扩容问题： 当超出临界值（且存放的位置非空），扩容，扩容到原来的2倍，并将原来的数据复制过来。
  • HashMap在jdk8与jdk7不同的方面：
    • new HashMap():底层没有创建一个长度为16的数组
    • 底层数组是Node[]，不是Entry[]
    • 首次调用put创建长度为16的数组
    • 7的底层是数组+链表，8的是数组+链表+红黑树，七上八下。
    • 扩容方面：当数组的某一个索引位置上的元素以链表形式存在的个数 > 8，且当前数组的
      长度 > 64时，此时此索引位置上的所有数据改为红黑树存储。
  • HashMap底层典型属性的属性的说明:
    • DEFAULT_INITIAL_CAPACITY：HasMap的默认容量，16
    • DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
    • threshold：扩容的临界值, =容量填充因子：16 0.75 => 12
    • TREEIFY_THRESHOLD：（Bucket中链表长度大于该默认值转换为红黑树） 8
    • MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量：64
  • LinkedHashMap的底层实现原理
  • 结构与HashMap相同，区别就在于LinkedListHashMap内部提供了Entry，替换了Node，可以指向前后两个对象。
  • TreeMap的使用
    //向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
    //因为要照key进行排序：自然排序 、定制排序

  • 使用properties读取配置文件 

    1. public static void main(String[] args)  {
    2.  FileInputStream fis = null;
    3.  try {
    4.      Properties pros = new Properties();
    6.      fis = new FileInputStream("jdbc.properties");
    7.      pros.load(fis);//加载流对应的文件
    9.      String name = pros.getProperty("name");
    10.      String password = pros.getProperty("password");
    12.      System.out.println("name = " + name + ", password = " + password);
    13.  } catch (IOException e) {
    14.      e.printStackTrace();
    15.  } finally {
    16.      if(fis != null){
    17.          try {
    18.              fis.close();
    19.          } catch (IOException e) {
    20.              e.printStackTrace();
    21.          }
    23.      }
    24.  }

面试题

为什么重写equals还有重写hashcode

HashMap中，比较key是否相等要同时使用这两个函数。如果不重写hashcode（），这个方法返回的是内存地址，那就算是含义相同的对象也不可能是一样的。map中的key比较是这样的：先得到hashcode（）的返回值，返回值一样在比较equals（），如果二者都相等的话才算相等。HashMap判断key是否相等的方法其实是调用HashSet判断加入元素是否相等，重写hashCode（）方法是为了对同一个key能得到相同的hashcode，这样就可以定位到指定位置的key，重写equals（）为了向HashMap表明当前对象和key上面保存的对象是相等的，这样我们才真正获得了这个键值对。

介绍一下map的分类和常用情况

  • Map：双列数据，key-value
    • HashMap：作为Map的主要实现类:线程不安全，效率高，可以存储null的key和value，
      • LinkedHashMap：子类，保证在遍历map元素时，可以照添加的顺序实现遍历
        原因：在HashMap的底层结构上添加了一对指针，指向前一个元素和后一个原色。
      • TreeMap：保证按照key-value进行排序，实现排序遍历，此时考虑key和value的自然排序或者定制排序。底层实现红黑树。
      • Hashtable：作为古老的实现类：线程安全的，效率低，不能存储null的key和value
        * Properties：常用来畜类配置文件：ksy和value都是String类型。
  • HashMap的底层：数组+链表（jdk8以前）
    数组+链表+红黑树（jdk8及以后）

请说明List、Map、Set三个接口存取元素的时候，各有什么特点

List：以特定所有来存取原色，可以有重复元素
Set：不能存放重复元素
Map：保存键值对，映射关系可以是一对一或者多对一
Set和Map都有基于哈希存储和排序树存储的两种实现版本，基于哈希存储的版本理论存取时间复杂度为O（1）
，但是基于排序树版本在实现插入或者删除元素时会按照元素或元素的key构成排序树实现排序和去重的效果

阐述ArrayList、Vector、LinkedList的存储性能和特性

ArrayList与Vector：都是使用数组方式存储数据，此数组长度大于实际存储的数据长度以便增加或者插入元素，
他们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作。所以两个都是查快块插入慢，vector中的方法添加了synchronized修饰，所以是线程安全的，但性能低，所以是遗留容器。
LinkedList：使用双向链表存储，内存利用率更高，按序号索引的时候需要遍历，但是插入数据的时候只需要记录本项的前后项即可，所以插入效率高，查找效率低。

说明HashTable和HashMap的区别

HashMap允许key，value是null，HasshTable不允许
HashMap不是同步的，适合单线程，HashTable反之
HashMap提供了可供应用迭代的键的集合，因此，HashMap是快速失败的。另一方面，Hashtable提供了对key的列举，一般认为是遗留的类

说说快速失败和安全失败

iterator的安全是白是基于对底层集合做拷贝，因此他不受源集合上修改的影响。java.util包下面的所有集合都是快速失败的，java.util.concurrent包下面所有的类都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常，但是安全失败不会

说一下Iterator和ListIterator的区别

iterator可以遍历List和Set，但是ListIterator只能遍历List
前者堆积和只能是前向遍历，后者既可以前向也可以后向
后者实现了前者这个接口，并包含了其他功能：增加原色，替换元素，获取前一个和后一个元素的索引等等

请简单说明一下什么是迭代器

Iterator提供了统一遍历操作集合的统一接口，Collection接口实现了Iterator接口
每个集合都通过实现iterator接口中的iterator（）方法返回iterator实例，然后对集合的元素进行迭代操作
注意:在迭代元素的时候不能通过集合的方法删除元素，否则会抛出ConcurrentModificationException异常
，但是可以用iterator接口中的remove（）方法

解释一下集合类为什么不实现Cloneable和Serializable接口

克隆或者序列化是跟具体的实现有关的（比如某个实体里是否序列化）等等
实现克隆的作用：将对象的状态保存到存储媒体中以便可以在以后重写创建出完全相同的副本;按值将对象从一个应用程序域发向另一个应用程序域
实现序列化作用：把对象存到字节流中，然后可以恢复。如果没有序列化就不难呢个进行网络传输，因为需要字节流才能呢个传输。

说明一下ConcurrenthashMap的原理

ConcurrentHashMap类中包含两个静态内部类HashEntry和Segment。HashEntry用来封装映射表的key-value;
Segment继承与ReentrantLock类用来充当锁的角色，每个Segment对象守护整个散列映射表的若干个桶。每个桶是由若干个HashEntry对象连接起来的链表。一个ConcurrentHashMap实例中包含了若干个Segment组成的数组。在HashEntry类中，key，hash，next域都被声明为final型，value域被声明为volatile型。
在concurrentHashmap中，散列的时候如果出现碰撞，把碰撞的HashEntry对象链接成一个链表。由于HashEntry的next域是final型的，所以新节点只能在链表的表头处插入。

说明ConcurrentHashMap有什么优势以及1.7和1.8有什么区别

优势：线程安全
1.7是采用Segment+HashEntry的方式进行实现的，lock锁加在Segment上面的。size计算是先采用不加锁的方法，连续计算元素的个数，最多计算3次：1、如果前后两次计算结果相同，则说明计算出来的元素个数是准确的;
2、如果不相同，则给每个Segment进行加锁，在计算依次元素的个数

1.8中放弃了Segment的设计，取而代之的是Node+CAS+Synchronized来保证并发安全进行实现，使用了一个volatile类型的变量baseCount记录元素的个数，当插入新书巨或者删除数据时，会通过addCount（）方法更新baseCount，通过累加baseCount和CounterCell数组中的数据即可得到元素的总个数。

解释一下TreeMap

TreeMap是一个有序的key-value集合，基于红黑树（平衡的排序二叉树）实现的。该映射根据key的自然顺序进行排序，或者根据创建映射是提供的Comparator进行排序，具体取决于使用的构造方法
TreeMap的特性：
根节点是黑色
每个节点都是只能是黑色或者红色
每个叶子节点是黑色的
一条路径上不能呢个有相邻的两个红色的节点
从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

解释HashMap具体如何实现的

HashMap是基于数组实现的，通过对key的（hashcode&数组的长度-1）得到在数组（数组的长度一般为2n）中的位置，如果当前这个位置有元素，比较hashcode，不同的话当前元素就指向添加元素，像这样解决hash冲突的。注意的是，jdk1.8的时候引入了红黑树，当链表元素个数大于等于8且数组长度大于等于64的时候转换为红黑树，当元素个数小于6的时候树结构转换为链表。因结构为红黑树的平均查找长度是logN，长度为8的时候平均长度是3,使用链表的话平均长度是4,提升了效率。中间有个7视为了防止频繁转换，假设链表元素个数一直在8的时候不停插入、删除那么链表和树就不停转换，效率会很低。