召WEN天下

2018-09-02 16:10 北京交通大学 C++

关注

【有书共读】《疯狂JAVA讲义》读书笔记08

集合是什么？

Java集合类存放于 java.util 包中，是一个用来存放对象的容器。

注意：①、集合只能存放对象。比如你存一个 int 型数据 1放入集合中，其实它是自动转换成 Integer 类后存入的，Java中每一种基本类型都有对应的引用类型。

②、集合存放的是多个对象的引用，对象本身还是放在堆内存中。

③、集合可以存放不同类型，不限数量的数据类型。

集合详解

①、Iterator:迭代器，它是Java集合的顶层接口（不包括 map 系列的集合，Map接口是 map 系列集合的顶层接口）

Object next()：返回迭代器刚越过的元素的引用，返回值是 Object，需要强制转换成自己需要的类型

boolean hasNext()：判断容器内是否还有可供访问的元素

void remove()：删除迭代器刚越过的元素

所以除了 map 系列的集合，我们都能通过迭代器来对集合中的元素进行遍历。

注意：我们可以在源码中追溯到集合的顶层接口，比如 Collection 接口，可以看到它继承的是类 Iterable

那这就得说明一下 Iterator 和 Iterable 的区别：

Iterable ：存在于 java.lang 包中。

我们可以看到，里面封装了 Iterator 接口。所以只要实现了只要实现了Iterable接口的类，就可以使用Iterator迭代器了。

Iterator ：存在于 java.util 包中。核心的方法next(),hasnext(),remove()。

这里我们引用一个Iterator 的实现类 ArrayList 来看一下迭代器的使用：暂时先不管 List 集合是什么，只需要看看迭代器的用法就行了

 1 //产生一个 List 集合，典型实现为 ArrayList。  2 List list = new ArrayList();  3 //添加三个元素  4 list.add("Tom");  5 list.add("Bob");  6 list.add("Marry");  7 //构造 List 的迭代器  8 Iterator it = list.iterator();  9 //通过迭代器遍历元素 10 while(it.hasNext()){ 11 Object obj = it.next(); 12  System.out.println(obj); 13 }

②、Collection:List 接口和 Set 接口的父接口

③、List :有序，可以重复的集合。

由于 List 接口是继承于 Collection 接口，所以基本的方法如上所示。

1、List 接口的三个典型实现：

①、List list1 = new ArrayList();

底层数据结构是数组，查询快，增删慢;线程不安全，效率高

　 ②、List list2 = new Vector();

底层数据结构是数组，查询快，增删慢;线程安全，效率低,几乎已经淘汰了这个集合

③、List list3 = new LinkedList();

底层数据结构是链表，查询慢，增删快;线程不安全，效率高

怎么记呢？我们可以想象：

数组就像身上编了号站成一排的人，要找第10个人很容易，根据人身上的编号很快就能找到。但插入、删除慢，要望某个位置插入或删除一个人时，后面的人身上的编号都要变。当然，加入或删除的人始终末尾的也快。

链表就像手牵着手站成一圈的人，要找第10个人不容易，必须从第一个人一个个数过去。但插入、删除快。插入时只要解开两个人的手，并重新牵上新加进来的人的手就可以。删除一样的道理。

2、除此之外，List 接口遍历还可以使用普通 for 循环进行遍历，指定位置添加元素，替换元素等等。

④、Set：典型实现 HashSet()是一个无序，不可重复的集合

1、Set hashSet = new HashSet();

①、HashSet:不能保证元素的顺序；不可重复；不是线程安全的；集合元素可以为 NULL;

②、其底层其实是一个数组，存在的意义是加快查询速度。我们知道在一般的数组中，元素在数组中的索引位置是随机的，元素的取值和元素的位置之间不存在确定的关系，因此，在数组中查找特定的值时，需要把查找值和一系列的元素进行比较，此时的查询效率依赖于查找过程中比较的次数。而 HashSet 集合底层数组的索引和值有一个确定的关系：index=hash(value),那么只需要调用这个公式，就能快速的找到元素或者索引。

