Set集合

1.Set集合概述

 Set集合类似一个罐子，程序可依次把多个对象丢进Set集合，而Set集合通常不能记住元素的添加顺序。Set集合不允许包含相同的元素，如果试图把两个相同的元素加入同一个Set集合中，则添加操作失败，add()方法返回false，且新元素不会被加入。

2.HashSet类

 HashSet是Set接口最常用的实现类,顾名思义,底层才用了哈希表(散列/hash)算法。其底层其实也是一个数组,存在的意义是提供查询速度,插入速度也比较快,但是适用于少量数据的插入操作。

2.1 HashSet具有以下特点：

 a.不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化。

 b.HashSet不是同步的，如果多个线程同时访问一个HashSet,假设有两个或者两个以上线程同时修改了HashSet集合时，则必须通过代码来保证其同步。

 c.集合元素值可以是null。

2.2 在HashSet中如何判断两个对象是否相同问题:

      1):两个对象的equals比较相等.  返回true,则说明是相同对象.

      2):两个对象的hashCode方法返回值相等.

二者:缺一不可.

当往HashSet集合中添加新的对象时,先判断该对象和集合对象中的hashCode值:

                         1):不等: 直接把该新的对象存储到hashCode指定的位置.

                         2):相等: 再继续判断新对象和集合对象中的equals做比较.

    hashCode相同,equals为true: 则视为是同一个对象,则不保存在哈希表中;hashCode相同,equals为false:非常麻烦,存储在之前对象同槽为的链表上.

2.3 对象的hashCode和equals方法的重要性:

 每一个存储到hash表中的对象,都得提供hashCode和equals方法,用来判断是否是同一个对象.存储在哈希表中的对象,都应该覆盖equals方法和hashCode方法,并且保证equals相等的时候,hashCode也应该相等.

 当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals()方法比较返回true，但他们的hashCode()方法返回值不相等，HashSet将会把它们存储在不同的位置，依然可以添加成功。

3.HashSet集合存储数据的结构（哈希表）

 哈希表底层使用的也是数组机制，数组中也存放对象，而这些对象往数组中存放时的位置比较特殊，当需要把这些对象给数组中存放时，那么会根据这些对象的特有数据结合相应的算法，计算出这个对象在数组中的位置，然后把这个对象存放在数组中。而这样的数组就称为哈希数组，即就是哈希表。

 当向哈希表中存放元素时，需要根据元素的特有数据结合相应的算法，这个算法其实就是Object类中的hashCode方法。由于任何对象都是Object类的子类，所以任何对象有拥有这个方法。即就是在给哈希表中存放对象时，会调用对象的hashCode方法，算出对象在表中的存放位置，这里需要注意，如果两个对象hashCode方法算出结果一样，这样现象称为哈希冲突，这时会调用对象的equals方法，比较这两个对象是不是同一个对象，如果equals方法返回的是true，那么就不会把第二个对象存放在哈希表中，如果返回的是false，就会把这个值存放在哈希表中。

总结：保证HashSet集合元素的唯一，其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象，那么保证其唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式。

4.HashSet存储自定义类型数据

 如果需要把自定义的对象存储到哈希表中,该类型的对象应该覆盖equals和hashCode方法,并在该方法中提供自己的判断规则。

package com.xupt.student;

