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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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;
           *     }
           */
  
      }
  }