集合相关内容

Veröffentlicht am | Bearbeitet am | in .
Symbole im Artikel gezählt: 7.4k | Lesezeit ≈ 7 minuten.

数组和集合的比较

数组不是面向对象的，存在明显的缺陷，集合弥补了数组的缺点，比数组更灵活更实用，而且不同的集合框架类可适用不同场合。如下:

  1. 数组能存放基本数据类型和对象，而集合类存放的都是对象的引用，而非对象本身！
  2. 数组容易固定无法动态改变，集合类容量动态改变。
  3. 数组无法判断其中实际存有多少元素，length只告诉了数组的容量，而集合的size()可以确切知道元素的个数
  4. 集合有多种实现方式和不同适用场合，不像数组仅采用顺序表方式
  5. 集合以类的形式存在，具有封装、继承、多态等类的特性，通过简单的方法和属性即可实现各种复杂操作，大大提高了软件的开发效率

Java集合整体图

Collection和Map是集合框架的根接口

Collection的子接口

Set接口—>实现类：HashSet、LinkedHashSet

​ Set的子接口SortedSet接口—>实现类：TreeSet

List接口—>实现类：LinkedList、Vector、ArrayList

List集合

  1. 有序的集合，允许存放重复的元素，有索引，元素可以为null

  2. 实现类：

    • ArrayList：数组实现，查询快，增删慢，轻量级（线程不安全的）
    • LinkedList:双向循环列表实现，增删快，查询慢（线程不安全）
    • Vector:数组实现，重量级（线程安全，不经常使用）

  3. List常用方法：

    • void add (int index,Object element):添加对象element到位置index上
    • boolean addAll(int index,Collection collection):在index位置后添加容器collection中所有的元素
    • Object get (int index):取出下标为index的位置的元素
    • int indexOf(Object element):查找对象element在List中第一次出现的位置
    • int lastIndexOf(Object element):查找对象element在List中最后出现的位置
    • Object remove(int index):删除index位置上的元素
    • ListIterator listIterator(int startIndex):返回一个ListIterator迭代器，开始位置为startIndex
    • List subList(int fromIndex,int toIndex):返回一个子列表，元素存放为fromIndex到toIndex之前的所有元素

  4. 利用LinkedList实现栈（stack)、队列（queue）、双向队列（double-ended queue)。LinkedList具有addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()等方法。

  5. 用LinkedList实现队列：

    队列是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。表中允许插入的一端称为队尾，允许删除的一端称为对头，队列的操作是按照先进先出的原则进行的，队列的物理存储可以用顺序存储结构也可以用链式存储结构

  6. 用LinkedList实现栈：

    栈也是一种特殊的线性表，是一种先进后出的结构，栈是限定在表尾进行插入和删除运算的线性表，表尾称为栈顶，表头称为栈底，栈的物理存储可以用顺序结构，也可以使用链式存储结构

