容器的概念

为什么要使用集合框架(Why)

如果并不知道程序运行时会需要多少个对象,或者需要更复杂的存储对象--可以使用Java 集合框架

Java集合框架包含的内容

Java集合框架提供了一套性能优良、使用方便的接口和类,它们位于java.util包中

Collection接口

Collection接口存储一组不唯一,无序的对象

         Collection c1 = new ArrayList();
         collection1.add("x");
         collection1.add("y");
         collection1.add("s");
         collection1.add("y");
         collection1.add("c");
         collection1.add("x");
         System.out.println(c1);

输出结果如下

 [x, y, s, y, c, x]

这里输入结果是不唯一,有序的 ,因为我new 的是List接口的实现类,有序是List接口的特性

Set接口存储唯一,无序对象,无序是Set接口的特性. List和Set的特性完全相反.

在此仅体现了Collection接口存储对象的不唯一性.

集合作为容器应该具有的功能(增删改查)

Collection接口的一些常见方法列表如下

我对这些常见常用的API方法进行了简单分类,集合的基本操作:增加,删除,判断,取出

添加

 add():要求传入的参数是Object对象,因此当写入基本数据类型的时候,包含了自动拆箱和自动装箱的过程
 addAll(): 添加另一个集合的元素到此集合中

删除

 clear():    只是清空集合中的元素,但是此集合对象并没有被回收
 remove():   删除指定元素
 removeAll():删除集合元素
 retainAll():仅保留那些包含指定集合的元素(删除指定集合元素之外的所有元素), 如果原集合有变动则返回                true,否则返回false

查询

 contains(): 判断集合中是否包含指定的元素值
 containsAll():判断此集合中是否包含另一个集合
 isEmpty():判断集合是否为空

其它

 toArray():将集合转换成数组

List接口

List接口存储一组不唯一,有序(插入顺序)的对象

List接口特有的方法

凡是可以操作索引的方法都是该体系特有的方法

|

ArrayList

ArrayList 实现了长度可变的数组,在内存中分配连续的空间.

ArrayList优点

遍历元素和随机访问元素的效率比较高

ArrayList缺点

添加和删除需要大量移动元素,效率低,按照内容查询效率低

ArrayList面试问题

ArrayList和Vector 的区别是什么?

• ArrayList是线程不安全的,效率高,Vector是线程安全的效率低
• ArrayList在进行扩容的时候,是当前容量的1.5倍,而Vector扩容的时候是扩容到当前容量的2倍

LinkedList采用链表存储方式

LinkedList采用链表存储方式,也就是说链表的优缺点LinkedList全具备,如果你具备一定的数据结构基础,相信学起来会非常友好. 数组和链表的区别与优缺点

linkedList特有的方法

LinkedList优点

插入、删除元素时效率比较高

LinkedList缺点

遍历和随机访问元素效率低下

ArrayList和LinkedList对比

• ArrayList
  • 遍历元素和随机访问元素的效率比较高
  • 插入、删除扥操作频繁时性能低下
• LinkedList
  • 插入、删除时元素效率较高
  • 查找效率较低

Set接口

• Set接口存储一组唯一,无序的对象
• (存入和取出的顺序不一定一致)
• 操作数据的方法和List类似,**Set接口不存在get()**方法

Set接口中的实现类

• HashSet:采用Hashtable哈希表存储结构
  • 优点:添加速度快,查询速度快,删除速度快
  • 缺点:无序
• LinkedHashSet
  • 采用哈希表存储结构,同时使用链表维护次序
  • 有序(添加顺序)
• TreeSet
  • 采用二叉树(红黑树)的存储结构
  • 优点:有序(排序后的升序)查询速度比List快
  • 缺点:查询速度没有HashSet快

什么是Hash表

哈希表(Hash table,也叫散列表),具有像数组那样根据随机访问的特性,是根据关键码值(key-value)而进行访问的数据结构.也就说,它通过把关键码映射到表中的一个位置来访问记录,以加快查找速度.这个映射函数叫做散列函数,存放记录的数组叫做散列表.

Hash Table的查询速度非常的快,几乎是O(1)的时间复杂度.

hash函数就是找到一种数据内容和数据存放地址之间的映射关系.

HashSet

