HashSet与TreeSet详解

先介绍下Java中的集合的概念

1.集合是JavaAPI所提供的一系列类,用来动态存放多个对象----集合只能存放对象

2.集合与数组的区别是,集合长度可变,且存放元素不受限定,主要是引用类型。

3.集合全部支持泛型,是一种数据安全的用法

集合框架图

集合分两大家族:

Collection(接口)家族:存放单一对象

Map(接口)家族:存放键值对(key,value)

先说Collection(接口)家族

Collection接口定义了存取对象的方法,它有两个很常用的子接口

List接口:存放的元素有序且重复

Set接口:存放的元素无序且唯一

List接口的两个重要实现类:ArrayList和LinkedList

这个不是我们要说的重点,就不多BB了,反正想用集合但不知道用什么集合,那就用ArrayList。

Set接口的两个重要实现类:HashSet和TreeSet

下面看看他们的具体存储原理:

HashSet

图中简单模拟了下hash算法,即数字转为二进制后与一串特定的二进制序列相与,得到hashcode。

对!你也许已经发现了:

不同数字的hashcode可能是相同的,在图中也可以看到hashcode相同时,元素是以链表的形式存放在该位置的。

相同数字的hashcode必然相同,比较相同元素的过程被大大简化。

下面我们来检测下HashSet存放元素的唯一性

  public class Test {

public static void main(String[] args) {

Set<Integer> set = new HashSet<>();

set.add(11);

set.add(22);

set.add(44);

set.add(11);

System.out.println(set);

//=======遍历1:基本for-无下标不能使用

//-----------增强for(实现原理就是迭代器)

System.out.println();

for(Integer a:set)

System.out.print(a+"-");

System.out.println();

//迭代器

Iterator<Integer> it = set.iterator();

while (it.hasNext()) {

System.out.print(it.next()+"-");

}

}

}

HashSet确实去掉了重复元素11

这里存放的是Integer类型对象,那么如果存放我们自己定义的对象呢?

定义一个Teacher类:

public class Teacher {

private String name;

private int age;

public int getAge() {

return age;

}

public void setAge(int age) {

this.age = age;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

@Override

public String toString() {

return "Teacher [name=" + name + age+"]";

}

public Teacher() {

super();

// TODO Auto-generated constructor stub

}

public Teacher(String name, int age) {

super();

this.name = name;

this.age = age;

}

}

我们再来测试下:

public class Test2 {

public static void main(String[] args) {

Set<Teacher> set = new HashSet<>();

set.add(new Teacher("苍老师",18));

set.add(new Teacher("陈老师",18));

set.add(new Teacher("苍老师",18));

System.out.println(set);

}

}

输出结果:

这次输出了两个苍老师,HashSet居然没有去重。

这是为什么呢?

我们注释掉Teacher类中的toString方法,再看下输出

我们看下输出,可以发现输出的对象地址都是不同的(尽管存放的都是苍老师)

因为我们存放的元素是对象,而不同的对象其地址肯定是不同的,而hashcode也是用地址去计算的,不同地址计算出来的hashcode当然也不同。

那么问题来了,我们上面存放的Integer对象,为什么就没出现这样的问题呢?

我们看下Integer类的源码

  public Integer(int value) {

            this.value = value;

        }

    @Override

        public int hashCode() {

            return Integer.hashCode(value);

        }

  public boolean equals(Object obj) {

        if (obj instanceof Integer) {

            return value == ((Integer)obj).intValue();

        }

        return false;

    }

原来Integer类内部悄悄重写了hashcode和equals方法,改为用value值去获取hashcode和比较。

那么给我们的Teacher类也实现hashcode和equals方法吧。

但怎么实现呢,大佬可以参照源码实现的方式自己写。

懒人方法:eclipse已经给我们提供自动实现了,就和getter和setter方法一样,按下alt+shift+s,即可看到Generate hashCode() and equals()选项,一键点击即可在我们自己写的类里实现hashSet的去重功能。

再来测试下:

可以看到,我们终于去掉了重复的苍老师。

下面重点来了:

TreeSet

先了解下TreeSet的存储方式

由于TreeSet的存储特性,可知TreeSet存储特点是唯一且有序。

和前面一样,我们先来测试Java自定义的Integer类对象及TreeSet的遍历

public class Test {

public static void main(String[] args) {

Set<Integer> set = new TreeSet<>();

set.add(1);

set.add(3);

set.add(2);

set.add(1);//唯一

System.out.println(set);

//遍历也是不能用基本for

//可以进行增强for和迭代器遍历

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

for(Integer i:set){

System.out.println(i);

}

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

Iterator<Integer> it = set.iterator();

while (it.hasNext()) {

System.out.println(it.next());

}

}

}

输出:

可以看到TreeSet不仅实现了去重,还进行了升序排序。

那么将Integer类对象换为我们定义的Teacher对象呢

public class Test2 {

public static void main(String[] args) {

Set<Student> set = new TreeSet<>();

//ClassCastException: Student cannot be cast to Comparable

set.add(new Student("zs",20));

set.add(new Student("ls",30));

set.add(new Student("ww",20));

set.add(new Student("zs",80));

System.out.println(set);

}

}

这次不仅仅是无法去重排序了,直接报了个Bug。

那该如何解决呢?

和之前一样,看下Integer类源码

public final class Integer extends Number implements Comparable<Integer> {

public int compareTo(Integer anotherInteger) {

        return compare(this.value, anotherInteger.value);

    }

}

原来Integer类实现了Comparable接口里的compareTo方法,

compareTo是Comparable接口定义的方法,那么里面调用的compare方法又是什么呢?

由于Integer类连compare方法都重写了,那该如何查看compare方法源码呢

这里补充个知识点,HashSet和TreeSet都是调用Map家族下的HashMap和TreeMap中的方法来实现的,所以我们得去TreeMap中找compare源码

final int compare(Object k1, Object k2) {

        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)

