Java 集合/容器

开发和学习中需要时刻和数据打交道,如何组织这些数据是我们编程中重要的内容。

我们一般通过“容器”来容纳和管理数据。那什么是“容器”呢?生活中的容器不难理解,是用来容纳物体的,如锅碗瓢盆、箱子和包等。程序中的“容器”也有类似的功能,就是用来容纳和管理数据。

事实上,数组就是一种容器,可以在其中放置对象或基本类型数据。

数组的优势:是一种简单的线性序列,可以快速地访问数组元素,效率高。如果从效率和类型检查的角度讲,数组是最好的。

数组的劣势:不灵活。容量需要事先定义好,不能随着需求的变化而扩容。比如:我们在一个用户管理系统中,要把今天注册的所有用户取出来,那么这样的用户有多少个?我们在写程序时是无法确定的。因此,在这里就不能使用数组。

基于数组并不能满足我们对于“管理和组织数据的需求”,所以我们需要一种更强大、更灵活、容量随时可扩的容器来装载我们的对象。这就是我们今天要学习的容器,也叫集合。以下是容器的接口层次结构图:

Collection 接口

Collection 表示一组对象,它是集中、收集的意思。Collection 接口的两个子接口是 List、Set 接口。

由于 List、Set 是 Collection 的子接口,意味着所有 List、Set 的实现类都有上面的方法。我们下一节中,通过 ArrayList 实现类来测试上面的方法。

  • Collection 集合概述
    • 是单例集合的顶层接口,它表示一组对象,这些对象也称为 Collection 的元素。
  • JDK 不提供此接口的任何直接实现,它提供更具体的子接口(如 Set 和 List)实现。
  • 创建 Collection 集合的对象:
    • 多态的方式;
    • 具体的实现类如 ArrayList。

Collection 集合基本使用:

public class CollectionDemo01 {
    public static void main(String[] args) {
        // 创建 Collection 集合的对象
        Collection<String> c = new ArrayList<String>();

        // 添加元素:boolean add(E e)
        c.add("hello");
        c.add("world");
        c.add("java");

        // 输出集合对象
        System.out.println(c);
    }
}

Collection 集合的常用方法

方法名说明
int size()集合的长度,也就是集合中元素的个数
boolean isEmpty()判断集合是否为空
boolean contains(Object o)判断集合中是否存在指定的元素
Iterator<E> iterator();获得迭代器,用于遍历所有元素
Object[] toArray();转化成 Object 数组
boolean add(E e)添加元素
boolean remove(Object o)从集合中移除指定的元素
boolean containsAll(Collection<?> c)判断集合中是否存在指定集合中的所有元素
boolean addAll(Collection<? extends E> c)添加指定集合中的所有元素
boolean removeAll(Collection<?> c)从集合中移除指定集合中的所有元素
boolean retainAll(Collection<?> c)仅保留此集合中包含在指定集合中的元素,即取交集
void clear()清空集合中的元素

List 接口

  • List 集合概述
    • 有序集合(也称为序列)。用户可以精确控制列表中每个元素的插入位置;用户可以通过整数索引访问元素,并搜索列表中的元素。
    • 与 Set 集合不同,列表通常允许重复的元素。
  • List 集合特点
    • 有索引;
    • 可以存储重复元素;
    • 元素存取有序。

List 接口常用的实现类有 3 个:ArrayList、LinkedList 和 Vector。

List 集合的特有方法

List 接口的定义:

public interface List<E> extends Collection<E> {}

继承自 Collection,也就继承了 Collection 的所有方法,因此这里只列出 List 的特有方法。

方法名描述
void add(int index,E element)在此集合中的指定位置插入指定的元素
E remove(int index)删除指定索引处的元素,返回被删除的元素
E set(int index,E element)修改指定索引处的元素,返回被修改的元素
E get(int index)返回指定索引处的元素

ArrayList

ArrayList 特点和底层实现

ArrayList 底层是用数组实现的存储。

**特点:**查询效率高,增删效率低,线程不安全。

