Java基础之集合框架

  • 内容
  • 评论
  • 相关
Java集合框架提供了数据持有对象的方式,提供了对数据集合的操作。Java集合框架位 于 java.util 包下,主要有三个大类: Collection 、 Map 接口以及对集合进行操作的工具 类。

Collection

ArrayList :线程不同步。默认初始容量为10,当数组大小不足时增长率为当前长度 的 50% 。
Vector :线程同步。默认初始容量为10,当数组大小不足时增长率为当前长度 的 100% 。它的同步是通过 Iterator 方法加 synchronized 实现的。 LinkedList :线程不同步。双端队列形式。
Stack :线程同步。继承自 Vector ,添加了几个方法来完成栈的功能。
Set :Set是一种不包含重复元素的Collection,Set最多只有一个null元素。
HashSet :线程不同步,内部使用 HashMap 进行数据存储,提供的方法基本都是调 用 HashMap 的方法,所以两者本质是一样的。集合元素可以为 NULL 。
NavigableSet :添加了搜索功能,可以对给定元素进行搜索:小于、小于等于、大于、 大于等于,放回一个符合条件的最接近给定元素的 key。
TreeSet :线程不同步,内部使用 NavigableMap 操作。默认元素“自然顺序”排列,可以通过 Comparator 改变排序。
EnumSet :线程不同步。内部使用Enum数组实现,速度比 HashSet 快。只能存储在构造 函数传入的枚举类的枚举值。

 Map

  HashMap :线程不同步。根据 key 的 hashcode 进行存储,内部使用静态内部类 Node 的 数组进行存储,默认初始大小为16,每次扩大一倍。当发生Hash冲突时,采用拉链法 (链表)。可以接受为null的键值(key)和值(value)。JDK 1.8中:当单个桶中元素个数大 于等于8时,链表实现改为红黑树实现;当元素个数小于6时,变回链表实现。由此来防 止hashCode攻击。
LinkedHashMap :保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到 的记录肯定是先插入的. 也可以在构造时用带参数,按照应用次数排序。在遍历的时候会 比HashMap慢,不过有种情况例外,当HashMap容量很大,实际数据较少时,遍历起来 可能会比LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容 量无关,而HashMap的遍历速度和他的容量有关。
TreeMap :线程不同步,基于 红黑树 (Red-Black tree)的NavigableMap 实现,能够把 它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历TreeMap时,得到的记录是排过序的。
HashTable :线程安全,HashMap的迭代器(Iterator)是 fail-fast 迭代器。HashTable 不能存储NULL的key和value。

工具类

Collections 、 Arrays :集合类的一个工具类\/帮助类,其中提供了一系列静态方法, 用于对集合中元素进行排序、搜索以及线程安全等各种操作。
Comparable 、 Comparator :一般是用于对象的比较来实现排序,两者略有区别。
Comparable 自然排序

Comparable 在 java.lang 包下,是一个接口,内部只有一个方法 compareTo():

public interface Comparable<T> {
    public int compareTo(T o);
}

Comparable 可以让实现它的类的对象进行比较,具体的比较规则是按照 compareTo 方法中的规则进行。这种顺序称为 自然顺序

compareTo 方法的返回值有三种情况:

e1.compareTo(e2) > 0 即 e1 > e2

e1.compareTo(e2) = 0 即 e1 = e2

e1.compareTo(e2) < 0 即 e1 < e2

注意:

1.由于 null 不是一个类,也不是一个对象,因此在重写 compareTo 方法时应该注意 e.compareTo(null) 的情况,即使 e.equals(null) 返回 false,compareTo 方法也应该主动抛出一个空指针异常 NullPointerException。

2.Comparable 实现类重写 compareTo 方法时一般要求 e1.compareTo(e2) == 0 的结果要和 e1.equals(e2) 一致。这样将来使用 SortedSet 等根据类的自然排序进行排序的集合容器时可以保证保存的数据的顺序和想象中一致。

Comparator 定制排序

Comparator 在 java.util 包下,也是一个接口,JDK 1.8 以前只有两个方法:

public interface Comparator<T> {

    public int compare(T lhs, T rhs);

    public boolean equals(Object object);
}

JDK 1.8 以后又新增了很多方法:基本上都是跟 Function 相关的,这里暂不介绍 1.8 新增的。

从上面内容可知使用自然排序需要类实现 Comparable,并且在内部重写 comparaTo 方法。

