一、Set接口的框架：
1.Collection接口：单列集合，用来存储一个一个的对象
2.Set接口：存储无序的，不可重复的数据 ，说白了就是高中讲的"集合"
3.HashSet接口：作为Set接口的主要实现类，线程不安全的，可以存储null值
4.LinkedHashSet：作为HashSet的子类，遍历其内部数据时，可以按照添加的顺序进行遍历。
对于频繁的遍历操作，LinkedHashSet效率高于HashSet
5.TreeSet接口：可以按照添加对象的指定属性，进行排序。
二、Set集合的无序性与不可重复性的理解：
- 无序性：不等于随机性，存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
- 不可重复性：保证添加的元素按照equals()判断时，不能返回true，即：相同的元素只能添加一个
- Set接口中没有额外定义新方法，使用的都是Collection中声明过的方法
- 要求：向Set中添加的数据，其所在的类一定要重写equals()方法和hashCode()方法
要求：重写的hashCode和equals()方法尽可能保持一致性：相等的对象必须具有相等的散列码(hash值)
重写两个方法的小技巧：对象中用作equals()方法比较的Field,都应该用来计算hashCode值.用快捷键直接生成就行了。
Set接口和常用方法如下
public class SetMethod { public static void main(String[] args) { //1.以Set接口的实现类，HashSet来讲解Set接口的方法 //2.set接口的实现类的对象(Set接口对象)，不能存放重复的元素，可以添加一个null //3.set接口对象存放数据是无序(即添加的顺序和取出的顺序不一致) //4.注意:取出的顺序虽然不是添加的顺序，但是它是固定的 Set set = new HashSet(); set.add("john"); set.add("lucy"); set.add("john"); set.add("jack"); set.add(null); set.add(null); set.add("ly"); for (int i = 0; i < 10; i++) { System.out.println("set=" + set);//取出的顺序，它是固定的 } //遍历 //方式一：使用迭代器 Iterator iterator = set.iterator(); while (iterator.hasNext()) { Object obj = iterator.next(); System.out.println("obj=" + obj); } set.remove(null); //删除null System.out.println("===增强for循环==="); //方式二：增强for循环 for (Object obj : set) { System.out.println("obj=" + obj); } //set接口对象，不能通过索引来获取 } }
输出结果如下
set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] set=[null, john, lucy, ly, jack] obj=null obj=john obj=lucy obj=ly obj=jack ===增强for循环=== obj=john obj=lucy obj=ly obj=jack
三、HashSet的全面说明
对应的代码讲解如下
public class HashSet_ { public static void main(String[] args) { //1.构造器走的代码 /* public HashSet() { map = new HashMap<>(); } 2.HashSet可以存放null，但是只能有一个null，即元素不能重复 */ Set hashSet = new HashSet(); hashSet.add(null); hashSet.add(null); System.out.println("hashSet=" + hashSet); } }
输出结果如下
hashSet=[null]
HashSet的案例说明
public class HashSet01 { public static void main(String[] args) { HashSet set = new HashSet(); //说明 //1.在执行add方法时，会返回一个boolean值 //2.如果添加成功，返回true，否则返回false //3.可以通过remove 指定删除哪个对象 System.out.println(set.add("john"));//true System.out.println(set.add("lucy"));//true System.out.println(set.add("john"));//false System.out.println(set.add("jack"));//true System.out.println(set.add("Rose"));//true set.remove("john"); System.out.println("set=" + set); set = new HashSet(); System.out.println(set);//[] set.add("lucy");//添加成功 set.add("lucy");//加入不了 set.add(new Dog("tom"));//添加成功 set.add(new Dog("tom"));//添加成功 System.out.println("set=" + set); //经典面试题 set.add(new String("ly"));//添加成功 set.add(new String("ly"));//加入不了 System.out.println("set=" + set); } } class Dog { private String name; @Override public String toString() { return "Dog{" + "name='" + name + '\'' + '}'; } public Dog(String name) { this.name = name; } }
输出结果
true true false true true set=[Rose, lucy, jack] [] set=[Dog{name='tom'}, Dog{name='tom'}, lucy] set=[Dog{name='tom'}, Dog{name='tom'}, lucy, ly]
HashSet底层机制说明
1、HashSet底层是HashMap,HashMap底层是(数组+链表+红黑树)
下面模拟简单的数组+链表结构代码如下
public class HashSetStructure { public static void main(String[] args) { //模拟一个HashSet的底层(HashMap的底层结构) Node[] table = new Node[16]; System.out.println("table=" + Arrays.toString(table)); //3.创建结点 Node john = new Node("john", null); table[2] = john; Node jack = new Node("jack", null); john.next = jack;//将jack结点 挂载到john Node rose = new Node("Rose", null); jack.next = rose;//将rose结点，挂载到jack System.out.println("table="+table[2]); Node lucy = new Node("lucy", null); table[3] = lucy; System.out.println("table="+table[3]); } } class Node {//结点，存储数据，可以指向下一个结点，从而形成链表 Object item;//存放数据 Node next;//指向下一个结点 public Node(Object item, Node next) { this.item = item; this.next = next; } @Override public String toString() { return "Node{" + "item=" + item + ", next=" + next + '}'; } }
输出结果如下
table=[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null] table=Node{item=john, next=Node{item=jack, next=Node{item=Rose, next=null}}} table=Node{item=lucy, next=null}
四、添加元素的过程：以HashSet为例：
我们向HashSet中添加元素a，首先调用元素a所在类的HashCode()方法，计算元素a的哈希值，此哈希值通过某种算法计算出在HashSet底层数组中的存放位置(即为：索引位置)，判断数组此位置上是否已经有元素。
如果此位置上没有其他元素，则元素a添加成功 ----情况1
如果此位置上有其他元素b（或以链表形式存在的多个元素），则比较元素a与元素b的hash值。
如果hash值不同，则元素a添加成功 -----情况2
如果hash值相同，进而需要调用元素a所在类的equals()方法，equals()返回true，则元素a添加失败，
equals()返回false，则元素a添加成功… ------情况3
注：对于添加成功的情况2和情况3而言，元素a与已经存在指定索引位置上数据以链表的形式存储
JDK7:元素a放到数组中，指向原来的元素
JDK8:原来的元素在数组中，指向元素a
总结：七上八下
HashSet底层：数组+链表的结构
五、HashSet的源码剖析
剖析代码如下
public class HashSetSource { public static void main(String[] args) { HashSet hashSet = new HashSet(); hashSet.add("java"); hashSet.add("php"); hashSet.add("java"); System.out.println("hashSet=" + hashSet); /* HashSet源码解读： 1.执行HashSet() public HashSet() { map = new HashMap<>(); } 2.执行add方法 public boolean add(E e) {//e="java" return map.put(e, PRESENT)==null; //PRESENT 就是 private static final Object 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; //根据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个结点，如果达到8个结点(是从0开始的) //就调用treefyBin()对当前这个链表进行树化(转成红黑树) //注意，在转成红黑树时，要进行判断 // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 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; } */ } }
HashSet底层机制二
可以debug以下代码，进行分析
public class HashSetIncrement { public static void main(String[] args) { HashSet hashSet = new HashSet(); // for (int i = 1; i < 100; i++) { // hashSet.add(i); // } /* 在java8中，如果一条链表的元素个数达到TREEIFY_THRESHOLD(默认是8) 并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树) 否则仍然采用数组扩容机制 */ for (int i = 1; i < 12; i++) { hashSet.add(new A(i)); } } } class A { private int n; public A(int n) { this.n = n; } @Override public int hashCode() { return 100; } }
HashSet底层机制三
当我们向hashset增加一个元素时，->Node ->加入到table，就算是增加了一个size++
可以debug以下源码进行分析
public class HashSetIncrement { public static void main(String[] args) { HashSet hashSet = new HashSet(); /* 当我们向hashset增加一个元素时，->Node ->加入到table，就算是增加了一个size++ */ for (int i = 1; i <=7 ; i++) {//在table的某一条链表上添加了 7个A对象 hashSet.add(new A(i)); } for (int i = 0; i <=7 ; i++) {//在table的某一条链表上添加了 7个A对象 hashSet.add(new B(i)); } } } class B{ private int n; public B(int n) { this.n = n; } @Override public int hashCode() { return 200; } } class A { private int n; public A(int n) { this.n = n; } @Override public int hashCode() { return 100; } }