通过以下源码,我们可以看出 ArrayList 底层使用 Object 数组来存储元素数据。所有的方法,都围绕这个核心的 Object 数组来开展。

img

ArrayList 数组扩容源码分析

数组长度是有限的,而 ArrayList 是可以存放任意数量的对象,长度不受限制,那么它是怎么实现的呢?本质上就是通过定义新的更大的数组,将旧数组中的内容拷贝到新数组,来实现扩容。 ArrayList 的 Object 数组初始化长度为10,如果我们存储满了这个数组,需要存储第11个对象,就会定义新的长度更大的数组,并将原数组内容和新的元素一起加入到新数组中,源码如下:

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
} 

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
} 

int newCapacity = oldCapacity + (oldCapacity >> 1); 我们可以知道 ArrayList 的扩容是增加 1/2 的扩容,即原来是 10容量的数组,变为 15。

ArrayList 删除元素源码分析

本质上还是数组的拷贝

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

System.arraycopy(elementData, index+1, elementData, index, numMoved);

解读:elementData 的从第 index+1 个元素往后的元素,即 elementData[index+1]~elementData[size-1],拷贝到 elementData 的以 index 为起点往后的位置中,即 elementData[index]~elementData[size-2]。这样原来的 elementData[index] 上的元素就被覆盖掉了,然后 size-1,就好像原来的元素被删除了一样。其实本质上还是拷贝。所以说,ArrayList 的增删效率是很低的。

LinkedList

LinkedList 特点和底层实现

LinkedList 底层用双向链表实现的存储。

**特点:**查询效率低,增删效率高,线程不安全。

双向链表也叫双链表,是链表的一种,它的每个数据节点中都有两个指针,分别指向前一个节点和后一个节点。 所以,从双向链表中的任意一个节点开始,都可以很方便地找到所有节点。

img

每个节点都应该有 3 部分内容:

class Node {
    Node previous;     //前一个节点
    Object element;    //本节点保存的数据
    Node next;         //后一个节点
}

查看 LinkedList 的源码,可以看到里面包含了双向链表的相关代码:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    transient Node<E> first;

    transient Node<E> last;

    public LinkedList() {
    }
    
    ...
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

Vector 向量

Vector 底层是用数组实现的 List,相关的方法都加了同步检查,因此“线程安全,效率低”。 比如,indexOf() 方法就增加了 synchronized 同步标记。

说明

如何选用 ArrayList、LinkedList、Vector?

  1. 需要线程安全时,用 Vector。

  2. 不存在线程安全问题时,并且查找较多ArrayList

  3. 不存在线程安全问题时,增加或删除元素较多LinkedList

  4. ArrayList 是使用最普遍的。

Set 接口

Set 接口继承自 Collection,Set 接口中没有新增方法,方法和 Collection 保持完全一致。

Set 容器特点:

  • 无序:指Set中的元素没有索引,我们只能遍历查找;
  • 不可重复:指不允许加入重复的元素。更确切地讲,新元素如果和 Set 中某个元素通过 equals() 方法对比为 true,则不能加入;Set 中甚至只能放入一个 null 元素,不能放多个。

Set 常用的实现类有:HashSet、TreeSet 等。一般使用 HashSet。

HashSet 基本使用

重点体会“Set 是无序、不可重复”的核心要点:

public static void main(String[] args) {
    Set<String> stringSet = new HashSet<>();
    stringSet.add("Hello");
    stringSet.add("World");
    stringSet.add("Java");
    stringSet.add("Java");
    System.out.println(stringSet); // [Java, Hello, World]
    stringSet.add("Golang");
    stringSet.add("Python");
    stringSet.add(null);
    System.out.println(stringSet); // [Golang, null, Java, Hello, World, Python]
}

Set 其他方法与 Collention 接口提供的方法差不多。

HashSet 底层实现

HashSet 是采用哈希算法实现,底层实际是用 HashMap 实现的(HashSet 本质就是一个简化版的 HashMap),因此,查询效率和增删效率都比较高。我们来看一下 HashSet 的源码:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E, Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    // 省略其他代码
} 

