Set接口和HashSet类

来自CloudWiki
跳转至： 导航， 搜索

Set接口

Set集合类似一个罐子，程序可以一次把对象丢进Set集合，而set集合通常不能记住元素的添加顺序。并且没有重复的对象，如图6-3所示。

Java6-2.png

图6-3 set集合

Set接口常用的实现类有三个：

  • HashSet类是Set接口实现类之一，使用较广泛，它不保存元素的加入顺序。HashSet类根据元素的哈希码进行存放，取出时也可以根据哈希码快速找到。
  • LinkedHashSet类根据元素的哈希码进行存放，同时用链表记录元素加入的顺序。通过链表来存储对象，一般插入和删除效率较高，检索效率相对较低。
  • TreeSet类使用红黑树结构对加入的元素进行排序存放，通过TreeSet构造方法来获取TreeSet对象。

Set集合实现了Collection接口，方法与Collection基本上完全一样，它没有提供额外的方法。

实现类：HashSet

为啥要用HashSet?

   假如我们现在想要在一大堆数据中查找X数据。LinkedList的数据结构就不说了，查找效率低的可怕。ArrayList哪，如果我们不知道X的位置序号，还是一样要全部遍历一次直到查到结果，效率一样可怕。HashSet天生就是为了提高查找效率的。

HashSet 散列表的内部结构

Java5-102.jpg

hashCode 散列码

   散列码是由对象导出的一个整数值。在Object中有一个hashCode方法来得到散列码。基本上，每一个对象都有一个默认的散列码，其值就是对象的内存地址。但也有一些对象的散列码不同，比如String对象，它的散列码是对内容的计算结果.

HashSet 如何add机制

假如我们有一个数据(散列码76268)，而此时的HashSet有128个散列单元，那么这个数据将有可能插入到数组的第108个链表中(76268%128=108)。但这只是有可能，如果在第108号链表中发现有一个老数据与新数据equals()=true的话，这个新数据将被视为已经加入，而不再重复丢入链表。

为什么HashSet查找效率提高了。

  知道了HashSet的add机制后，查找的道理一样。直接根据数据的散列码和散列表的数组大小计算除余后，就得到了所在数组的位置，然后再查找链表中是否有这个数据即可。

  查找的代价也就是在链表中，但是真正一条链表中的数据很少，有的甚至没有。几乎没有什么迭代的代价可言了。所以散列表的查找效率建立在散列单元所指向的链表中的数据要少 。

HashSet的基本使用

Set用于存储不重复的元素集合，它主要提供以下几个方法： 

   将元素添加进Set<E>：boolean add(E e)
   将元素从Set<E>删除：boolean remove(Object e)
   判断是否包含元素：boolean contains(Object e)

HashSet是它的实现类。

引用接口

import java.util.* ;

初始化

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

增加元素

 set.add(5); //向集合中添加一个整数    	
    	set.add(4); //向集合中添加一个
    	set.add(3); //向集合中添加一个
    	set.add(2); //向集合中添加一个
    	boolean a1=set.add(1); //add和remove函数是有返回值的，
    	if(a1 == true) {//如果成功 ，返回true,否则返回false
    		System.out.println(1+"添加成功！");
    	}else {
    		System.out.println(1+"添加 失败！");
    	}

删除元素

 //删除元素
    	set.remove(1);
    	boolean a2 = set.remove(0);
    	if(a2 == true) {//如果成功 ，返回true,否则返回false
    		System.out.println(0+"删除成功！");
    	}else {
    		System.out.println(0+"删除失败！");
    	}

查找元素

   	
    	//查找元素
    	if(set.contains(4)){
    		   System.out.println("4存在于集合之中");
    	}else{
    		System.out.println("4不存在于集合之中");
    	}

遍历集合

   	//遍历集合
    	System.out.println("遍历集合：");
    	for(Integer i:set){
			System.out.print(i+" ");    	
	    }

试一试：Set练习

  • 在以上代码基础上，向Set中添加6,7,8
  • 删除7，8
  • 查找6是否存在
  • 重复添加7，7 ，看看集合有什么变化。

完整代码

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		HashSet<Integer> set = new HashSet<>();
    	//增加元素
    	set.add(5); //向集合中添加一个整数    	
    	set.add(4); //向集合中添加一个
    	set.add(3); //向集合中添加一个
    	set.add(2); //向集合中添加一个
    	boolean a1=set.add(1); //add和remove函数是有返回值的，
    	if(a1 == true) {//如果成功 ，返回true,否则返回false
    		System.out.println(1+"添加成功！");
    	}else {
    		System.out.println(1+"删除失败！");
    	}
    	    	
    	//删除元素
    	set.remove(1);
    	boolean a2 = set.remove(0);
    	if(a2 == true) {//如果成功 ，返回true,否则返回false
    		System.out.println(0+"删除成功！");
    	}else {
    		System.out.println(0+"删除失败！");
    	}
    	
    	//查找元素
    	if(set.contains(4)){
    		   System.out.println("4存在于集合之中");
    	}else{
    		System.out.println("4不存在于集合之中");
    	}
    	
    	//遍历集合
    	System.out.println("遍历集合：");
    	for(Integer i:set)
			System.out.print(i+" ");    	
	    }

}

HashSet的应用

HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是确定HashSet的哈希码，这是对象存储的关键。

确定哈希码后，先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等.并且 hashCode方法必须与equals方法向兼容。

Java5-102.jpg 

//hashCode与equals方法的兼容   
public class Employee{   
       public int id;   
       public String name="";   
       //相同id对象具有相同散列码   
       public int hashCode(){    
              return id;   
       }   
       //equals必须比较id   
        public boolean equals(Employee x){   
              if(this.id==x.id) return true;   
              else return false;   
       }  
}    

  为什么要这样，因为HashSet不允许相同元素(equals==ture)同时存在在结构中。假如employeeX(1111，“张三”)和employee(1111,"李四")，而Employee.equals比较的是name。这样的话，employeeX和employeeY的equals不相等。它们会根据相同的散列码1111加入到同一个散列单元所指向的列表中。这种情况多了，链表的数据将很庞大，散列冲突将非常严重，查找效率会大幅度的降低

如果我们没有重写这两个方法，将会使用这个方法的默认实现。

下面程序演示了Set集合的应用。

程序清单：book.java 

public class Book {
	private String id;
	private String name;
	public Book(String id, String name) {
		this.id = id;
		this.name = name;
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((id == null) ? 0 : id.hashCode());
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Book other = (Book) obj;
		if (id == null) {
			if (other.id != null)
				return false;
		} else if (!id.equals(other.id))
			return false;
		return true;
	}
	public String toString() {
		return "编号：" + id + ", 书名：" + name;
	}
}

程序清单TestSet 

public class TestSet {
	public static void main(String[] args) {
		Set<Book> books=new HashSet<>();
		//添加元素
		books.add(new Book("01","Think in java"));
		books.add(new Book("02", "java 讲义"));
		books.add(new Book("03", "java 语言程序设计"));
		//不能添加成功，Set集合不允许存在相等的元素
		books.add(new Book("03", "疯狂java讲义"));
		//Set集合遍历：
		for(Book b:books)
			System.out.println(b);
	}
}


程序运行结果如下： 

编号：01, 书名：Think in java
编号：02, 书名：java 讲义
编号：03, 书名：java 语言程序设计


参考文档：

[1] https://www.cnblogs.com/ywjy/p/5073082.html

返回 Java程序设计

取自“http://www.openbrains.net/mediawiki/index.php?title=Set接口和HashSet类&oldid=18092”