HashSet 集合不允许存储相同的元素, 它底层实际上使用 HashMap 来存储元素的, 不过关注的只是key元素, 所有 value元素默认为 Object类对象.

当使用无参构造创建 HashSet对象时, 其实调用了 HashMap的无参构造创建了一个 HashMap对象, 所以 HashSet 的初始化容量也为16, 负载因子也为 0.75.

HashSet实现了Set接口, 仅存储对象

代码验证HashSet的无序性和唯一性

         HashSet hashSet = new HashSet();
         hashSet.add("b");
         hashSet.add("b");
         hashSet.add("c");
         hashSet.add("耗子尾汁");
         hashSet.add("Fedeline");
         hashSet.add("雪月书韵茶香");
         System.out.println(hashSet);

 [耗子尾汁, b, c, Fedeline, 雪月书韵茶香]

hashSet存储自定义对象

如果我们需要使用HashSet存储自定义对象,我们需要重写hashCode方法与equals方法

 HashSet hs=new HashSet();//创建HashSet对象
 hs.add(new Person("张三",20));
 hs.add(new Person("李四",22));
 hs.add(new Person("王五",23));
 hs.add(new Person("李四",22));

• HashSet存储进了相同的对象,不符合实际情况
• 解决方案
  • 重写equals方法和hashCode方法
• 不重写的后果
  • 自定义对象会调用父类的hashCode方法对自定义对象内存地址的比对,hashSet的唯一性将失效

 @Override
 public int hashCode() {
  System.out.println(this.name+".....hashCode");
  return this.name.hashCode()+age;
 }

HashSet是如何保证元素的唯一性?

HashSet是通过元素的两个方法,HashCode和equals方法来完成

如果元素的HashCode值相同,才会判断是否为true

如果元素的hashCode 值不同,不会调用equals方法

LinkedHashSet

TreeSet

• TreeSet是Set接口的实现子类,因此具备Set接口的唯一性,并具备有序的特点
• TreeSet底层实现的是TreeMap,利用红黑树来进行实现
• 设置元素的时候,如果是自定义对象,会查找对象中的equals和hashCode方法,如果没有,比较的是内存地址
• 树中的元素是要默认进行排序操作的,如果是基本数据类型,自动比较,如果是引用类型,需要自定义比较器
  • 比较器分类
    • 内部比较器
      • 定义在元素的类中,通过实现Comparable接口来实现
    • 外部比较器
      • 定义在当前类中,通过实现Comparator接口来实现
      • 外部比较器可以定义成一个工具类,此时所有需要比较的规则如果一样的话可以复用
      • 内部比较器局限性较大,多种自定义元素都需要进行比较时候,需要在每种自定义元素类中编写代码
      • 如果外部比较器和内部比较器同时存在,外部比较器优先被使用
      • 当使用比较器时候不会调用equals方法

TreeSet 存放自定义类型示例代码

 package cn.xysycx.collection;
 
 public class Person implements Comparable {
     private String name;
     private int age;
     @Override
     public int compareTo(Object o) {
         Person person = (Person) o;
         if (person.name.length()>this.name.length()){
             return -1;
         }else if (person.name.length()<this.name.length()){
             return 1;
         }
         return 0;
     }
 
     public Person() {
     }
 
     public Person(String name, int age) {
         this.name = name;
         this.age = age;
     }
 
     @Override
     public String toString() {
         return "Person{" +
                 "name='" + name + '\'' +
                 ", age=" + age +
                 '}';
     }
 
     public String getName() {
         return name;
     }
 
     public void setName(String name) {
         this.name = name;
     }
 
     public int getAge() {
         return age;
     }
 
     public void setAge(int age) {
         this.age = age;
     }
 }
 

 package cn.xysycx.collection;
 
 import java.util.Comparator;
 import java.util.TreeSet;
 
 public class TreeSetDemo implements Comparator<Person> {
     @Override
     public int compare(Person o1, Person o2) {
         if (o1.getAge()>o2.getAge()){
             return -1;
         }else if (o1.getAge()<o2.getAge()){
             return 1;
         }
         return 0;
     }
 
     public static void main(String[] args) {
         TreeSet treeSet=new TreeSet();
         treeSet.add(new Person("lisi",13));
         treeSet.add(new Person("zhangsan",15));
         treeSet.add(new Person("maliu",17));
         treeSet.add(new Person("wansi",15));
         treeSet.add(new Person("liubai",19));
         System.out.println(treeSet);
         System.out.println("----------------------------");
         TreeSet treeSet1=new TreeSet(new TreeSetDemo());
         treeSet1.add(new Person("lisi",13));
         treeSet1.add(new Person("zhangsan",15));
         treeSet1.add(new Person("zhangsan1",15));  //比较器返回0  会去重,此条数据不会被加入treeSet
         treeSet1.add(new Person("maliu",17));
         treeSet1.add(new Person("wansi",15));
         treeSet1.add(new Person("liubai",19));
         System.out.println(treeSet1);
 
     }
 }
 

 [Person{name='lisi', age=13}, Person{name='maliu', age=17}, Person{name='liubai', age=19}, Person{name='zhangsan', age=15}]
 ----------------------------
 [Person{name='liubai', age=19}, Person{name='maliu', age=17}, Person{name='zhangsan', age=15}, Person{name='lisi', age=13}]