我们发现里面有个 map 属性,这就是 HashSet 的核心秘密。我们再看 add() 方法,发现增加一个元素说白了就是在 map 中增加一个键值对,键对象就是这个元素,值对象是名为 PRESENT 的 Object 对象。说白了,往 set 中加入元素,本质就是把这个元素作为 key 加入到了内部的 map 中。

由于 map 中 key 都是不可重复的,因此,Set 天然具有“不可重复”的特性。

TreeSet 的使用

TreeSet 底层实际是用 TreeMap 实现的,内部维持了一个简化版的 TreeMap,通过 key 来存储 Set 的元素。 TreeSet 内部需要对存储的元素进行排序,因此,我们对应的类需要实现 Comparable 接口。这样,才能根据 compareTo() 方法比较对象之间的大小,才能进行内部排序。

public static void main(String[] args) {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("200");
    treeSet.add("300");
    treeSet.add("100");
    for (String s : treeSet) {
        System.out.println(s);
    }

    System.out.println("======================");

    TreeSet<Emp> empMap = new TreeSet<>();
    empMap.add(new Emp(1, "Andy", 30000));
    empMap.add(new Emp(3, "Bob", 5000));
    empMap.add(new Emp(2, "Candy", 10000));
    empMap.add(new Emp(4, "David", 5000));
    for (Emp emp : empMap) {
        System.out.println(emp);
    }
}

class Emp implements Comparable<Emp> {
    int id;
    String name;
    double salary;

    public Emp(int id, String name, double salary) {
        this.id = id;
        this.name = name;
        this.salary = salary;
    }

    @Override
    public int compareTo(Emp o) { // 返回值说明:负数代表小于,0代表等于,正数代表大于。
        if (this.salary > o.salary) {
            return 1;
        } else if (salary < o.salary) {
            return -1;
        } else {
            return Integer.compare(this.id, o.id);
        }
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", salary=" + salary +
                '}';
    }
}

使用TreeSet要点:

  1. 由于是二叉树,需要对元素做内部排序。 如果要放入 TreeSet 中的类没有实现 Comparable 接口,则会抛出异常:java.lang.ClassCastException。
  2. TreeSet 中不能放入 null。

Map 接口

现实生活中,我们经常需要成对存储某些信息。比如,我们使用的微信,一个手机号只能对应一个微信账户。这就是一种成对存储的关系。

Map 就是用来存储“键(key)-值(value) 对”的。 Map 类中存储的“键值对”通过来标识,所以“键”不能重复。

Map 接口的实现类有 HashMap、TreeMap、HashTable、Properties 等。

Map 常用方法

方法名说明
int size();Map 中键值(key-value)对的数量
boolean isEmpty();Map 是否为空
boolean containsKey(Object key);Map 中是否包含指定的 key
boolean containsValue(Object value);Map 中是否包含指定的 value
V get(Object key);通过 key 查找 value
V put(K key, V value);存放 key-value
V remove(Object key);从 Map 中删除指定的 key-value,并返回 value
void putAll(Map<? extends K, ? extends V> m);将指定 Map m 中的所有键值对存放到本 Map 中
Set<K> keySet();获取所有 key 的 Set 集合
Set<Map.Entry<K, V>> entrySet();获取 Map 中的所有键值对

HashMap

HashMap 采用哈希算法实现,是 Map 接口最常用的实现类。由于底层采用了哈希表存储数据,我们要求键不能重复,如果发生重复,新的键值对会替换旧的键值对。 HashMap 在查找、删除、修改方面都有非常高的效率。

示例:

public static void main(String[] args) {
    Map<Integer, String> m1 = new HashMap<Integer, String>();
    Map<Integer, String> m2 = new HashMap<Integer, String>();
    
    m1.put(1, "one");
    m1.put(2, "two");
    m1.put(3, "three");
    
    m2.put(1, "一");
    m2.put(2, "二");
    
    System.out.println(m1.size()); // 3
    System.out.println(m1.containsKey(1)); // true
    System.out.println(m2.containsValue("two")); // false
    
    m1.put(3, "third"); // 键重复了,则会替换旧的键值对
    
    Map<Integer, String> m3 = new HashMap<Integer, String>();
    m3.putAll(m1);
    m3.putAll(m2);
    
    System.out.println("m1:" + m1); // m1:{1=one, 2=two, 3=third}
    System.out.println("m2:" + m2); // m2:{1=一, 2=二}
    System.out.println("m3:" + m3); // m3:{1=一, 2=二, 3=third}
}

