Set接口学习（2）

基本介绍

1）无序，没有索引（无下标序号）。

2）不允许重复元素，所以最多包含一个null

常用方法

和List接口一样，Set接口也是Collection的子接口，所以常用方法和Collection一样

Set接口的遍历方式

迭代器和foreach，但是不能用索引，因为Set接口是无序且没有索引的。

set常用方法

这里没有什么新方法，只对 add()、equals() 和 hashCode() 方法添加了限制

HashSet全面说明

简介：

1）HashSet实际上是HashMap，通过源码可以看出来。

2）可以存放null，但是只能存放一个，因为HashSet数据不能重复，

3）HashSet不保证元素是有序的，取决于hashCode，再确定索引结果，对象的变化则会导致HashCode的变化。

如果需要访问的顺序和插入的顺序一致，可以使用HashSet的子类LinkedHashSet；

5）Set接口—>HashSet实现类 --> LinkedHashSet【在hashSet的基础上给每个存储的元素额外添加一个链表，用于记录添加元素的顺序】

6）HashSet的实现原理

public class HashSet<E> extends AbstractSet<E> 抽象类，其中提供Set的公共方法 implements Set<E>, 实现Set接口 Set set=new HashSet(); 多态 Cloneable,可克隆的 java.io.Serializable 可序列化和反序列化的

7）属性： private transient HashMap<E,Object> map; 具体存储数据的HashMap，存储数据需要提供key和value两个部分,HashSet只是使用了key值部分

8）哈希的介绍（散列算法）：

Hash一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

MessageDigest md=MessageDigest.getInstance("md5");
  		String pwd="123456";
 		byte[] bb=md.digest(pwd.getBytes());
  		String ss=Base64.getEncoder().encodeToString(bb);
 		System.out.println(ss); 

所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

9)构造器

构造器
 * public HashSet() {
        map = new HashMap<>();
    }
    
     public HashSet(int initialCapacity初始化容器, float loadFactor负载因子) {  集合中最大存储数据的数据
     量为【容器*负载因子】,如果大于这个值则自动扩容
        map = new HashMap<>(initialCapacity, loadFactor);
    }

10)哈希冲突 当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，就把它叫做碰撞（哈希碰撞）。

以key/value的方式存储数据，采用拉链法综合了数组和链表结构。如果key已知则存取效率较高，但是删除慢，如果不知道key存取则慢，对存储空间使用不充分。最典型的实现是HashMap。

11）散列算法

散列法Hashing是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值 或索引值的方法，称为散列法，也叫哈希法。

由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中 建立索引并进行搜索，同时还用在各种解密算法中

HashSet底层机制（重点）

HashSet底层是HashMap，HashMap底层是（数组+链表+红黑树）

文字描述：

1）HashSet底层是HashMap。

2）添加一个元素的时候，会先得到一个hash值（散列算法Hashing），该hash值会转换成为一个索引值。

3）找到存储数据表table，看这个索引位置是否以已经存放有元素。

4）如果没有，直接加入。

5）如果有，调用equals比较，如果相同，就放弃添加，如果不相同，那么就添加到最后。

6）如果一条链表的元素个数到达TREEIFY_THRESHOLD（默认是8），并且table大于MIN+TREEIFY_CAPACITY（默认64），那么就会进行树化。

第五条补充：要求当两个同类型对象equals为TRUE时候，必须hashCode值一致。事实上 equals方法和hashCode方法没有任何必然联系，所以说前面的规则是个潜规则

HashSet源码解读

@SuppressWarnings({"all"})
public class HashSetSource {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");//到此位置，第 1 次 add 分析完毕. hashSet.add("php");//到此位置，第 2 次 add 分析完毕
hashSet.add("java");
System.out.println("set=" + hashSet);
/*
1. 执行 HashSet()
public HashSet() {
map = new HashMap<>();
}
2. 执行 add()
public boolean add(E e) {//e = "java"
return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();
}
3.执行 put() , 该方法会执行 hash(key) 得到 key 对应的 hash 值 算法 h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//key = "java" value = PRESENT 共享
return putVal(hash(key), key, value, false, true);
}
4.执行 putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; //定义了辅助变量
//table 就是 HashMap 的一个数组，类型是 Node[]
//if 语句表示如果当前 table 是 null, 或者 大小=0
//就是第一次扩容，到 16 个空间. if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(1)根据 key，得到 hash 去计算该 key 应该存放到 table 表的哪个索引位置
//并把这个位置的对象，赋给 p
//(2)判断 p 是否为 null
//(2.1) 如果 p 为 null, 表示还没有存放元素, 就创建一个 Node (key="java",value=PRESENT)
//(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建
Node<K,V> e; K k; //
//如果当前索引位置对应的链表的第一个元素和准备添加的 key 的 hash 值一样
//并且满足 下面两个条件之一:
//(1) 准备加入的 key 和 p 指向的 Node 结点的 key 是同一个对象
//(2) p 指向的 Node 结点的 key 的 equals() 和准备加入的 key 比较后相同
//就不能加入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//再判断 p 是不是一颗红黑树, //如果是一颗红黑树，就调用 putTreeVal , 来进行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果 table 对应索引位置，已经是一个链表, 就使用 for 循环比较
//(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
// 注意在把元素添加到链表后，立即判断 该链表是否已经达到 8 个结点
// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
// 注意，在转成红黑树时，要进行判断, 判断条件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面条件成立，先 table 扩容. // 只有上面条件不成立时，才进行转成红黑树
//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接 break
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//size 就是我们每加入一个结点 Node(k,v,h,next), size++
if (++size > threshold)
resize();//扩容
afterNodeInsertion(evict);
return null;
}
*/
}
}