采用二叉树(红黑树)的存储结构

TreeSet优点

有序(排序后的升序)查询速度比List快

TreeSet缺点

查询速度没有HashSet快

Map

map特点:key-value映射

举例:session存储键值对 redis存储键值对 JSON也是键值对格式 HBase存储键值对

Map接口特有的方法

Map 的实现子类

• HashMap
• LinkedhashMap
• TreeMap

HashMap(重点)

HashMap底层

• 数组+链表(JDK1.7)
• 数组+链表+红黑树(JDK1.8)

LinkedHashMap

特点:有序的HashMap 速度快

• LinkedHashMap是非线程安全的
• 可以把LinkedHashMap看成是HashMap+LinkedList
  • 使用HashMap操作数据结构,也用LinkedList维护插入元素的先后顺序

LinkedHashMap底层

• 哈希表+双向链表

TreeMap

有序 速度没有hash快

问题:Set与Map有关系吗?

如果集合前缀相同,底层算法一样,Set底层用的是Map的算法.

把Set集合对象作为Map的Key,再使用一个Object常量作为value.

也就是说,在Map中,所有的Key就是一个Set集合.

iterator接口

所有实现了Collection接口的容器类都有一个iterator方法用以返回一个实现了Iterator接口的对象

iterator是一个接口，它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。

所有的集合类均为提供相应的遍历方法,而是把遍历交给迭代器完成.迭代器是为集合而生,专门实现集合遍历

Iterator是迭代器设计模式的具体实现.

有些新手更疑惑了,啥是迭代器?

Provide a way to access the elements of an aggregate object sequentially without exposing its
underlying representation.

它提供一种方法访问一个容器对象中各个元素， 而又不需暴露该对象的内部细节。

下图是迭代器模式通用类图

迭代器就是为容器服务的.

迭代器模式提供了遍历容器的方便性， 容器只要管理增减元素就可以了， 需要遍历时交
由迭代器进行。

简单地说， 迭代器就类似于一个数据库中的游标， 可以在一个容器内上下翻滚， 遍历所
有它需要查看的元素

可以使用Iterator的本质就是实现了Iterator接口

Iterator提供的API接口如下：

在iterator()方法中,要求返回一个Iterator的接口子类实例对象,此接口包含了hasNext(),next(),remove()

 boolean hashNext();//判断是否有元素没有被遍历
 Object next();//返回游标当前位置的元素并将游标移动到下一个位置
 void remove();//删除游标左面的元素,在执行完next之后该操作只能执行一次

在使用Iterator进行迭代过程中,如果删除其中的某个元素会报错---->并发操作异常.

如果只删除一个元素可以使用remove方法删除,因为remove只可以被调用一次

java中的For-each循环

For-each循环

• 增强的for循环,遍历array或Collection的时候相当简便

• 无需获得集合和数组的长度,无需使用索引访问元素,无需循环条件

• 遍历集合时底层调用Iterator完成操作

  For-each缺陷

  • 数组:
    • 不能方便访问下标值
    • 不要在for-each中尝试对变量赋值,只是一个临时变量
  • 集合
    • 与使用Iterator相比,不能方便 的删除集合总的内容
  • For-each总结
    • 除了简单的遍历并读出其中的内容外,不建议使用增强for循环(For-each)