③、对于 HashSet: 如果两个对象通过 equals() 方法返回 true，这两个对象的 hashCode 值也应该相同。

　　　1、当向HashSet集合中存入一个元素时，HashSet会先调用该对象的hashCode（）方法来得到该对象的hashCode值，然后根据hashCode值决定该对象在HashSet中的存储位置

1.1、如果 hashCode 值不同，直接把该元素存储到 hashCode() 指定的位置

1.2、如果 hashCode 值相同，那么会继续判断该元素和集合对象的 equals() 作比较

1.2.1、hashCode 相同，equals 为 true，则视为同一个对象，不保存在 hashSet（）中

1.2.2、hashCode 相同，equals 为 false，则存储在之前对象同槽位的链表上，这非常麻烦，我们应该约束这种情况，即保证：如果两个对象通过 equals() 方法返回 true，这两个对象的 hashCode 值也应该相同。

注意：每一个存储到哈希表中的对象，都得提供 hashCode() 和 equals() 方法的实现，用来判断是否是同一个对象

对于 HashSet 集合，我们要保证如果两个对象通过 equals() 方法返回 true，这两个对象的 hashCode 值也应该相同。

常见的 hashCode()算法：

2、Set linkedHashSet = new LinkedHashSet();

①、不可以重复，有序

因为底层采用链表和哈希表的算法。链表保证元素的添加顺序，哈希表保证元素的唯一性

3、Set treeSet = new TreeSet();

TreeSet:有序；不可重复，底层使用红黑树算法，擅长于范围查询。

* 如果使用 TreeSet() 无参数的构造器创建一个 TreeSet 对象, 则要求放入其中的元素的类必须实现 Comparable 接口所以, 在其中不能放入 null 元素

* 必须放入同样类的对象.(默认会进行排序) 否则可能会发生类型转换异常.我们可以使用泛型来进行限制

                                         1            
             2            
             3            
             4            
                         Set treeSet = new TreeSet();             
                      treeSet.add(1);  //添加一个 Integer 类型的数据             
                      treeSet.add("a");   //添加一个 String 类型的数据             
                      System.out.println(treeSet);  //会报类型转换异常的错误             
          
               

　 *　自动排序：添加自定义对象的时候，必须要实现 Comparable 接口，并要覆盖 compareTo(Object obj) 方法来自定义比较规则

如果 this > obj,返回正数 1

如果 this < obj,返回负数 -1

如果 this = obj,返回 0 ，则认为这两个对象相等

　　　　　　* 两个对象通过 Comparable 接口 compareTo(Object obj) 方法的返回值来比较大小, 并进行升序排列

　 * 定制排序: 创建 TreeSet 对象时, 传入 Comparator 接口的实现类. 要求: Comparator 接口的 compare 方法的返回值和两个元素的 equals() 方法具有一致的返回值

              public class TreeSetTest {             
                  public static void main(String[] args) {             
                      Person p1 = new Person(1);             
                      Person p2 = new Person(2);             
                      Person p3 = new Person(3);             
                                    
                      Set<Person> set = new TreeSet<>(new Person());             
                      set.add(p1);             
                      set.add(p2);             
                      set.add(p3);             
                      System.out.println(set);  //结果为[1, 2, 3]             
                  }             
                            
              }             
                            
              class Person implements Comparator<Person>{             
                  public int age;             
                  public Person(){}             
                  public Person(int age){             
                      this.age = age;             
                  }             
                  @Override             
                  /***             
                   * 根据年龄大小进行排序             
                   */             
                  public int compare(Person o1, Person o2) {             
                      // TODO Auto-generated method stub             
                      if(o1.age > o2.age){             
                          return 1;             
                      }else if(o1.age < o2.age){             
                          return -1;             
                      }else{             
                          return 0;             
                      }             
                  }             
                                
                  @Override             
                  public String toString() {             
                      // TODO Auto-generated method stub             
                      return ""+this.age;             
                  }             
              }             