本文共 7915 字，大约阅读时间需要 26 分钟。

1. Set集合

1.1 基本概念

• 是Collection接口的子接口，和List接口平级
• 元素不能重复，且无序
• 主要实现类：
  • HashSet：底层是哈希表
  • TreeSet：底层是红黑树
  • LinkedHashSet：底层是哈希表+双向链表
    • 双向链表：用于记录元素放入集合中的先后顺序，便于迭代

1.2 Set的常用方法

• 参考Collection集合中的方法即可

1.3 HashSet

• 是set接口的主要实现类 ；非线程安全；可以存储null值

• HashSet 底层的实现其实是一个 java.util.HashMap 支持

  // 构建一个hashSetSet
       
         hashSet = new HashSet
        
         ();// 调用的构造方法，实际上是创建了一个HashMappublic HashSet() {
           map = new HashMap<>();}
        
       

• HashSet存储

  • 根据 HashSet 中元素的哈希值，来确定元素在集合中的位置

  • 底层是希表存

  • 必须重写hashCode、equals方法

    • 重写equals方法：

      用equals判断两个对象是否相等，比较的是地址值。重写equals方法后，判断的是这两个对象的属性是否相等

    • 重写hashCode方法：

      保证同一个元素能得到唯一的哈希码。这样，同一个元素只有一个哈希值，只需要和索引位置的元素进行比较即可，从而提高了效率，避免元素重复

  • 哈希表的大致结构图：

    

    • 在JDK1.8之前，哈希表底层采用数组+链表实现 （数组中存放的是链表头结点的地址）

      

    • 元素通过HashCode()，得到一个哈希码。该哈希码通过哈希算法，得到哈希值

    • 哈希值通过一系列算法，得到哈希值在数组中索引，并将元素添加到到该数组中

    • 若数组中已经存放链表了，

      1. 先用该元素的哈希值和整条链表的所有节点进行比较，若没有相同，则将该元素添加到尾节点

      2. 如果有节点，与之哈希值相同！！那么调用equal()，判断这两个元素是否相同。若是没有，则将该元素添加到尾节点

      3. 如果有节点，与之哈希值相同！！那么插入失败( 所谓的元素不能重复 )

举例：用HashSet存储用户自定义的类

• 自定义用户类

  public class Student {
           private String name;    private int age;    // ......(还有get、set、构造方法，就省略了)        @Override    public boolean equals(Object o) {
               // ...... （重写equals方法）    }    @Override    public int hashCode() {
               return Objects.hash(name, age);    }}

• 构建哈希表，并进行存储

  • 在下面的代码中，构建了 HashSet集合，并进行添加元素

  • 但是我们发现，第二次没有添加成功 ( 是因为自定义的Student类重写了hashCode、equals方法 )

    // 构建HashSet来存储Student类型对象HashSet
           
             stuSet = new HashSet
            
             ();//存储测试Student stu = new Student("于谦", 43);stuSet.add(stu);stuSet.add(new Student("于谦", 43));
            
           

• 添加不同元素

  stuSet.add(new Student("郭德纲", 44));stuSet.add(new Student("郭麒麟", 23));

• 遍历HashSet

  // 遍历列表for (Student stu2 : stuSet) {
           System.out.println(stu2);}

• 执行结果：

  Student [name=郭德纲, age=44]

  Student [name=于谦, age=43]

  Student [name=郭麒麟, age=23]

案例总结：

• 根据执行结果，我们可以看到，相同的name=于谦的类，没有添加成功
• HashSet集合是无序的
• 自定义类，一定要重写hashCode、equals方法

1.4 TreeSet

• 二叉树：

  • 基本概念：

    

  • 有序二叉树：

    • 左子树中任意一个节点 < 根节点(30) < 右子树中的任意一个节点
    • 左、右子树内部，也遵循 左< 根 < 右

    

• 红黑树，就是有序二叉树

  • 所以，当有新元素插入TreeSet时，实际上就是把新元素和集合中元素依次比较，来确定合理的位置，保证插入后的集合，还是有序二叉树

  