public class Student {
	private String name;
	private int age;
	public Student() {
		super();
		// TODO Auto-generated constructor stub
	}
	public Student(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	@Override
	public String toString() {
		return "Student [name=" + name + ", age=" + age + "]";
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + age;
		result = prime * result + ((name == null) ? 0 : name.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;
		Student other = (Student) obj;
		if (age != other.age)
			return false;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}
}

5.LinkedHashSet类

 LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的。也就是说，当遍历LinkedHashSet集合里的元素时，LinkedHashSet将会按元素的添加顺序来访问集合里的元素。LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet的性能，但在迭代访问Set里的全部元素时将有很好的性能，因为它以链表维护内部顺序。虽然LinkedHashSet使用了链表记录集合元素的添加顺序，但LinkedHashSet依然是HashSet,因此它依然不允许集合元素重复。

6. TreeSet类

 TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。与HashSet集合采用hash算法来决定元素存储位置不同，TreeSet采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方法：自然排序和定制排序。在默认的情况下TreeSet采用自然排序（注意: 必须保证TreeSet集合中的元素对象是相同的数据类型,否则报错）。

6.1 自然排序

 TreeSet会调用集合元素的compareTo（Object  obj）方法来比较元素之间的大小关系，然后将集合元素按升序排列，这种方式就是自然排序。

 Java提供了一个Comparable接口，该接口里定义了一个compareTo(Objectobj)方法，该方法返回一个整数值，实现该接口的类必须实现该方法，实现该接口的类的对象就可以比较大小。

6.2 定制排序

 TreeSet需要实现定制排序，可以通过Comparator接口帮助。如果需要实现定制排序，则需要在创建TreeSet集合对象时，提供一个Comparator对象与该TreeSet集合关联，由该Comparator对象负责集合元素的排序逻辑。

package com.edu_05;
public class Student{
	private String name;
	private int age;
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	public Student() {
		super();
		// TODO Auto-generated constructor stub
	}
	public Student(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
}

package com.edu_05;
import java.util.Comparator;
public class ComparatorImpl implements Comparator<Student>{
	@Override
	public int compare(Student s1, Student s2) {
		int num  = s1.getAge() - s2.getAge();
		int num2 = num==0?s1.getName().compareTo(s2.getName()):num;
		
		return num2;
	}
}

package com.edu_05;
import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetTest {
	public static void main(String[] args) {
		//TreeSet(Comparator comparator) 
        //创建使用比较器排序的TreeSet集合
		TreeSet<Student> ts = new TreeSet<Student>(new Comparator<Student>() {
			@Override
			public int compare(Student s1, Student s2) {
				int num  = s1.getAge() - s2.getAge();
				int num2 = num==0?s1.getName().compareTo(s2.getName()):num;
				return num2;
			}
		});
		
		//创建元素
		Student s1 = new Student("guodegang", 45);
		Student s2 = new Student("yuqian", 48);
		Student s3 = new Student("zhangziyi", 40);
		Student s4 = new Student("wangfeng", 50);
		Student s5 = new Student("guofucheng", 50);
		
		ts.add(s1);
		ts.add(s2);
		ts.add(s3);
		ts.add(s4);
		ts.add(s5);
		
		//遍历元素
		for (Student student : ts) {
			System.out.println(student.getAge()+"--"+student.getName());
		}
	}
}

7.ArrayList的contains方法判断元素是否重复原理

 ArrayList的contains方法会使用调用方法时，传入的元素的equals方法依次与集合中的旧元素所比较，从而根据返回的布尔值判断是否有重复元素。此时，当ArrayList存放自定义类型时，由于自定义类型在未重写equals方法前，判断是否重复的依据是地址值，所以如果想根据内容判断是否为重复元素，需要重写元素的equals方法。

8.HashSet的add/contains等方法判断元素是否重复原理

 Set集合不能存放重复元素，其添加方法在添加时会判断是否有重复元素，有重复不添加，没重复则添加。HashSet集合由于是无序的，其判断唯一的依据是元素类型的hashCode与equals方法的返回结果。规则如下：

   先判断新元素与集合内已经有的旧元素的HashCode值

 如果不同，说明是不同元素，添加到集合。

 如果相同，再判断equals比较结果。返回true则相同元素；返回false则不同元素，添加到集合。

 所以，使用HashSet存储自定义类型，如果没有重写该类的hashCode与equals方法，则判断重复时，使用的是地址值，如果想通过内容比较元素是否相同，需要重写该元素类的hashcode与equals方法。

总结

1.List与Set集合的区别？

       List:

                它是一个有序的集合(元素存与取的顺序相同)

                它可以存储重复的元素                        

        Set:

               它是一个无序的集合(元素存与取的顺序可能不同)

               它不能存储重复的元素

2.List集合中的特有方法

 void add(int index, Object element) 将指定的元素，添加到该集合中的指定位置上

 Object get(int index)返回集合中指定位置的元素。

 Object remove(int index) 移除列表中指定位置的元素, 返回的是被移除的元素

 Object set(int index, Object element)用指定元素替换集合中指定位置的元素,返回值的更新前的元素。