而 Comparator 则是在外部制定排序规则,然后作为排序策略参数传递给某些类,比如 Collections.sort(), Arrays.sort(), 或者一些内部有序的集合(比如 SortedSet,SortedMap 等)。

使用方式主要分三步:

1、创建一个 Comparator 接口的实现类,并赋值给一个对象 ,在 compare 方法中针对自定义类写排序规则。

2、将 Comparator 对象作为参数传递给 排序类的某个方法

3、向排序类中添加 compare 方法中使用的自定义类

其实可以看到,Comparator 的使用是一种策略模式。

排序类中持有一个 Comparator 接口的引用:

Comparator<? super K> comparator;

而我们可以传入各种自定义排序规则的 Comparator 实现类,对同样的类制定不同的排序策略。

总结

Java 中的两种排序方式:

1、Comparable 自然排序。(实体类实现)

2、Comparator 是定制排序。(无法修改实体类时,直接在调用方创建)

Comparable是排序接口;若一个类实现了Comparable接口,就意味着“该类支持排序”。而Comparator是比较器;我们若需要控制某个类的次序,可以建立一个“该类的比较器”来进行排序。

我们不难发现:Comparable相当于“内部比较器”,而Comparator相当于“外部比较器”。

同时存在时采用 Comparator(定制排序)的规则进行比较。

对于一些普通的数据类型(比如 String, Integer, Double…),它们默认实现了Comparable 接口,实现了 compareTo 方法,我们可以直接使用。

而对于一些自定义类,它们可能在不同情况下需要实现不同的比较策略,我们可以新创建 Comparator 接口,然后使用特定的 Comparator 实现进行比较。

Object类中equals()与hashCode()

equals()和hasCode()是java.lang.Object类中有两个非常重要的方法.
Object类是类继承结构的基础,所以是每一个类的父类。所有的对象,包括数组,都实现了在Object类中定义的方法。
 equals()
 1、作用:用来判断两个对象是否相等。
2、equals() 与 == 的区别是什么?
1、==:
它的作用是判断两个对象的地址是不是相等。即,判断两个对象是不是同一个对象。
2、equals() :
它的作用也是判断两个对象是否相等。但它一般有两种使用情况:
(1).若某个类没有覆盖equals()方法,当它的通过equals()比较两个对象时,实际上是比较两个对象是不是同一个对象。这时,等价于通过“==”去比较这两个对象。
(2).我们可以覆盖类的equals()方法,来让equals()通过其它方式比较两个对象是否相等。通常的做法是:若两个对象的内容相等,则equals()方法返回true;否则,返回fasle。
3、性质
(1)自反性(reflexive)。对于任意不为null的引用值x,x.equals(x)一定是true
(2)对称性(symmetric)。对于任意不为null的引用值xy,当且仅当x.equals(y)true时,y.equals(x)也是true
(3)传递性(transitive)。对于任意不为null的引用值xyz,如果x.equals(y)true,同时y.equals(z)true,那么x.equals(z)一定是true
(4)一致性(consistent)。对于任意不为null的引用值xy,如果用于equals比较的对象信息没有被修改的话,多次调用时x.equals(y)要么一致地返回true要么一致地返回false
(5)对于任意不为null的引用值xx.equals(null)返回false
4、注意
1、我们知道,String 、Math、Integer、Double等这些封装类在使用equals()方法时,已经覆盖了object类的equals()方法。查看源码后知道,是进行的内容比较,而已经不再是地址的比较。当然,基本类型是进行值的比较。
2、重新equals()方法后,一定要重写hashCode()方法,否则会引起一些意想不到的错误
hashCode()
 1、作用:获取哈希码,也称为散列码;它实际上是返回一个int整数。这个哈希码的作用是确定该对象在哈希表中的索引位置。
 hashCode() 定义在JDK的Object.java中,这就意味着Java中的任何类都包含有hashCode() 函数。
