Java 容器之Hashset 详解.

ゞ浴缸里的玫瑰 2022-08-27 10:56 140阅读 0赞

在之前的博文中本屌已经介绍过java的Collection接口.

作为实现了Collection接口的容器中, List容器无疑是最常用的, 无论是Arraylist, Linklist, Vector 都不难理解.

我们已经知道List容器的特点就是其里面的元素是有序的, 而且允许放入重复的元素.

## 一, 实现Set接口的容器. ##

跟List接口一样, Set接口也是继承自Collection接口.

实现Set接口的容器可以与数学上的"集合" 概念相对应.

但是实现Set接口的容器的元素是没有顺序的, 而且不会存有 **多个重复的元素**.

### 1.1 为何需要set容器 ###

咋一看, 对比list容器,  Set容器的两个特点都是缺点啊.

例如Set容器里的元素没有顺序, 就导致Set容器没有List容器的两个很常用的方法,  set(index)  和 object get(index).

因为set() 方法和get()方法都需要1个序号(index)作为参数, 告诉List容器到底想存取哪1个对象.

但是Set()没有index这东西(因为元素无序), 所以自然就没有set(index) 和 get(index) 方法了.

那么Java中Set容器的意义何在呢?

答案很简单, 因为现实中有一些东西很适合用Set容器来模拟.

例子1:

电视台安排节目单,   节目单里的节目必须是有序的, 一个节目播完才到下1个,  而且同1个节目可以出现在节目单多个不同的位置(重播).

那么电视节目单在coding中, 就应该用List容器来模拟了.

而且当节目单某1个节目被其他节目替换时, set(index)方法就发挥作用.

当想获得节目单某个特定位置的节目时,  get(index)就适用了.

例子2:

但是显示中也有一些容器是不需要次序, 而且不允许重复元素的,  1个最简单的例子就是足球教练选拨国家队成员.

国家队就像1个Set容器,  里面的队员没必要按任何顺序排列(元素无序), 而且国家队也不允许同1个队员占用两个位置(不允许重复元素).

所以在生产中, 如果需要1个元素无序, 不允许重复的容器,   请选择Set容器.

### 1.2 Set容器的常用方法. ###

Set接口继承自Collection接口,  并没有提供额外的方法, 但是具有下列继承自Collection接口的方法:

我们用回上面国家队的例子解释.

**boolean add(Object o)**

就如国家领队选拨1个球员作为国家队员,  作为1个容器, add方法是必须具有的.

**void clear()**

相当于领队遣散国家队, 过一段时间重新选人.

**boolean contains(object o)**

判断国家队中是否包括某个球员, 也就是判断1个球员是否国家队员..

**boolean isEmtpy**

判断国家队是否为空.

**boolean remove(Object o)**

把1个队员踢出国家队, 前提是这个队员本来就存在与国家队中, 否则返回False

**int size()**

返回当前国家队员的数量.

## 二, HashSet 简介以及优点. ##

Java中是没有Set这个容器的, Set只是1个接口.

Java有两个常用的实现了Set接口的容器, 1个就是HashSet, 另1个是TreeSet. 本文Focus on HashSet.

HashSet 作为1种Set容器, 自然包含了上述提到的各种方法.

但是大家其实可以发现,  Hashset容器的方法其实都可以在List容器找到替换的方法.

例如ArrayList 容器也有 contains(Object o), remove(Object o) 的方法.

也就是说, 在coding中, HashSet的方法完全可以用ArrayList来取代.

但是HashSet自然有它的优点. 这个优点就是访问数据的性能.

就比如同于同1个方法boolean contains(Object o),  无论是ArrayList 还是 LinkList, 都是需要遍历List的, 值到找到该元素为止.

**而HashSet是基于Hashcode() 找到该元素的位置, 大大减少(非避免)遍历的行为.**

## 三, HashSet 的内存存储结构. ##

### 3.1 Java 里 List的存储结构. ###