Set集合

  1. 不允许存放重复的元素，没有索引，允许使用null元素，但是不能重复，所以只能有一个空元素

  2. 实现类:

    • HashSet:不仅不能保证元素插入的顺序，而且元素在以后的顺序中也可能发生变化（这是由于HashSet按照Hash’Code存储对象单元决定的，对象变化可能也会导致HashCode变化），HashSet是线程非安全的。HashSet的后台有一个HashMap初始化后台容量，而HashMap的底层是哈希表(数组+单向链表+红黑树(链表的长度超过8)),只不过生成一个HashSet的话，系统只提供key的访问，如果有两个key相同，那么会覆盖之前 的。
    • LinkedHashSet:此实现与HashSet的不同之处在于它维护这一个运行于所有条目的双重连接列表，存储的数据是有序的
    • TreeSet:TreeSet实现了SortedSet接口，顾名思义，这是一种排序的Set集合，查看jdk源码发现底层是用TreeMap实现的，本质上是一个红黑树原理。正因为他是排了序的，所以相对HashSet来说，TreeSet提供了一些额外的按照排序位置访问元素的方法，例如first()、last()、lower()、higher()、subSet()、headSet()、tailSet()。TreeSet的排序分为两种，一种是自然排序，一种是定制排序。

  3. HashSet常用的方法：

    • public boolean contaions(Object o):如果Set包含指定的元素，返回True
    • public Iterator iterator()：返回Set集合中元素的迭代器
    • public Object[] toArray():返回包含Set中所有元素的数组
    • public Object[] toArray(Object[] a):返回包含Set中所有元素的数组，返回数组的运行时类型是指定数组的运行时类型。
    • public boolean add(Object o):如果set中不存在指定元素，则向set中添加
    • public boolean remove(Object o):如果set中存在指定的元素，则从set中删除
    • public boolean removeAll(Collection c):如果set中包含指定的集合，则从set中删除指定集合的所有元素
    • public boolean containsAll(Collection c):如果set包含指定集合的所有元素，返回true，如果指定的集合也是一个set，只有是当前set的子集时，返回true

  4. HastSet的equals和HashCode

    前面说过Set集合是不允许重复元素的，否则将会引发各种各样的问题，那么HashSet如何判断元素重复呢？

    • HashSet集合通过equals和HashCode连个方法来判断两个元素是否相等，具体规则是：
      • 调用元素HashCode方法获得哈希码，判断哈希码是否相等，不相等则录入
      • 相等的话，再判断equals方法是否返回true，如果为true则不录入，如果为false则录入
    • 所以如果要将自定义的类装入Set集合中，需要重写HashCode和equals方法，这样才能保证装入Set中的元素具有独一性

  5. LinkedHashSet的特性：

    LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候既要计算HashCode的值，又要维护链表，而遍历的时候只需要按照链表来访问元素，查看LinkedHashSet的源码发现它是一样的。由此可知，LinkedHashSet本质上也是从LinkedHashMap而来，LinkedHashSet的所有方法都继承自HashSet,他能维持元素的插入顺序的性质则继承自LinkedHashMap

  6. TreeSet的特性：

    TreeSet会调用compareTo方法比较两个元素的大小，然后按照升序排序，所以自然排序中的元素对象，都必须 实现了CompareTo接口，否则会抛出异常，对于TreeSet判断元素是否重复的标准，也是调用元素从Comparable接口继承而来的compareTo方法，如果放回0，则是重复元素。Java中常见的类都已经实现了Comparable接口。并且TreeSet中只允许存入同一类的元素。

  7. TreeSet是依靠TreeMap实现的，TreeSet集合中元素将按照升序排列，缺省是按照自然顺序进行排列，以为着TreeSet中元素要实现Comparable接口，我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。

  8. 几种Set的比较：

    1. HashSet外部无序的遍历成员。成员可为任意Object类型的子类的对象，但如果覆盖了equals方法，同时注意修改hashCode方法。
    2. TreeSet外部有序的遍历成员。附加实现了SortedSet，支持子集等要求顺序的操作
    3. 成员要求实现Comparable接口，或者使用Comparator构造TreeSet。成员一般都为同一类型。
    4. LinkedHashSet外部按成员的插入顺序遍历成员。成员和HashSet成员类似
    5. HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能的时候，我们才使用TreeSet
    6. HashSet的元素存放顺序和我们添加进去的顺序没有任何关系，而LinkedHashSet则保持元素的添加顺序。TreeSet则是对我们的Set中的元素进行排序存放。

  9. 几种Set集合性能分析

    1. HashSet和TreeSet是Set集合中用的最多的集合。HashSet总是比TreeSet集合性能更好，因为HashSet不需要额外维护元素的顺序。
    2. LinkedHashSet需要用额外的链表维护元素的插入顺序，因此在插入时性能比HashSet低，但在迭代访问是想能更高，因为插入的时候既要计算ha’sh’Code又要维护链表，而访问的时候只需要按照链表来访问元素。
    3. EnumSet元素是所有Set元素中性能最好的，但是它只能保存Enum类型的元素。

Map的子接口

Map接口—>实现类：HashMap、TreeMap、LinkedHashMap、Hashtable等

它提供了一组键值的映射。其中存储的每个对象都有一个相应的关键字（key)，关键字决定了对象在Map集合中的存储位置。

关键字应该是唯一的，每一个key只能映射一个value。