• 比较元素大小的规则，有两种方式：

  1. 自然排序：

     • 让集合中的元素，实现java.lang.Comparable接口 ( 重写compareTo方法 )

       // Comparable接口public interface Comparable
                
                  {
                	public int compareTo(T o);}
                

  2. 比较器排序：

     • 在TreeSet的构造方法中，将java.util.Comparator接口作为参数传入

       public TreeSet(Comparator
                 comparator) {
                    this(new TreeMap<>(comparator));}

     • 准备一个比较器对象，作为参数传入构造方法：

       1. 使用Comparator接口的匿名内部类
       2. 使用Comparator接口的实现类

  3. 两种排序方式的一个对比：

     • 自然排序方式，比较单一
     • 比较器排序，则多元化 ( 优先使用比较器排序 )

• 举例说明：

  • 下列代码执行结果为： [a, b, c]
    • [a, b, c] ，满足有序二叉树的规则

  // 构建HashSetSet
       
         strSet = new HashSet
        
         ();strSet.add("a");strSet.add("c");strSet.add("b");System.out.println(strSet.toString());
        
       

  思考：将元素插入二叉树中，实际上是将元素同集合中的元素进行比较，确保二叉树有序。但是上述代码中，并没有指定比较类型，那他们是如何进行比较的？

  • 查看源码：

    public final class String    implements java.io.Serializable, Comparable
           
            , CharSequence
           

    我们发现String类型，实现了java.lang.Comparable接口。原来，默认的是使用自然排序。同时，Integer、Short…等都实现了

    public final class Integer extends Number implements Comparable
           

  • 结论：

    除了自定义类，默认都是实现了java.lang.Comparable接口。所以，自定义类想要使用TreeSet集合，那么必须在自然排序，比较器排序中，选择一种实现。

• 使用 TreeSet集合，存储自定义类Student （一定要选择排序方式）

  • 第一种方式：实现Comparable接口

  public class Student implements Comparable
       
        {
           private String name;    private int age;    // ......(还有get、set、构造方法，就省略了)        // 实现了Comparable接口那么就要重写compareTo    public int compareTo(Student obj){
               // 先根据姓名比较。如果姓名相等，那么比较年龄		int i = this.getName().compareTo(obj.getName();        return 0 != i ? i : this.getAge() - obj.getAge();    }}
       

  ​ compareTo方法，返回值说明：

  1. 0： 待插入的对像 - 参数对象 = 0 (插入失败)
  2. 负数：待插入的对像 - 参数对象 < 0 , 说明待插入的对像 < 参数对象
  3. 正数：待插入的对像 - 参数对象 > 0 , 说明待插入的对像 > 参数对象

  Set
       
         trSet = new TreeSet
        
         ();stuSet.add(new Student("悟空", 43));stuSet.add(new Student("八戒", 43));
        
       

  • 第二种方式：在TreeSet的构造方法中，将Comparator 接口作为参数传入

    public class Student {
               private String name;    private int age;    // ......(还有get、set、构造方法，就省略了)        // 重写hashCode和qeuals	@Override    public boolean equals(Object o){
                   // ...略    }    @Override    public int hashCode() {
                   return Objects.hash(name, age);    }}

    在构建TreeSet时，将Comparator接口使用匿名内部类，作为参数传入：

    Set
           
             stuSet = new TreeSet
            
             (new Comparator
             
              () {
               @Override    // o1,表示待插入集合的元素对象；o2,表示集合中已有的对象    public int compare(Student o1, Student o2) {
                   int i = o1.getName().compareTo(o2.getName());        return 0 != i ? i : o1.getAge() - o2.getAge();    }});stuSet.add(new Student("悟空", 43));stuSet.add(new Student("八戒", 43));
             
            
           

    ​ 而且从Java8开始，支持Lambda表达式：( 参数列表 ) -> { 方法体 }

    Set
           
             trSet = new TreeSet
            
             ((Student o1, Student o2) -> {
               int i = o1.getName().compareTo(o2.getName());    return 0 != i ? i : o1.getAge() - o2.getAge();});
            
           

