JavaSet的源码分析

叁歲伎倆 2022-06-13 00:48 208阅读 0赞

Java中，set能保证列表中元素唯一，map就是用来key-value用的东西。

先看Set。

首先Set是个接口，最常见的实现有HashSet，LinkedHashSet，和同步Set。

看HashSet的源码，其他应该类似（只是加上了特定功能，比如使用链表、加上同步机制等）。

public class HashSet<E> extends AbstractSet<E>
      implements Set<E>, Cloneable, Serializable
    {
      static final long serialVersionUID = -5024744406713321676L;
      private transient HashMap<E, Object> map;
      private static final Object PRESENT = new Object();
    
      public HashSet()
      {
        this.map = new HashMap();
      }

一目了然的是，HashSet组合了一个HashMap通过对HashMap的操作来实现哈希set。

hashset的add操作如下：

public boolean add(E paramE)
      {
        return (this.map.put(paramE, PRESENT) == null);
      }

通过在hashmap中把要放到set中的元素作为key，静态变量present（Object类型）作为value，来为hashset添加元素。

同理，hashset的remove操作也就是对map的操作了。

需要有一点注意到的是，set是如何保证内部的对象唯一性的（当然，也是靠hashmap实现的），怎么感觉像是废话  =。=

hashmap实现唯一性的代码如下：

public V put(K paramK, V paramV)
      {
        if (paramK == null)
          return putForNullKey(paramV);
        int i = hash(paramK.hashCode());
        int j = indexFor(i, this.table.length);
       for (Entry localEntry = this.table[j]; localEntry != null; localEntry = localEntry.next) if (localEntry.hash == i) { java.lang.Object localObject1; if (((localObject1 = localEntry.key) == paramK) || (paramK.equals(localObject1))) { java.lang.Object localObject2 = localEntry.value; localEntry.value = paramV; localEntry.recordAccess(this); return localObject2; } }
        this.modCount += 1;
        addEntry(i, paramK, paramV, j);
        return null;
      }

其中粗体标注了检测要添加的元素是否在map中的操作。这里用到了hashcode和equals的作用。 **hashcode在之前的文中已经提到过，是为了减少对对象的比较复杂度而设置的。这里遍历了map中所有的元素。**

transient Entry[] table;

上面粗体还提到了table属性。这里是维护的Entry的数组，同其他列表一样，数组大小会自动增长：不过奇怪的是，这里使用了 2147483647这个数字，不知道那个if判断是做什么用的，求指点

void resize(int paramInt)
      {
        Entry[] arrayOfEntry1 = this.table;
        int i = arrayOfEntry1.length;
        if (i == 1073741824)
        {
          this.threshold = 2147483647;
          return;
        }
        Entry[] arrayOfEntry2 = new Entry[paramInt];
        transfer(arrayOfEntry2);
        this.table = arrayOfEntry2;
        this.threshold = (int)(paramInt * this.loadFactor);
      }