Map集合

  1. 实现类：

    1. HashMap：键值对，key不能重复，但是value可以重复，key的实现就是HashSet；value对应着放；允许null的键或者值。
    2. HashTable：线程安全的，不允许null的键或者值。
    3. Properties：key和value都是String类型，用来读配置文件。
    4. TreeMap：对key排好序的Map，key就是TreeSet，value对应每一个key，key要实现Comparable接口或者TreeMap有自己的构造器。
    5. LinkedHashMap：此实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。存储的数据是有顺序的。

  2. HashMap：

    1. Map主要存储键值对，根据键得到值，因此键不允许重复，但允许值重复。
    2. HashMap是一个最常用的Map，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。
    3. HashMap：最多只允许一条记录的键为null。允许多条记录的值为null。
    4. HashMap：不支持线程的同步，即任一时刻可以有多个线程同时写HashMap；可能会导致数据的不一致，如果需要同步，可以用Collections的synchronizedMap方法使HashMap具有同步的能力。

  3. HashMap实现原理:

    Hash哈希算法的意义在于提供了一种快速存储数据的方法，它用一种算法建立键值与真实值之间的对应关系。散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。

    当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除，在Java语言中通过负载因子来决定何时对散列表进行再散列。

  4. Map集合比较：

    1. HashMap的存入顺序和输出顺序无关。
    2. LinkedHashMap则保留了键值对的存入顺序。
    3. TreeMap则是对Map中的元素进行了排序
    4. 因为HashMap和LinkedHashMap存储数据的速度比直接使用TreeMap要快，存取效率要高。当我们完成了所有的元素的存放之后，我们再对整个的Map集合进行排序，这样可以提高整个程序的运行的效率，缩短执行时间。

  5. HashMap与TreeMap联系与区别

    1. HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。
    2. 在Map 中插入、删除和定位元素，HashMap是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。
      两个map中的元素一样，但顺序不一样，导致hashCode()不一样。

  6. Map常用的方法：

    1. Object put(Object key,Object value):用来存放一个键值对到Map中
    2. Object remove(Object key):根据key(键),移除键值对,并将值返回
    3. void clear():清空当前Map中的元素
    4. Object get(Object key):根据key取得对应的值
    5. boolean containsKey(Object key):判断Map中是否存在某键(key)
    6. boolean containsValue(Object value):判断Map中是否存在某值
    7. public Set keySet():返回所有的键,并使用Set容器存放
    8. public Collection values():返回所有的值,并使用Collection存放
    9. public Set entrySet():返回一个实现Map.Entry接口的元素Set

集合的遍历

  1. List集合的遍历:

    1. 使用普通for循环,每次调用get()方法获取每一个索引的值的方式遍历整个集合

    2. 增强for循环遍历整个集合(本质上还是调用的Iterator迭代器)

    3. 迭代器的方式Iterator<String> it = list.iterator();while(it.hasNext()){it.next();}

    4. 转数组进行遍历list.toArray();for();
  2. Set集合的遍历:
    1. 三种方式:因为Set集合是无序的所以比List集合少了第一种通过普通for循环方式遍历的方法
  3. Map集合的遍历:
    1. 通过获取所有的Key的Set集合,按照key来遍历:map.keySet();然后遍历整个Set集合,通过get方法获取value
    2. 直接遍历所有的value,但不能遍历key:map.values()
    3. Set<Map.Entry<K,V>> entrySet()返回此映射中包含的映射关系的 Set 视图,然后遍历整个Set集合,得到每一个entrySet对象,通过每一个entrySet对象的getKey()和getValue()方法获取对应的值

获取集合中最大的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.ArrayList;
import java.util.List;
 
public class Test {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(12);
        list.add(34);
        list.add(5);
        list.add(123);
        list.add(89);
 
        int min = Integer.MAX_VALUE; // 用于记录列表中的最小值
        int max = Integer.MIN_VALUE;// 用于记录列表中的最大值
        for (Integer integer : list) {
            if (integer < min) {
                min = integer; // 遍历找出最小值
            }
            if (integer > max) {
                max = integer; // 遍历找出最大值
            }
        }
        System.out.println("最小值是：" + min + "，最大值是：" + max);
    }
}

ArrayList list = new Arraylist();

  1. ArrayList获取最大元素？

    int maxElement = Collections.max(list);

  2. ArrayList获取最大元素索引？
    //此处注意，当list为空时，会抛出空指针异常，因此需要先进行list是否为空的判断

    int indexOfMaxElement = list.indexOf(Collections.max(list));

集合简记

Thanks!