2. Map集合

2.1 基本概念

• Map集合中，存取基本单位是键值对

• Map在大量的数据下，具有优良的查询性能 (先找Key，Key找不着，就不用去找Value了)

• key是不能重复的 ( Key：目录，value：目录对应的内容 。目录是不能重复的)

• Map接口的主要实现类：

  • HashMap类：底层是，哈希表

    • LinkedHashMap是HashMap的子类
    • LinkedHashMap类：底层是，哈希表 + 双向链表

  • TreeMap类：底层是，红黑树

  • HashTable类：

    • 古老的Map实现类，key、value的值不能为null

    • 线程安全，效率低下

    • Properties 类是Hashtable 的子类：

      1. 用于处理配置文件

      2. Properties 里的key和value 都是字符串类型

      3. 存取数据时，建议使用 setProperty(String key,String value) 方法和 getProperty(String key) 方法

         

• 面试题：

  为什么有HashMap了，还要有LinkedHashMap？

  • HashMap保证成对元素唯一，并且查询速度很快，可是成对元素存放进去是没有顺序的
  • LinkedHashMap，询速度快，而且存放的顺序有序

  LinkedHashMap为什么存放有序？

  • 在HashMap的基础上，每一个键值对对象引用的一前一后，都添加了一对指针，指向了前一个元素的引用和后一个元素的引用。

  HashMap 和 Hashtable 的区别

  • Hashtable 线程安全效率低下，HashMap 与之相反

  Set集合和Map集合的关系

  • Set集合底层是Map集合

  • Set集合在添加元素的时候，实际上是往Map的key中添加，而Value则添加默认值：new Object()

    • 以TreeSet为例

      // 底层是Map集合public TreeSet() {
                   this(new TreeMap
               
                ());}
               

      add方法

      private static final Object PRESENT = new Object();public boolean add(E e) {
                   // 元素是往 key添加，而Value值是一个默认值PRESENT    return m.put(e, PRESENT)==null;}

1.2 Map集合中的常用方法

1.2.1 Map集合的遍历

• 方法1：遍历key

  // 将key存放在set集合Set
       
         stuKeys = studentMap.keySet();// 遍历key，来获取对应的valuefor (Integer key: stuKeys){
           // 根据键值，来求 value    String value = studentMap.get(key);    System.out.print(value + ",");}
       

• 方法2：遍历key-value

  // 将所有键值对对象存放在set集合Set
       
        
         > keyValueObj = studentMap.entrySet();// 遍历键值对for (Map.Entry
         
           objEntry : keyValueObj) {
           // 获取单个键值对的key、value    Integer key = objEntry.getKey();    String value = objEntry.getValue();    System.out.println(key + " - " + value);}
         
        
       

1.3 Map 集合扩容分析

• 构建Map，调用构造方法

  HashMap
       
         s = new HashMap
        
         ();// 源码：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;static final float DEFAULT_LOAD_FACTOR = 0.75f;  int threshold;public HashMap() {
           this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
        
       

  参数说明：

  • DEFAULT_LOAD_FACTOR ： 加载因子，默认是 0.75
  • DEFAULT_INITIAL_CAPACITY：默认容量16 。是指哈希表中数组的长度
  • threshold：扩容的临界值，threshold = 加载因子 * 默认容量 = 16 * 0.75 = 12。也就是说，数组中有12个元素，我们就对数组进行扩容

3.Collections工具类

注意：

• 在使用copy方法时，源集合的中现有的元素个数 > 目标集合中的先有个数。不然会索引越界异常
• 值得注意的是，这里并不是指容量，而是指集合汇总存在的个数
• 那么我们新建一个空集合，想要使用copy，最好用 Arrays.asList 的方式创建

List
   
     list = Arrays.asList(new Integer[10]);System.out.println(list);
   

结果为：

转载地址：http://dhuen.baihongyu.com/