HashMap 与 HashTable

HashTable 和 HashMap 用法几乎一样,底层实现几乎一样,只不过 HashTable 的方法添加了 synchronized 关键字确保线程同步检查,效率较低。

  1. HashMap: 线程不安全,效率高。允许 key 或 value 为null。
  2. HashTable: 线程安全,效率低。不允许 key 或 value 为null。

HashMap 底层实现详解

HashMap 底层实现采用了哈希表,这是一种非常重要的数据结构。很多技术都用到了这个数据结构。比如:Redis 数据库的核心技术和 HashMap 本质是一样。

数据结构中由数组和链表来实现对数据的存储,他们各有特点。

  1. 数组:占用空间连续。寻址容易,查询速度快。但是,增加和删除效率非常低。
  2. 链表:占用空间不连续。寻址困难,查询速度慢。但是,增加和删除效率非常高。

那么,我们能不能结合数组和链表的优点(即查询快,增删效率也高)呢?答案就是“哈希表”。哈希表的本质就是“数组+链表”。

HashMap 基本结构

打开 HashMap 源码,其核心为:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    /**
     * The default initial capacity - MUST be a power of two.
     * 核心数组默认初始化的大小为16(数组大小必须为2的整数幂)
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     * 核心数组最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
     * The load factor used when none specified in constructor.
     * 负载因子(核心数组被占用超过0.75,则开始启动扩容)
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * 核心数组(根据需要可以扩容)。数组长度必须始终为2的整数幂。
     */
    transient Node<K,V>[] table;
} 

其中的 Node[] table 就是 HashMap 的核心数组结构,我们也称之为“位桶数组”。我们再继续看 Node 是什么,源码如下:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

一个 Node 对象存储了:

  1. hash:键对象的 hash 值;
  2. key:键对象;
  3. value:值对象;
  4. next:下一个节点。

显然每一个 Node 对象就是一个单向链表结构,我们使用图形表示一个 Node 对象的典型示意:

然后,Node[] 数组的结构也就很清楚了(这也是HashMap的结构):

存储数据过程 put(key, value)

明白了 HashMap 的基本结构后,我们继续深入了解 HashMap 如何存储数据。此处的核心是如何产生 hash 值,该值用来对应数组的存储位置。

