首页 > 其他分享 >Set、HashSet、LinkedHashSet

Set、HashSet、LinkedHashSet

时间:2023-02-09 15:17:10浏览次数:42  
标签:Set hash HashSet value key table LinkedHashSet null

set接口基本介绍

  1. 无序(添加和取出的顺序不一致),没有索引
  2. 不允许重复元素,所有最多包含一个null

HashSet

  1. HashSet实现了Set接口
  2. HashSet实际上是HashMap

HashSet细节

set.add("jack"); true
set.add("jack"); false
set.add(new Cat("tom")); true
set.add(new Cat("tom")); true

//重点
set.add(new String("hello")); true
set.add(new String("hello")); false

HashSet底层是HashMap,添加一个元素时,先得到hash值,会转成索引值,找到存储数据表table,看这个索引的位置是否已经存放有元素,如果没有就直接加入,如果有,就调用equals比较,如果相同就放弃添加,如果不同就添加到此链表后面,在Java8中如果一条连链表个数等于默认值8,并且table>=64 就转换成红黑树

执行过程:

  1. 执行 HashSet()
public HashSet() {
      map = new HashMap<>();
}
  1. 执行 add()
public boolean add(E e) {
    return map.put(e, PRESENT)==null; 
    //private static final Object PRESENT = new Object();
}
  1. 执行 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);
}
  1. 执行 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;
      if ((tab = table) == null || (n = tab.length) == 0) //table就是存放节点的数组
          n = (tab = resize()).length;

      //根据key,得到hash去计算该key应该存到table表的哪个索引位置
      //并把这个位置的对象赋给p
      //判断p是否为null,如果为空表示还没有存放元素,就创建一个node放在末尾
      if ((p = tab[i = (n - 1) & hash]) == null)
          tab[i] = newNode(hash, key, value, null);
      else {
          Node<K,V> e; K k;
          if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样 ,准备加入的key和p指向的Node节点是同一个对象,或者不是同一个对象,但是内容相同
              e = p;
          //再判断 p 是不是一颗红黑树,
          //如果是一颗红黑树,就调用 putTreeVal,来进行添加
          else if (p instanceof TreeNode)
              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
          else { //如果table对应索引位置,已经是一个链表,就依次比较
                  //(1)依次和该链表的每个元素比较后,都不相同,就使用for循环比较,把元素添加到链表后,立即判断是否达到8个节点,如果达到就调用treeifyBin()对当前列表进行树化(红黑树)。在转成红黑树时,还进行判断,如果该table数组大小 小于64先扩容,否则转成红黑树
                  //(2)在比较的过程中,有相同情况就break
                  //
              for (int binCount = 0; ; ++binCount) {
                  if ((e = p.next) == null) {
                      p.next = newNode(hash, key, value, null);
                      if (binCount >= TREEIFY_THRESHOLD - 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;
      if (++size > threshold)
          resize();
      afterNodeInsertion(evict);
      return null;
  }

HashSet的扩容

  1. 底层的HashMap,第一次添加时,table数组扩容到16,临界值(threshold)是16 * 加载因子 (loadFactor)是0.75 = 12
  2. 如果table数组使用到了临界值12,就会扩容到16 * 2 = 32,新的临界值就是32 * 0.75 = 24,依次类推
  3. 在java8中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(模拟64),就会进行树化(红黑树),否则仍然采用数组进行扩容机制

标签:Set,hash,HashSet,value,key,table,LinkedHashSet,null
From: https://www.cnblogs.com/jxnote/p/17105354.html

相关文章