ListIterator

为什么需要ListIterator

在迭代过程中,准备添加或者删除元素

         ArrayList al=new ArrayList();
         al.add("java1");//添加元素
         al.add("java2");
         al.add("java3");
        //遍历
         Iterator it=al.iterator();
         while(it.hasNext()){
             Object obj=it.next();
             if (obj.equals("java2")) {
                 al.add("java9");
             }
             System.out.println("obj="+obj);
         }

提示并发修改异常

 obj=java1
 obj=java2
 Exception in thread "main" java.util.ConcurrentModificationException
     at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
     at java.util.ArrayList$Itr.next(ArrayList.java:859)
     at cn.xysycx.Test1.main(Test1.java:15)
 
 Process finished with exit code 1

ListIterator的作用--->解决并发操作异常

在迭代时,不可能通过集合对象的方法(al.add(?))操作集合中的元素

会发生并发修改异常

所以,在迭代时只能通过迭代器的方法操作元素,但是Iterator的方法是有限的,只能进行判断(hasNext),取出(next),删除(remove)的操作,

如果想要在迭代过程中进行向集合中添加,修改元素等就需要使用ListIterator接口中的方法

         ListIterator li=al.listIterator();
         while(li.hasNext()){
             Object obj=li.next();
             if ("java2".equals(obj)) {
                 li.add("java9994");
 //                li.set("java002");
             }
 
         }

Comparable 接口

问题:如何排序?

上面的算法根据什么确定集合对象的"大小"顺序?

所有可以"排序"的了都实现了java.lang.Comparable接口

Comparable接口中只有一个方法

 public int compareTo(Object obj);

返回 0 表示 this == obj

返回 正数 表示 this > obj

返回 负数 表示 this < obj

实现了Comparable接口的类通过实现compareTo方法从而确定了该类的排序方式

排序方法示例代码如下

 public class StrLenComparator implements Comparator<String> {
     @Override
     public int compare(String o1, String o2) {
         if (o1.length()>o2.length()) {
             return 1;
         }
         if (o1.length()<o2.length()) {
             return -1;
         }
         return o1.compareTo(o2);//长度相同，按字母
     }
 }

 public static void sortDemo(){
         List<String> list=new ArrayList<String>();
         //此处省略..添加元素
         sop(list);
         Collections.sort(list);//按字母排序
         sop(list);
 //按照字符串长度排序
         Collections.sort(list,new StrLenComparator());
         sop(list);
         }

Collection工具类

Collections和Collection不同

Collections是集合的操作类,Collection是集合接口

Collections提供的静态方法

• addAll(): 批量的添加
• sort():排序
• binarySearch():二分查找
• fill():替换
• shuffle():随机排序
• reverse():逆序

集合总结

面试常问

Collection和Collections的区别

• Collection是Java提供的集合接口，存储一组丌唯 一，无序的
  对象。它有两个子接口List和Set。
• Java还有一个Collections类，与门用来操作集合类，它提供了
  一系列的静态方法实现对各种集合的搜索、排序、线程安全化
  等操作。

ArrayList和LinkedList的联系和区别

• ArrayList实现了长度可变的数组,在内存中分配连续空间.遍历元素和随机访问元素效率比较高
• LinkedList采用链表存储方式.插入、删除元素效率比较高

Vector和ArrayList的联系和区别

• Vector和ArrayList实现原理相同,都是长度可变的数组结构,很多时候可以互用
• 两者主要区别如下
  • Vector是早期JDK接口,ArrayList是替代Vector的新接口
  • Vector线程安全,ArrayList重速度轻安全,线程非安全
  • 长度需要增长时,Vector默认增长一倍,ArrayList增长50% (1+0.5)

HashMap和Hashtable的联系和区别

• HashMap和HashTable的实现原理相同,功能相同,底层都是hash表结构,查询速度快,在很多情况下都可以互用
• 两者主要区别如下
  • HashTable是早期的JDK提供的接口,HashMap是新版的JDK提供的接口
  • HashTable继承Dictionary类,HashMap实现Map接口
  • HashTable是线程安全,HashMap是线程非安全
  • HashTable不允许null值,HashMap允许null值