我们的目的是将“key-value 两个对象”成对存放到 HashMap 的 Entry[] 数组中。参见以下步骤:

  1. 获得 key 对象的 hashcode

  2. 根据 hashcode 计算出 hash 值(要求在[0, 数组长度-1]区间)。

    hashcode 是一个整数,我们需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的 hash 值尽量均匀地分布在[0,数组长度-1]这个区间,减少“hash冲突”。这里提供两种思路:

    • 极简的算法:hash值 = hashcode/hashcode;

      也就是说,hash 值总是 1。意味着,键值对对象都会存储到数组索引 1 位置,这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”,HashMap 也退化成了一个“链表”。

    • 简单和且常用的算法 —— 相除取余算法:hash值 = hashcode % 数组长度;

      这种算法可以让 hash 值均匀的分布在[0,数组长度-1]的区间。 早期的 HashTable 就是采用这种算法。但是,这种算法由于使用了“除法”,效率低下。JDK 后来改进了算法。首先约定数组长度必须为2的整数幂,这样采用位运算即可实现取余的效果:hash值 = hashcode & (数组长度-1)

      关于为什么取余运算可以转换成位运算,可以看这篇文章

      /**
       * @author ZJax
       * @date 2021年05月23日 13:28
       */
      public class TestHash {
          public static void main(String[] args) {
              int h = 25860399;
              int length = 16; // length为2的整数次幂,则h&(length-1)相当于对length取模
              int hash = myHash(h, length);
              System.out.println(hash);
          }
      
          /**
           * @param h      任意整数
           * @param length 长度必须为2的整数幂
           * @return 余数
           */
          private static int myHash(int h, int length) {
              System.out.println(h & (length - 1));
              // length为2的整数幂情况下,和取余的值一样
              System.out.println(h % length); // 取余数
              return h & (length - 1);
          }
      }
      

      运行如上程序,我们就能发现直接取余 h % length 和 位运算 h & (length - 1) 结果是一致的。事实上,为了获得更好的散列效果,JDK 对 hashcode 进行了进一步处理(核心目标就是为了分布更散更均匀),源码如下:

      /**
       * Computes key.hashCode() and spreads (XORs) higher bits of hash
       * to lower.  Because the table uses power-of-two masking, sets of
       * hashes that vary only in bits above the current mask will
       * always collide. (Among known examples are sets of Float keys
       * holding consecutive whole numbers in small tables.)  So we
       * apply a transform that spreads the impact of higher bits
       * downward. There is a tradeoff between speed, utility, and
       * quality of bit-spreading. Because many common sets of hashes
       * are already reasonably distributed (so don't benefit from
       * spreading), and because we use trees to handle large sets of
       * collisions in bins, we just XOR some shifted bits in the
       * cheapest possible way to reduce systematic lossage, as well as
       * to incorporate impact of the highest bits that would otherwise
       * never be used in index calculations because of table bounds.
       */
      static final int hash(Object key) {
          int h;
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }
      
  3. 生成 Node 对象

    如上所述,一个 Node 对象包含4部分:key、value、hash值、指向下一个Node对象的引用。我们现在算出了hash值。下一个Node对象的引用为null。

  4. 将 Node 对象放到 table 数组中

    如果本 Node 对象对应的数组索引位置还没有放 Node 对象,则直接将 Node 对象存储进数组;如果对应索引位置已经有 Node 对象,则将已有 Node 对象的 next 指向本 Node 对象,形成链表。

过程总结:

当添加一个键值对(key-value)时,首先计算 key 的 hash值,以此确定插入数组中的位置,但是可能存在同一 hash值的元素已经被放在数组同一位置了,这时就添加到同一 hash值的元素的后面,他们在数组的同一位置,就形成了链表,同一个链表上的 hash值是相同的,所以说数组存放的是链表。

额外说明:JDK8中,当链表长度大于8时,链表就转换为红黑树,这样又大大提高了查找的效率。

取数据过程 get(key)

我们需要通过 key 对象获得“键值对”对象,进而返回 value 对象。明白了存储数据过程,取数据就比较简单了,参见以下步骤:

  1. 获得 key 的 hashcode,通过 hash() 散列算法得到 hash值,进而定位到数组的位置。
  2. 在链表上挨个比较 key 对象。 调用 equals() 方法,将 key 对象和链表上所有节点的 key 对象进行比较,直到碰到返回 true 的节点对象为止。
  3. 返回 equals() 为 true 的节点对象的 value 对象。

明白了存取数据的过程,我们再来看一下 hashcode() 和 equals 方法的关系:

Java 中规定,两个内容相同(即 equals() 为 true)的对象必须具有相等的 hashCode。因为如果 equals() 为 true 而两个对象的 hashcode 不同,那在整个存储过程中就发生了悖论。

扩容问题

HashMap 的位桶数组,初始大小为16。实际使用时,显然大小是可变的。如果位桶数组中的元素达到(0.75*数组 length), 就重新调整数组大小变为原来2倍大小。

扩容很耗时。扩容的本质是定义新的更大的数组,并将旧数组内容挨个拷贝到新数组中。

TreeMap

TreeMap 的使用和底层实现

TreeMap 是红黑二叉树的典型实现。我们打开 TreeMap 的源码,发现里面有一行核心代码:

private transient Entry<K,V> root;

root 用来存储整个树的根节点。我们继续跟踪 Entry(TreeMap 的内部类)的代码:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
    // 省略其他代码
} 

可以看到里面存储了本身数据、左节点、右节点、父节点、以及节点颜色。 TreeMap 的 put()/remove() 方法大量使用了红黑树的理论。