我们知道, 无论是ArrayList, 还是 LinkList, 它们的元素都是一块一块存放地址的内存, 存放的地址再指向各个不同的对象.

如图:

![444127020140531134712074.png_950x452_130][]

上面左边的内存块就是Java里的一段ArrayList的内存, 它存放了5个元素(对象地址), 指向了4个对象.   因为List中第2个地址和第4个地址都指向同1个对象object2,  所以相当于object2在List存放了2次.

如果要判断object4是否在List存在, 则很可能从List第1个位置向后逐个遍历.

当然Collections类中提供了2分查找法的静态方法, 但是前提是List中的元素必须排序, 而排序是比遍历更耗成本的操作.

### 3.2 Java 里 HashSet的存放机制(add) ###

HashSet 里的存储结构跟List的存储结构完全不同.

假如一段Hashset中含有10个内存位置(并一定是连续的),  而我要将1个对象object1 放入1个HashSet中.

如果要大概分成下面若干个步骤:

#### 3.2.1 第一步: 根据object1的hashCode()方法获得hashCode()的返回值, 经过算法后获得object1在HashSet中的位置. ####

看下图:

假如一段Hashset中含有10个内存位置(并一定是连续的),  而我要把object1存放到HashSet中.

![444127020140531141031064.png_514x483_130][]

**假如经过hashCode()的计算, 这个object1应该存入位置3中.**

值得注意的是, 不同的hashCode值经过算法转换后, 有可能得到同1个位置, 也就表明HashSet中位置3可能已经存在数据了!

#### 3.2.2 第二步情况1: 假如Hashset中的位置3是空的 ####

经过第1步, **根据hashCode()**的转换计算出位置是3.    java并不会直接把object1的地址写入位置3中.

首先会判断位置3的内容是否为空.

**如果是空的话, 仍然不会直接将object1的地址写入.**

而是新建1个LinkList(链表),  将object1的地址写入到链表的第1个位置, 然后将链表的头部地址写入到位置3中.

如下图:

![444127020140531143830094.png_801x472_130][]

###     ###

#### 3.2.2 第二步情况2: 假如Hashset中的位置3不是空的, 而是已经存在一条链表. ####

那么Java会逐个遍历这条LinkList(所以说还是回遍历),  逐个 **利用equals()方法**来跟要插入的object1比较.

1. 假如发现里面其中1个对象 object2.equals(object1) == 1.   那么java就回认为object2 跟 object1是重复的元素. 不会将object1 放入HashSet容器中.

![444127020140531150154057.png_847x506_130][]

2. 假如遍历Linklist所有元素后, 都没发现重复的对象, 那么就将object1 放到该LinkList的尾部.

![444127020140531150650058.png_804x460_130][]

### 3.2 Java 里 HashSet的查找机制(例如 contains()) ###

上面已经介绍过对象是怎样存放入HashSet容器中的了.

那么如何查找1个对象是否在HashSet容器中存在呢?

无非也是分两步.

1. 首先根据对象的 **hashCode** 获得 应该在HashSet的位置.

2. 遍历HashSet中对应位置的链表, 如果存在1个对象o , 且o. **equals**(要放入的对象)是真(即使o是另1个对象), 则认为该对象在链表中存在.

### 3.3 小结: Java 里 HashSet的本质 ###

通过上面的分析,  我们可以得出HashSet在内存中的存放本质.

参考下图:

![444127020140531152959068.png_650x526_130][]

1.,  HashSet实际上存放的是多个子链表, 这些子链表的元素再指向各个对象.

2.   HashSet 各个位置的子链表长度(对象个数)是差不多的, 因为Hash另1个名称是"散列", 所谓散列就是分散均匀分布的意思. 这取决与HashCode的转换算法.

3.  HashSet 根据对象的hashCode()来决定对象在HashSet里的位置(哪一条链表), 但是不同hashCode值的对象可能存在同1个位置(链表)中.