            : comparator.compare((K)k1, (K)k2);

    }

这是个三目运算,当comparator为空时,执行第一个表达式,否则执行第二个表达式。

即实现了comparator接口的话,就调用其compare方法实现比较大小;而未实现comparator接口就调用comparable接口的compareTo方法。

也就是说源码给我们提供了两种比较方法,一种是实现comparator接口,另一种是实现comparable接口,这也就是我们所说的比较器法和自然排序法。

自然排序法

方式1:自然排序法------》自定义类实现Comparable接口

public class Student implements Comparable{

private String name;

private int age;

public int getAge() {

return age;

}

public void setAge(int age) {

this.age = age;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

@Override

public String toString() {

return "Student [name=" + name + ", age=" + age + "]";

}

public Student() {

super();

// TODO Auto-generated constructor stub

}

public Student(String name, int age) {

super();

this.name = name;

this.age = age;

}

@Override

public int compareTo(Student o) {

if(o.age==this.age)

return o.name.compareTo(this.name);//升序

//return o.name.compareTo(this.name);//降序

return o.age - this.age; //按年龄降序,相同则按名字首字母升序排列

    }

}

方式2:比较器法------》自定义实现比较器comparator类

这里用匿名内部类实现:

//匿名内部类

Map<Student, Integer> map3 = new TreeMap<>(new Comparator<Student>() {

@Override

public int compare(Student o1, Student o2) {

if(o1.getName().equals(o2.getName()))

return o1.getAge()-o2.getAge();

return o1.getName().compareTo(o2.getName());

}

});

虽是TreeMap集合,但TreeSet与其除相差无几

Map集合中的HashMap、TreeMap与上面说的HashSet、TreeSet实现方式大致相同。

值得一提的就是Map集合的遍历了

//遍历

Set<String> set1 = map.keySet();

for(String a:set1){

System.out.println(a+" "+map.get(a));

}

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

//键值对遍历

Set<Entry<String, Integer>> set = map.entrySet();

Iterator<Entry<String, Integer>> it = set.iterator();

while (it.hasNext()) {

Entry<String, Integer> entry = (Entry<String, Integer>) it.next();

System.out.println(entry.getKey()+"-->"+entry.getValue());

}

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 222,946评论 6 518
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 95,336评论 3 399
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 169,716评论 0 364
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 60,222评论 1 300
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 69,223评论 6 398
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,807评论 1 314
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 41,235评论 3 424
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 40,189评论 0 277
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,712评论 1 320
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,775评论 3 343
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,926评论 1 353
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,580评论 5 351
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 42,259评论 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,750评论 0 25
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,867评论 1 274
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 49,368评论 3 379
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,930评论 2 361

推荐阅读更多精彩内容

  • 一. Java基础部分.................................................
    wy_sure阅读 3,815评论 0 11
  • DAY 05 1、 public classArrayDemo { public static void mai...
    周书达阅读 689评论 0 0
  • 一、Set Set:Collection 的子接口。 Set 规范的要求:要求 元素无序,不重复。 Set:1:H...
    fe0180bd6eaf阅读 236评论 0 1
  • 一、为什么会出现集合类 1.集合是一个容器,为了方便的对多个对象进行操作。 2.集合容器同数组容器的...
    大禹编程扛把子阅读 582评论 0 0
  • 一、基础知识:1、JVM、JRE和JDK的区别:JVM(Java Virtual Machine):java虚拟机...
    杀小贼阅读 2,391评论 0 4