TreeMap 和 HashMap 实现了同样的接口 Map,因此,用法对于调用者来说没有区别。HashMap 效率高于 TreeMap,在需要排序的 Map 时才选用 TreeMap。

public static void main(String args[]) {
    Map<Integer, String> treeMap = new TreeMap<>();
    treeMap.put(1, "A");
    treeMap.put(3, "C");
    treeMap.put(2, "B");

    /*
     * TreeMap内部按照key.hashCode()递增的方式排序
     * 1-----A
     * 2-----B
     * 3-----C
     */
    for (Integer key : treeMap.keySet()) {
        System.out.println(key + "-----" + treeMap.get(key));
    }

    System.out.println("======");

    Map<Emp, String> empMap = new TreeMap<>();
    empMap.put(new Emp(1, "Andy", 30000), "Andy");
    empMap.put(new Emp(3, "Bob", 5000), "Bob");
    empMap.put(new Emp(2, "Candy", 10000), "Candy");
    empMap.put(new Emp(4, "David", 5000), "David");

    /*
     * Emp{id=3, name='Bob', salary=5000.0}-----Bob
     * Emp{id=4, name='David', salary=5000.0}-----David
     * Emp{id=2, name='Candy', salary=10000.0}-----Candy
     * Emp{id=1, name='Andy', salary=30000.0}-----Andy
     */
    for (Emp key : empMap.keySet()) {
        System.out.println(key + "-----" + empMap.get(key));
    }
}

class Emp implements Comparable<Emp> {
    int id;
    String name;
    double salary;

    public Emp(int id, String name, double salary) {
        this.id = id;
        this.name = name;
        this.salary = salary;
    }

    @Override
    public int compareTo(Emp o) { // 返回值说明:负数代表小于,0代表等于,正数代表大于。
        if (this.salary > o.salary) {
            return 1;
        } else if (salary < o.salary) {
            return -1;
        } else {
            return Integer.compare(this.id, o.id);
        }
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", salary=" + salary +
                '}';
    }
} 

Collections 工具类

java.util.Collections 提供了对 Set、List、Map 进行排序、填充、查找元素的辅助方法。

方法说明
void sort(List<T> list)对 List 容器内的元素排序,排序的规则是按照升序进行排序。
void shuffle(List<?> list)对 List 容器内的元素进行随机排列。
void reverse(List<?> list)对 List 容器内的元素进行逆续排列;即翻转 List。
void fill(List<? super T> list, T obj)用一个特定的对象重写整个 List 容器。
int binarySearch(List<? extends Comparable<? super T>> list, T key)对于顺序的 List 容器,采用折半查找的方法查找特定对象。
public static void main(String[] args) {
    List<String> aList = new ArrayList<>();
    for (int i = 0; i < 5; i++){
        aList.add("a" + i);
    }
    System.out.println(aList);

    Collections.shuffle(aList); // 随机排列
    System.out.println(aList);

    Collections.reverse(aList); // 逆序
    System.out.println(aList);

    Collections.sort(aList); // 按照递增的方式排序。自定义类要实现Comparable接口
    System.out.println(aList);

    System.out.println(Collections.binarySearch(aList, "a2")); // 二分搜索

    Collections.fill(aList, "hello");
    System.out.println(aList);
}

迭代器

迭代器:集合的专用遍历方式。

迭代器是通过集合的 iterator() 方法得到的,所以我们说它是依赖于集合而存在的。

Collection 集合的遍历

  • 步骤1:创建集合对象
  • 步骤2:添加元素
  • 步骤3:遍历集合
    • 通过集合对象获取迭代器对象
    • 通过迭代器对象的 hasNext() 方法判断是否还有元素
    • 通过迭代器对象的 next() 方法获取下一个元素

如果遇到遍历容器时,判断删除元素的情况,使用迭代器遍历!