4. HashSet 根据对象的equals()方法来判断两个对象是否重复, 也就是说两个不同的对象只要ob1.equals(ob2) == True, HashSet 就回认为 ob1 与 ob2 重复.

5. HashSet查找1个对象, 只需要遍历其中1个子链表, 而不需要遍历整个容器, 所以如果存在大量无序数据.  HashSet的访问性能会比List容器高.

## 四, HashSet的对象必须同时重写对象的hashCode 和  equals() 方法. ##

很多人都会get到这个建议:  放入HashSet容器的对象, 最好重写其hashCode() 和 equals()方法.

这里就详细解释重写这两个方法的原因.

下面是1个简单例子:

import java.util.HashSet;
    
    class Student{
        private int id;
        private String name;
    
        public Student(int id, String name){
            this.id = id;
            this.name = name;
        }
    
        //overwrite
        public String toString(){
            return this.id + ":" + this.name;
        }
    }
    
    public class Hashset1{
        public static void f(){
            HashSet hs = new HashSet();
            hs.add(1);
            hs.add(2);
            hs.add(1);
            hs.add(1);
    
            System.out.println(hs);
            hs.clear();
    
            hs.add(new Student(1,"Jack"));
            hs.add(new Student(2,"Bill"));
            hs.add(new Student(1,"Jack"));
            hs.add(new Student(1,"Jack"));
            
            System.out.println(hs);
        } 
    }

上面简单定义了1个class Student, 只有两个成员id和name.

在下面的启动方法f()中, 首先向1个HashSet容器hs放入4个int 元素(实际上被自动装箱成Integer对象),  然后输出hs所有元素

接着清空容器, 放入4个Student对象. 其中3个对象的id和 name都是相同的(1, "Jack"), 再输出这个元素.

输出如下:

[java] [1, 2]
     [java] [1:Jack, 1:Jack, 1:Jack, 2:Bill]

可见, 第一次输出1 和 2 符合了Set容器不放入重复元素的原则.

但是第次输出, 输出了3个 1: Jack    ... 符合了无序的原则, 但是貌似允许重复数据啊.

其实原因很简单, 我们是用new Student()方法来构建1个对象的, 所以我们实际上放入了3个不同的对象, 即使3个对象的id和name属性都一样.

而java是根据这3个对象的hashCode()值来决定对象在HashSet的位置的.

而Student对象的hashCode()方法继承自基类.    返回1个跟内存地址有关的十六进制字符.

也就是说那3个1:Jack的对象因为内存地址不同, 返回的hashCode()不同,  就很可能处于HashSet容器的不同子链表中.

如下图:

![444127020140531164151081.png_804x516_130][]

### 4.1 重写对象的hashCode()方法. ###

假如我们想避免这种id name相同的重复元素, 则必须做到:

** 假如对象的id 和 name一样, 则对象的hashCode() 必须相等.**

所以我们可以重写hashCode()方法:

令其返回    id \*  name.hashCode()

值得注意的是, Student类 的 name 成员是1个String对象, 而String对象是重写过hashCode()的, 也就是说两个不同String对象, 只要各各字符相同, 其hashCode()就一样.

所以 id \* name.hashCode() 能保证当id 和 name 一样的话, Student的hashCode()就一样.

注意: 并不能保证当两个Student对象的id 和 name不一样, 它们的hashCode也不一样哦.

修改后的代码如下:

import java.util.HashSet;
    
    class Student{
        private int id;
        private String name;
    
        public Student(int id, String name){
            this.id = id;
            this.name = name;
        }
    
        //overwrite
        public String toString(){
            return this.id + ":" + this.name;
        }
    
        //overwrite hashCode()
        public int hashCode(){
            return id * name.hashCode();
        }
    
    }
    
    public class Hashset1{
        public static void f(){
            HashSet hs = new HashSet();
            hs.add(1);
            hs.add(2);
            hs.add(1);
            hs.add(1);
    
            System.out.println(hs);
            hs.clear();
    
            hs.add(new Student(1,"Jack"));
            hs.add(new Student(2,"Bill"));
            hs.add(new Student(1,"Jack"));
            hs.add(new Student(1,"Jack"));
            
            System.out.println(hs);
        } 
    }