虽然,每个Java类都包含hashCode() 函数。但是,仅仅当创建并某个“类的散列表”(关于“散列表”见下面说明)时,该类的hashCode() 才有用(作用是:确定该类的每一个对象在散列表中的位置;其它情况下(例如,创建类的单个对象,或者创建类的对象数组等等),类的hashCode() 没有作用。
上面的散列表,指的是:Java集合中本质是散列表的类,如HashMap,Hashtable,HashSet。
也就是说:hashCode() 在散列表中才有用,在其它情况下没用。在散列表中hashCode() 的作用是获取对象的散列码,进而确定该对象在散列表中的位置。
 hashCode() 和 equals() 的关系
 1. 第一种 不会创建“类对应的散列表”
这里所说的“不会创建类对应的散列表”是说:我们不会在HashSet, Hashtable, HashMap等等这些本质是散列表的数据结构中,用到该类。例如,不会创建该类的HashSet集合。
在这种情况下,该类的“hashCode() 和 equals() ”没有半毛钱关系的!
这种情况下,equals() 用来比较该类的两个对象是否相等。而hashCode() 则根本没有任何作用,所以,不用理会hashCode()。
2. 第二种 会创建“类对应的散列表”
这里所说的“会创建类对应的散列表”是说:我们会在HashSet, Hashtable, HashMap等等这些本质是散列表的数据结构中,用到该类。例如,会创建该类的HashSet集合。
在这种情况下,该类的“hashCode() 和 equals() ”是有关系的:
1)、如果两个对象相等,那么它们的hashCode()值一定相同。这里的相等是指,通过equals()比较两个对象时返回true。
2)、如果两个对象hashCode()相等,它们并不一定相等。
因为在散列表中,hashCode()相等,即两个键值对的哈希值相等。然而哈希值相等,并不一定能得出键值对相等。补充说一句:“两个不同的键值对,哈希值相等”,这就是哈希冲突。
此外,在这种情况下。若要判断两个对象是否相等,除了要覆盖equals()之外,也要覆盖hashCode()函数。否则,equals()无效。
例如,创建Person类的HashSet集合,必须同时覆盖Person类的equals() 和 hashCode()方法。
如果单单只是覆盖equals()方法。我们会发现,equals()方法没有达到我们想要的效果。
How to override equals and hashCode

1、经典方式

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
26
27
28
29
30
31
32
33
public class User {
    private String name;
    private int age;
    private String passport;
 
	//getters and setters, constructor
 
    @Override
    public boolean equals(Object o) {
 
        if (o == this) return true;
        if (!(o instanceof User)) {
            return false;
        }
 
        User user = (User) o;
 
        return user.name.equals(name) &&
                user.age == age &&
                user.passport.equals(passport);
    }
 
    //Idea from effective Java : Item 9
    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + name.hashCode();
        result = 31 * result + age;
        result = 31 * result + passport.hashCode();
        return result;
    }
 
}

注意:不同类型hashCode值的计算可以采用如下公式。

Field类型 计算公式
boolean hashCode=(f?0:1);
整数类型(byte,short,char,int) hashCode=(int)f;
long hashCode=(int)(f^(f>>>32));
float hashCode=Float.floatToIntBits(f);
double long l=Double.doubleToLongBits(f);

hashCode=(int)(l^(l>>>32);

普通引用类型 hashCode=f.hashCode();

使用系数为31的原因如下:

  • 31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终的出来的结果只能被素数本身和被乘数还有1来整除!。(减少冲突)
  • 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化.(提高算法效率)
  • 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)
  • 并且31只占用5bits,相乘造成数据溢出的概率较小。

 2、JDK 7

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
26
27
28
import java.util.Objects;
 
public class User {
    private String name;
    private int age;
    private String passport;
 
	//getters and setters, constructor
 
    @Override
    public boolean equals(Object o) {
 
        if (o == this) return true;
        if (!(o instanceof User)) {
            return false;
        }
        User user = (User) o;
        return age == user.age &&
                Objects.equals(name, user.name) &&
                Objects.equals(passport, user.passport);
    }
 
    @Override
    public int hashCode() {
        return Objects.hash(name, age, passport);
    }
 
}

 3、Apache Commons Lang

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
26
27
28
29
30
31
32
33
34
35
36
import org.apache.commons.lang3.builder;
 
public class User {
    private String name;
    private int age;
    private String passport;
 
	//getters and setters, constructor
 
     @Override
    public boolean equals(Object o) {
 
        if (o == this) return true;
        if (!(o instanceof User)) {
            return false;
        }
 
        User user = (User) o;
 
        return new EqualsBuilder()
                .append(age, user.age)
                .append(name, user.name)
                .append(passport, user.passport)
                .isEquals();
    }
 
    @Override
    public int hashCode() {
        return new HashCodeBuilder(17, 37)
                .append(name)
                .append(age)
                .append(passport)
                .toHashCode();
    }
 
}