LinkedHashSet全面说明

LinkedHashSet规范：

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, Serializable

简介

LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。

采用双向链表记录添加元素的顺序

LinkedHashMap类中的节点定义
			static class Entry<K,V> extends HashMap.Node<K,V> {
        		Entry<K,V> before, after;
		        Entry(int hash, K key, V value, Node<K,V> next) {
		            super(hash, key, value, next);
		        }
    		}

Set<String> set=new LinkedHashSet<>();
for(int i=0;i<10;i++)
	set.add("str-"+i);
Iterator<String> it=set.iterator();
while(it.hasNext()){
    String tmp=it.next();
    System.out.println(tmp);
}

TreeSet全面介绍

Tree是一种有顺序的set实现类：

TreeSet全面说明：

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable

数据存储

private transient NavigableMap<E,Object> m;
public interface NavigableMap<K,V> extends SortedMap<K,V>

查看jdk源码发现底层是用TreeMap实现的，本质上是一个红黑树原理。正因为它是排序了的，所以相对HashSet来说，TreeSet提供了一些额外的按排序位置访问元素的方法，例如first(), last(), lower(), higher(), subSet(), headSet(), tailSet();

数据排序

TreeSet的排序分两种类型，一种是自然排序，另一种是定制排序。

Java中为了实现对象的比较引入了compare算法

这里用于实现了两个日期的比较大小，如果返回为0则表示两个对象相等，如果 返回为1则表示d1大于参数；如果返回-1表示d1小于参数

1）自然排序

TreeSet 会调用compareTo方法比较元素大小，然后按升序排序（从小到达）。所以自然排序中的元素对象，都必须实现了Comparable接口，否则会跑出异常。对于TreeSet判断元素是否重复的标准，也是调用元素从Comparable接口继承而来compareTo方法，如果返回0则是重复元素。Java的常见类都已经实现了Comparable接口

给Person类上添加针对Comparable接口的实现：考虑具体的业务规则，按照类中什么属性进行排序比较

2）定制排序

TreeSet还有一种排序就是定制排序，定制排序时候，需要关联一个 Comparator对象，由Comparator提供排序逻辑

构造器

 public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

Set<Person> set=new TreeSet<>((obj1, obj2)->{
    Person p1=(Person)obj1;
    Person p2=(Person)obj2;
    return p2.getId().compareTo(p1.getId());
});
for(int i=0;i<10;i++)
	set.add(new Person(1L+i, (9-i)+"name"));
set.forEach(System.out::println);

关于几种Set的比较

1）HashSet：不保证元素的添加顺序，底层采用哈希表算法，查询效率高。判断两个元素是否相等，equals方法返回为true要求hashCode值必须相等。即要求存入HashSet中的元素要覆盖equals方法和hashCode方法。

2）LinkedHashSet是HashSet的子类，底层采用了哈希表算法以及链表算法，既保证了元素的添加顺序，也保证了查询效率。但是整体性能要低于HashSet。

3）TreeSet不保证元素的添加顺序，但是会对集合中的元素进行排序。底层采用红-黑树算法，树结构比较适合查询，但是添加的效率较低

各种Set集合性能分析

1）HashSet和TreeSet是Set集合中用得最多的集合。HashSet总是比TreeSet集合性能好，因为HashSet不需要额维护元素的顺序。

2）LinkedHashSet需要用额外的链表维护元素的插入顺序，因此在插入时性能比HashSet低，但在迭代访问（遍历）时性能更高。因为插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。

3）EnumSet元素是所有Set元素中性能最好的，但是它只能保存枚举类型的元素。

线程安全化

ArrayList和LinkedList线程不安全，针对线程安全的需求一般也不建议使用Vector。

synchronizedXxx

List<Integer> list=Collections.synchronizedList(new ArrayList<>());

具体实现是在原来数据操作的基础上添加了一个全局锁