修改后的输出:

[java] [1, 2]
     [java] [2:Bill, 1:Jack, 1:Jack, 1:Jack]

貌似问题还是没解决啊.

其实根据本文3.2.2 小节就知道原因.

虽然这个三个 1 Jack的对象被分配到HashSet同1个位置中.  HashSet 还是把这个3个对象放在同1个链表中了.

因为Student对象的equals()方法 也是继承自基类Object的.  是比较对象的内存地址...

所以HashSet容器会认为它们3个是不同的元素放在同1个链表中了,  (hashCode()相同).

如下图:

![44412702014053117044609.png_916x507_130][]

### 4.2 重写对象的equals()方法. ###

所以除了hashCode() 之外,  放入HashSet容器的类还应该重写equals()方法.

重写的逻辑也很简单:

只要让id 和 name相等的两个对象相等就ok了.

修改后的代码如下:

import java.util.HashSet;
    
    class Student{
        private int id;
        private String name;
    
        public Student(int id, String name){
            this.id = id;
            this.name = name;
        }
    
        //overwrite
        public String toString(){
            return this.id + ":" + this.name;
        }
    
        //overwrite hashCode()
        public int hashCode(){
            return id * name.hashCode();
        }
    
        //overwrite equals()
        public boolean equals(Object o){
            Student s = (Student)o;
            return (s.id == this.id) && (s.name.equals(this.name));
        }
    
    }
    
    public class Hashset1{
        public static void f(){
            HashSet hs = new HashSet();
            hs.add(1);
            hs.add(2);
            hs.add(1);
            hs.add(1);
    
            System.out.println(hs);
            hs.clear();
    
            hs.add(new Student(1,"Jack"));
            hs.add(new Student(2,"Bill"));
            hs.add(new Student(1,"Jack"));
            hs.add(new Student(1,"Jack"));
            
            System.out.println(hs);
        } 
    }

这时的输出:

[java] [1, 2]
    [java] [2:Bill, 1:Jack]

符合我们的要求了.

终上所述, 这就是为什么说:

**放入HashSet的对象最好同时重写hashCode() 和 equals()方法了.**

## 五, 小结: ##

从本质上将, HashSet将大量元素散列分为若干个子LinkList来存放数据,  大大减少了遍历的次数.

如果程序员需要1个容器来来存放大量无序的元素时, HashSet是1个很合适的选择.

[444127020140531134712074.png_950x452_130]: http://image16.poco.cn/mypoco/myphoto/20140531/13/444127020140531134712074.png?950x452_130
[444127020140531141031064.png_514x483_130]: http://image16.poco.cn/mypoco/myphoto/20140531/14/444127020140531141031064.png?514x483_130
[444127020140531143830094.png_801x472_130]: http://image16.poco.cn/mypoco/myphoto/20140531/14/444127020140531143830094.png?801x472_130
[444127020140531150154057.png_847x506_130]: http://image16.poco.cn/mypoco/myphoto/20140531/15/444127020140531150154057.png?847x506_130
[444127020140531150650058.png_804x460_130]: http://image16.poco.cn/mypoco/myphoto/20140531/15/444127020140531150650058.png?804x460_130
[444127020140531152959068.png_650x526_130]: http://image16.poco.cn/mypoco/myphoto/20140531/15/444127020140531152959068.png?650x526_130
[444127020140531164151081.png_804x516_130]: http://image16.poco.cn/mypoco/myphoto/20140531/16/444127020140531164151081.png?804x516_130
[44412702014053117044609.png_916x507_130]: http://image16.poco.cn/mypoco/myphoto/20140531/17/44412702014053117044609.png?916x507_130