public static void main(String[] args) {
    // 创建集合对象
    Collection<String> c = new ArrayList<>();

    // 添加元素
    c.add("hello");
    c.add("world");
    c.add("java");
    c.add("javaee");

    // Iterator<E> iterator():返回此集合中元素的迭代器,通过集合的iterator()方法得到
    Iterator<String> it = c.iterator();

    // 用while循环改进元素的判断和获取
    while (it.hasNext()) {
        String s = it.next();
        System.out.println(s);
    }
}

迭代器遍历 List

public static void main(String[] args) {
    List<String> aList = new ArrayList<String>();
    for (int i = 0; i < 5; i++) {
        aList.add("a" + i);
    }
    System.out.println(aList);

    for (Iterator<String> iter = aList.iterator(); iter.hasNext();) {
        String temp = iter.next();
        System.out.print(temp + "\t");
        if (temp.endsWith("3")) { // 删除3结尾的字符串
            iter.remove();
        }
    }

    /* 也可以使用while循环 */
    /*Iterator<String> it = aList.iterator();
        while(it.hasNext()) {
            String temp = it.next();
            System.out.print(temp + '\t');
            if (temp.endsWith("3")) {
                it.remove();
            }
        }*/

    System.out.println();
    System.out.println(aList);
}

迭代器遍历 Set

public static void main(String[] args) {
    Set<String> set = new HashSet<String>();
    for (int i = 0; i < 5; i++) {
        set.add("a" + i);
    }
    System.out.println(set);
    for (Iterator<String> iter = set.iterator(); iter.hasNext();) {
        String temp = iter.next();
        System.out.print(temp + "\t");
    }
    System.out.println();
    System.out.println(set);
}

迭代器遍历 Map 一

public static void main(String[] args) {
    Map<String, String> map = new HashMap<String, String>();
    map.put("A", "zjax");
    map.put("B", "izj");
    Set<Entry<String, String>> ss = map.entrySet();
    for (Iterator<Entry<String, String>> iterator = ss.iterator(); iterator.hasNext();) {
        Entry<String, String> e = iterator.next();
        System.out.println(e.getKey() + "--" + e.getValue());
    }
}

迭代器遍历 Map 二

public static void main(String[] args) {
    Map<String, String> map = new HashMap<String, String>();
    map.put("A", "zjax");
    map.put("B", "izj");
    Set<String> ss = map.keySet();
    for (Iterator<String> iterator = ss.iterator(); iterator.hasNext();) {
        String key = iterator.next();
        System.out.println(key + "--" + map.get(key));
    }
}

总结

  1. Collection 表示一组对象,它是集中、收集的意思,就是把一些数据收集起来。

  2. Collection接口的两个子接口:

    • List中的元素有顺序,可重复。常用的实现类有ArrayList、LinkedList和 vector。

      • ArrayList 特点:查询效率高,增删效率低,线程不安全。

      • LinkedList 特点:查询效率低,增删效率高,线程不安全。

      • vector 特点:线程安全,效率低,其它特征类似于 ArrayList。

    • Set 中的元素没有顺序,不可重复。常用的实现类有 HashSet 和 TreeSet。

      • HashSet 特点:采用哈希算法实现,查询效率和增删效率都比较高。
      • TreeSet 特点:内部需要对存储的元素进行排序。因此,我们对应的类需要实现 Comparable 接口。这样,才能根据 compareTo() 方法比较对象之间的大小,才能进行内部排序。
  3. 实现 Map 接口的类用来存储键(key)-值(value)对。Map 接口的实现类有 HashMap 和 TreeMap 等。Map类中存储的键-值对通过键来标识,所以键值不能重复。

  4. Iterator 对象称作迭代器,用以方便的实现对容器内元素的遍历操作。

  5. 类 java.util.Collections 提供了对 Set、List、Map 操作的工具方法。

  6. 如下情况,可能需要我们重写equals/hashCode方法:

    • 要将我们自定义的对象放入HashSet中处理。
    • 要将我们自定义的对象作为HashMap的key处理。
    • 放入Collection容器中的自定义对象后,可能会调用remove、contains等方法时。
  7. JDK1.5 以后增加了泛型。泛型的好处:

    • 向集合添加数据时保证数据安全。
    • 遍历集合元素时不需要强制转换。