HashSet和HashTable的的源码分析
- HashSet
- HashTable

HashSet和HashTable的的源码分析

HashSet

HashSet其实就是使用HashMap来实现的，方法都是依靠Hash Map的方法。如hashSet构造，hashSet的添加等操作。这样能够实现hashset去重。因为hashMap的key不能重复。这样就能看上篇，当hashMap遇到key值重复的处理。

HashSet结构源码

HashSet的结构就相当于HashMap只将key值put进去，但是Value值却为空的new Object。可以看作为只有key的HashMap.

/* 可以看到hashSet的这几个构造方法和HashMap息息相关 */
private transient HashMap<E,Object> map;
public HashSet() {
    map = new HashMap<>();
}

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

HashSet的基本方法

add和remove和size等基本方法都是调用HashMap的

如add方法:

public boolean add(E e) {
  /* 这里的PRESENT等于new Object() */
       return map.put(e, PRESENT)==null;
   }

HashSet的Iterator和contains方法

同样的也是调用的HashMap的基本方法，但是需要先得到Map的keySet集合

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

HashTable

首先HashTable和HashMap的结构类似。但是有最重要的区别就是HashTable是synchronized的，也就是线程安全的。在他的基本方法前都有synchronized锁所限制。

结构就不看了，只看一个Put方法

/* 其实大致和HashMap是类似的也是使用Entry作为基本结构 */
public synchronized V put(K key, V value) {
     // Make sure the value is not null
     if (value == null) {
         throw new NullPointerException();
     }
     // Makes sure the key is not already in the hashtable.
     Entry<?,?> tab[] = table;
     int hash = key.hashCode();
     /* 这里的0x7FFFFFFF 是32-bit的int的最大值 */
     int index = (hash & 0x7FFFFFFF) % tab.length;
     @SuppressWarnings("unchecked")
     Entry<K,V> entry = (Entry<K,V>)tab[index];
     /* 如果这个entry存在，也就是键值重复 */
     for(; entry != null ; entry = entry.next) {
         if ((entry.hash == hash) && entry.key.equals(key)) {
             V old = entry.value;
             entry.value = value;
             return old;
         }
     }
    /* 否则添加Entry节点 */
     addEntry(hash, key, value, index);
     return null;
 }

 private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
      /* 如果当前count大于阈值的大小 重新生成table size和hash值 */
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

通过上面的代码可以看出HashTable和HashMap的结构还是有差异的，HashMap是纵向的列表当出现相同的hash值的时候，扩展出横向列表，当横向的列表到达一定的长度的时候，这个横向的链表就会自动整理成红黑树的形式，而hashTable不存在横向的这种结构的，当count>=阈值的时候就会把Hash重置，使之不会出现hash值重复的情况。可以说hashTable比较hashMap的结构更简单，但是效率会比HashMap的低。