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

 

集合简介

集合可存储类型不同的对象，并可实现栈、队列等常用的数据结构。

集合的两个根接口：

• Collection 单列集合
• Map 双列集合，key唯一标识一个键值对，key不能重复

集合的实现类都重写了toString()方法。

Set

HashSet

按照hash算法来存储元素，元素无序、不可重复。

HashSet内部使用一个HashMap来存储元素，元素作为HashMap的key来存储。

hash，哈希，也叫作散列。hash算法的优势在于查找元素速度快，查找元素时根据hashCode确定存储位置，直接定位该元素。

 

HashSet添加元素的流程

先计算元素的hashcode确定元素的存储位置，如果该位置上没有元素，则加入该元素；如果该位置上有元素，调用equals()判断这2个元素是否相同，如果相同，则不添加该元素。  

为保证HashSet不存储重复的元素（一个位置只存储一个元素，保证性能），需要我们重写元素的hashCode()。如果不重写，HashSet可以存入该类相同的对象（相同是指对象内容相同，对象地址可以不同）。而重写hashCode()，又需要重写equals()。

jdk自带的类型（包括String、集合）基本都重写了hashCode()、equals()，如果我们要添加自定义类的对象到HashSet中，需要我们自己重写该类的hashCode()、equals()。

 

重写规则：如果equals()返回true，则这2个对象的hashCode()也应该相同。示例

@Setter@Getterpublic class User {
       private Long id;    private String username;    //.....    //重写hashCode(),使用唯一标识对象的字段的hashCode    @Override    public int hashCode() {
           return id.hashCode();    }    //重写equals()，Object的equals()是根据对象地址来判断，我们想要的是根据对象内容来判断    @Override    public boolean equals(Object object) {
           if (this == object)   //是否是同一对象            return true;        if (!(object instanceof User))  //是否是同一类型            return false;        //如果是同一类型        User obj = (User) object;   //强制类型转换，因为object可能是User子类的对象        return this.id.equals(obj.getId());  //根据唯一标识对象的字段来比较    }}

 

LinkedHashSet

LinkedHashSet是HashSet的子类，具有HashSet的所有性质，但LinkedHashSet内部使用一个链表保持元素的插入顺序，存储、查找元素仍是按hash算法进行，链表只用于遍历LinkedHashSet。

 

TreeSet

TresSet使用红黑树来存储元素，有序。

TreeSet的2种排序方式

• 自然排序　TreeSet默认的排序方式。数值型按数值大小排列，字符串按码值大小排列，Date、Time按时间戳大小排列…默认升序
• 定制排序　按我们自定义的规则排序

 

比较

• EnumSet性能最好，因为不维护什么，没有其他开销，但只用于存储枚举类的实例，应用不广泛

• HashSet次之，尤其是添加（存储）、查找元素性能很高

• TreeSet性能最差，因为要维护一棵红黑树

• HashSet的子类LinkedHashSet

  添加、查找元素时，LinkedHashSet内部要维护一个链表，有额外开销，性能低于HashSet；但正是由于链表，LinkedHashSet的遍历要比HashSet快

HashSet、TreeSet、EnumSet都不是线程安全的，当多个线程同时访问、修改同一个Set集合时，需要手动同步该Set集合，可通过Collections工具类的静态方法synchronizedXxx()来同步集合。

 

List

List用下标索引元素，有序，元素可重复。

ArrayList、Vector

ArrayList、Vector都是基于数组的，内部都封装了一个动态（长度可变）数组。

向ArrayList、Vector中添加元素，如果数组长度不够，会自动调用 ensureCapacity()扩容，如果要向ArrayList、Vector中添加大量元素，可以手动调用 ensureCapacity() 一次性扩容，减少扩容次数，提高性能。

ensureCapacity(int minCapacity)   //参数是数组的最小元素个数

Vector有一个子类Stack，用于模拟栈。

 

LinkedList

LinkedList不仅实现了List接口，还实现了Queue接口的子接口Deque。Queue接口用于模拟队列。

LinkedList基于链表，内部维护了一个链表，有序。

 

比较

ArrayList、Vector基于数组，LinkedList基于链表。

ArrayList不是线程安全的，当多个线程同时访问、修改同一个ArrayList集合时，需要手动同步该集合。Vector是线程安全的，这意味着额外开销，性能降低，尽管Vector线程安全，但缺点太多，一般不用。

 

ArrayList基于数组，get()、set()是随机存取，速度快；插入、删除元素时要移动大量元素，速度慢；适合多查找、更新值的场景。

LinkedList基于链表，操作元素要遍历链表，找到指定元素才停下，查询、更新元素值速度比ArrayList慢，但添加、删除元素时不用移动其它元素，速度比ArrayList快；适合多添加、删除的场景。

 

Map

Map使用内部类Entry来封装键值对，key、value都可以是任意类型，根据key来区分键值对，key不能重复。

HashMap

HashMap的key、value都可以是null。

如果要使用自定义的类作为key，需要重写自定义类的hashCode()、equals()来保证集合中没有重复的key。名字中带hash的集合都要这样。

 

LinkedHashMap是HashMap的子类，内部使用一个双向链表来维护键值对的顺序（与添加顺序相同），链表维护的是key。

 

