java中的set接口(Hashset，LinkedHashset,TreeSet)

Hashset介绍

• HashSet实际上是HashMap，底层都一样(数组+链表+红黑树)
• 不能有重复的元素，记住深入理解，可以添加不同的对象的，在前面的随笔中讲过了，只能有一个null
• 添加元素底层机制说明(先说结论)：
• 添加一个元素时，先得到hash值，会转成–>索引。
• 找到存储数据表table，看这个索引是否已经存放元素
• 如果该hash值得出的索引位置上没有其他元素，则直接存放
• 如果有则调用equals比较，如果相同就放弃添加，如果没有添加到最后
• 重要，我们可以在添加的对象中重写equals，就是判断的内容，主要是看equals有没有重写
• 添加元素的代码分析

@SuppressWarnings({"all"})public class HashSet01 {    public static void main(String[] args) {        Set set = new HashSet<>();        set.add("平凡晨");//成功        set.add("浪子王");//成功        set.add("路人甲");//成功        set.add("平凡晨");//失败        System.out.println("Set = "+ set);        /**         * 1、 底层创建了的是HashMap         * public HashSet() {         *         map = new HashMap<>();         *     }         *         * 2、执行add()方法，并且是返回一个布尔值         * public boolean add(E e) { //e：平凡晨         *         return map.put(e, PRESENT)==null; //PRESENT = new Object         *     }         *         * 3、执行的是put()         * public V put(K key, V value) { //key："平凡晨"  value： 因为Hashset没有value值，存放的是Object，起到站位的作用         *         return putVal(hash(key), key, value, false, true);         *     }         *         * 4、往里追会(hash(key)方法 会跳到hash()方法  这个方法 会得到 key对应的hash值         *     重要重要的一句话： 里面的hash值 不等价于 hashCode()         * static final int hash(Object key) {         *         int h;         *         //解释：这个方法是先判断传进来的key是不是空，         *         //       不是空的话就得到他的hash值，无符号右移16位         *         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);         *     }         *         *         * 重要重要！！！！！！！！！！！！         *         *  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,         *                    boolean evict) {         *         Node[] tab; Node p; int n, i; //定义了一些辅助变量         *         *         // 解释：if ((tab = table) == null 把当前的table表赋给了数组变量tab，在判断当前的tab表是不是空         *         //解释：|| (n = tab.length) == 0)  并且判断当前的tab的长度赋给 n  在判断长度是不是0         *         // 解释：第一次添加tab肯定是null，所以第一次添加会进入if语句的代码块         *         if ((tab = table) == null || (n = tab.length) == 0)         *         //解释：这个resize()).length其实是给数组初始化值位12个空间，然后在赋给数组tab ，在给到n         *             n = (tab = resize()).length;         *         *         //解释：根据key ，得到hash值，去计算在tab表中的索引位置 ，并赋给p ，在判断p 是不是null         *         //如果p 等于null 就表示没有添加过数据         *         if ((p = tab[i = (n - 1) & hash]) == null)         *         //解释：创建一个Node （key = "平凡晨"，value = "PRESENT"）         *             tab[i] = newNode(hash, key, value, null);         *         *         //解释：如果p不为空就进入else         *         else {         *             Node e; K k;         *         *              解释：如果当前索引位置对应的第一个链表和准备添加的key的hash值一样         *              解释：并且当前索引的key 和要传进来的key 是不是同一个对象         *              解释：或者传进来的null不等于空，并且传进来的key的equlas等于k         *              解释：看传进来的代码有没有重写equal方法         *             if (p.hash == hash &&         *                 ((k = p.key) == key || (key != null && key.equals(k))))         *                 e = p;         *         *             解释：进入else if  在判断p是不是一个红黑树         *              解释：如果是一个红黑树就调用 putTreeVal 这个方法         *             else if (p instanceof TreeNode)         *                 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);         *         *             解释：如果 table 表的索引位置 ，已经是一个链表就for循环         *             解释：以此和链表上的每个元素进行比较。         *             解释：如果链表有元素，并且判断比较时，不相同就加载到有元素的链表的后面         *             else {         *                 for (int binCount = 0; ; ++binCount) {         *                     if ((e = p.next) == null) {         *                         p.next = newNode(hash, key, value, null);         *                         解释：当把数据添加进来以后，就立即判断的链表的结点是否已经达到八个         *                         重点！！！：注意在进行红黑树的时候，他会判断你当前的的数组大小有没有达到64个空间         *                                  如果没有就先把数组大小扩容到64         *                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st         *                              解释：达到八个就转为红黑树         *                             treeifyBin(tab, hash);         *                         break;         *                     }         *         *                      解释：如果链有元素，并且判断比较时，相同，则就brak         *                     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  ，在判断是不是应该扩容 ，返回一个null         *         ++modCount;         *         if (++size > threshold)         *             resize();         *         afterNodeInsertion(evict);         *         return null;         *     }         */    }}

• Hashset扩容和红黑树机制(总结)
• HashSet底层HashMap，第一添加的时候，table数组扩容到16，临界值时16加载因子(0.75)。也就是160.75 = 12 ，临界值就是12
• 如果table数组使用到临界值12就会扩容，162 = 32，新的临界值就是320.75 = 24，依此类推
• 如果一条链表达到8时，会先把tabel数组扩容到64，在转化成红黑树，如果没有到64，不转红黑树，知道到达64为止

LinkedHashSet的说明

LinkedHashSet是Hashset的子类

LinkedHashSet底层是LinkedHashMap底层维护的是数组+双向链表

LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使 用链表维护元素的次序(图)，这使得元素看起来是以插入顺序保存的。

LinkedHashset不允许元素重复

TreeSet

• 核心：TreeSet里面有一个构造器，传入的是一个比较器(匿名内部类)
• 注意：tes.add( new 对象); 这个会报错，因为会把 这个对象转位 comparble类型，没发转
• Comparator是一个比较器(比较大小，也就是按照一定规则排序)，里面有一个compare的构造器需在调用的时候重写，主要是return返回值是大于0，就从大到小排序，return返回值是小于0，就从小到大排序
  *

java;gutter:true; import java.util.Comparator; import java.util.TreeSet;</p> <p>public class text { public static void main(String[] args) { TreeSet tes = new TreeSet<>(new Comparator() { @Override public int compare(Object o1, Object o2) { //根据字符串长度比较 //注意，如果用字符的长度排序，如果有相同的长度底层源码 ，就直接返回，没有听见进去 // return ((String) o1).length() - ((String) o2).length();</p> <pre><code> //根据字符串的字母顺序比较 return ((String) o1).compareTo((String) o2); } }); tes.add("java"); tes.add("lm"); tes.add("jack");//这里如果按字符长度排序 则不能添加进去，因为 tes.add("java"); 也是4 ，底层源码就返回0，添加不成功 tes.add("liming"); tes.add("pingfanchen"); System.out.println("tes + " +tes);　　 } </code></pre> <p>}

Original: https://www.cnblogs.com/ityc/p/15996581.html
Author: 平凡晨
Title: java中的set接口(Hashset，LinkedHashset,TreeSet)