HashTable源码阅读
HashTable源码阅读
环境jdk1.8.0_121
与HashMap有几点区别
在HashMap中，冲突的值会在bucket形成链表，当达到8个，会形成红黑树，而在HashTable中，冲突的值就以链表的形式存储
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(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; }
会发现求索引的方式也不一样，(hash&0x7FFFFFFF)%tab.length，而在HashMap中是(hash^(hash>>>16))&(tab.length-1)，可以看出HashTable里，并没有做出相应的优化，这边解释下HashMap中的优化，(hash^(hash>>>16))这一步是其实是让一个hash值的高16位和低16位做异或，混合高位和低位，加大低位的随机性，(hash^(hash>>>16))&(tab.length-1)求与，其实就是相当于HashTable中的取模，只是在你计算机中用位预算效率比较高，当然tab.length在HashMap中其实是一个2的n次方，所以能达到这一的效果。
还有一点，可以看到HashTable中是不允许放值为Null的value，它会抛出错误。而且key值也不能为null，因为它直接拿key.hashCode()，null是拿不到hashCode也会发生错误。
继续看addEntry，开始添加元素
private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<?,?> tab[] = table; if (count >= threshold) { // 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++; }
代码非常简洁，如果数量大于限定值，就开始扩充，重新计算索引位置，然后插入
先看插入
tab[index] = new Entry<>(hash, key, value, e);
在创建entry的时候，传了个bucket的第一个entry，
protected Entry(int hash, K key, V value, Entry<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; }
看构造函数其实可以看出，在这里进行指向旧的第一个entry，因此，在hashtable中其实是插入在链表的头，而在HashMap是在尾
然后我们在看它的rehash
protected void rehash() { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; modCount++; threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; for (int i = oldCapacity ; i-- > 0 ;) { for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; newMap[index] = e; } } }
比HashMap简单的多。。。len扩充2*len+1，然后对原来bucket中的entry重新计算索引，并赋值，不改变链表原先的顺序，在HashMap中复杂的多，可以看我另个讲HashMap的博客
但相对HashMap，HashTable是线程安全的，因为在很多方法，比如get,put,equals等，都使用了synchronized同步锁。
总结：
1. HashTable的key、value不能为null
2. HashTable线程安全
3. HashTable的优化其实没有HashMap做的好，在单线程的情况，最好使用HashMap
贴上一句源码中的提示
* Java Collections Framework</a>. Unlike the new collection * implementations, {@code Hashtable} is synchronized. If a * thread-safe implementation is not needed, it is recommended to use * {@link HashMap} in place of {@code Hashtable}. If a thread-safe * highly-concurrent implementation is desired, then it is recommended * to use {@link java.util.concurrent.ConcurrentHashMap} in place of * {@code Hashtable}.
大致意思就是：不需要线程安全用HashMap，不需要线程安全的高并发用ConcurrentHashMap