Hashtable

Hashtable（t是小写）的key、value都不能是null。

Properties是Hashtable的子类，常用于处理属性文件，Properties的key、value都只能是String，常用方法如下

void  load(InputStream is)  //从属性文件（输入流）中加载键值对到Properties对象void store(OutputStream os, String info)  //把Properties中的键值对写到输出流中（属性文件）,第二个参数指定附加说明

 

TreeMap

TreeMap用红黑树来存储元素，有序，有2种排序方式：自然排序（默认）、定制排序。

 

比较

HashMap、Hashtable都无序，TreeMap红黑树有序。

Hashtable线程安全，额外开销；HashMap线程不安全，性能高于Hashtable。Hashtable毛病很多，一般不用。

TreeMap内部维护红黑树开销大，尤其是增删元素时，性能一般低于HashMap、Hashtable。

 

集合遍历

1、所有集合都可使用增强的for循环

HashMap hashMap;for (Object key:hashMap.keySet()){
       System.out.println(key+" --> "+hashMap.get(key));}

 

2、 所有集合都可使用forEach循环

HashSet hashSet;hashSet.forEach(ele->{
     //lambda表达式	//......});HashMap hashMap;hashMap.forEach((key,value)->{
   	//......});

 

3、Collection集合可使用Iterator（迭代器）进行遍历

HashSet hashSet;Iterator iterator=hashSet.iterator();while (iterator.hasNext()){
        System.out.println(iterator.next());}

 

• 遍历集合时，在循环体中不能使用集合本身的删除方法来删除元素，会发生异常。可以用另一个集合来保存需要的元素，或者用Stream来迭代集合。如果是用Iterator（迭代器），也可以使用Iterator类提供的remove()方法来删除元素。
• 使用迭代器遍历集合时，如果循环体内部又嵌套了迭代器，容易出问题，尽量用增强for循环代替迭代器。

 

操作集合的工具类Collections

Collections提供了操作集合的很多方法，包括查找最值、二分搜索、统计元素出现次数、替换、排序、反序、同步等，均为静态方法。

 

数组、List的相互转换

//集合转数组，使用list的成员方法toArray()List
   
     list = new ArrayList<>();list.add("张三");list.add("李四");list.add("王五");//写法一// String[] arr = list.toArray(new String[list.size()]);//写法二String[] arr = new String[list.size()];list.toArray(arr);//数组转集合，使用工具类Arrays的静态方法asList()// String [] arr = {"张三","李四","王五"};// List
    
      list = Arrays.asList(arr);
    
   

 

List的提取问题

str.substring();list.subList();

String、List都可以只提取部分，如果要指定(start, end)2个参数时，要特别注意以下2种情况

• start == end
• end > list或str的最大下标

end不是indexOf()获取的下标时，很容易出现这个问题，在使用sub函数前要对end进行判断，否则运行时sub函数可能会报错：end超出范围（下标越界）

 

集合的空值判断

字符串、数组、集合类型的变量，只要赋了new出来的对象，则一定不为null，判断时注意用==null还是.size|length来判断。

 

hash系列集合优化

hash系列集合：HashSet、LinkedHashSet、HashMap、LinkedHashMap，都是用hash表来存储元素，map是在hash表中存储key。

hash表中可以存储元素的位置称为bucket（桶）

一个bucket里只存储一个元素，此时可根据hashCode直接定位元素所在的bucket，获取元素，性能最好。

但hash表是open的，发生hash冲突时（插入元素的hashCode相同），一个bucket中会存储多个元素，这些元素以链表形式存储在一个bucket中，此时hash表性能会下降，根据hashCode确定bucket位置后，还要遍历链表，找到指定元素。

为避免hash冲突、得到不错的性能，我们需要重写hashCode()、equals()，保证hash表中没有重复元素，确保一个bucket中只存储一个元素。hashCode()中不要做很复杂的运算，影响性能。

 

hash系列集合（hash表）都有以下属性

• capacity　容量，hash表中bucket的总数
• loadFactor　负载因子，hash表的bucket最多允许使用多少，默认0.75
   

当hash表负载达到loadFactor（默认0.75）时：

会rehashing（重哈希/再散列），hash表自动成倍扩容（capacity），将原有元素都移到新hash表中，重新分配存储位置，而此时元素已经很多了，时间开销大。  

loadFactor较大时：空桶很多

添加元素时很容易找到空的bucket，存储性能高； 已存储元素的bucket少，很容易从中找到指定元素，查找性能高； 但遍历集合（hash表）时，要过滤掉大量空的bucket，花时间，遍历性能低。  

loadFactor较小时：空桶很少

查找、存储元素性能低，且容易发生rehashing。  

hash系列集合都有3个重载的构造函数

()      //无参(int capacity)   //指定初始容量(int capacity, float loadFactor )

通过调整capacity、loadFactor来提高hash表性能，一般loadFactor就使用默认的0.75，如果要查询、存储元素性能高，将容量设置大一些,，但容量也不要太大，太大会加大内存开销。

先估算元素总数大概是多少，假设为m，设置容量为：m/0.75，再往上加一些，避免rehashing，节省时间开销。且前中期hash表负载低，添加、查询元素效率高。

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