简介
HashTable也是一个Key-Value对的集合，任何非空对象都可以做为其key或是value，也就是说：它并不限制key或value是否重复，只限制key或value不允许为null，如果key重复，则最后被put的key-value对中的value会替换掉原来key-value对中的value。
为了能够成功的从HashTable中存储或检索对象，HashTable要求key对象必须实现了hashCode和equals方法。
每个HashTable对象都有两个影响其性能的属性，它们是：初始容量和填空因子(initial capacity, load factor)。容量是指HashTable中Bucket的数量，而初始容量是指HashTable刚创建时，它分配的容量，此时还未向HashTable填空数据更未进行扩容，只是初始化时指定的一个容量大小。注意，HashTable是开放的：当发生哈希冲突的时候，一个Bucket需要存储多个数据元素，此时如果搜索数据时，需要从Bucket处按顺序向后搜索。填空因子是HashTable扩容之前允许存储元素的比例，例如默认的填空因子是0.75，如果HashTable的初始容量是16，那么当HashTable存储了12个数据之后，它的填空因子达到了0.75，如果再向HashTable存储数据的话，由于存储的数据量超过了填空因子，所以需要对HashTable进行扩容。初始容量和填空因子这两个参数的具体 数值是可以改变的。何时以及是否调用reHash函数取决于HashTable的具体实现或是TashTable的具体使用者。
一般情况下，默认的填空因子是0.75，这个数值是权衡时间开销和空间开销而得到的一个值。更大的填空因子，可以节省内存空间，但是会增加查找，插入数据等操作的时间，更小的填空因子，也会造成较多的内存浪费，因为还没有填充多数数据就要对HashTable进行扩容。
如果初始容量比HashTable存储的最大元素个数除以填充因子还大，则HashTable在使用过程中不会发生扩容，例如，HashTable的初始容量是100，而在HashTable的整个使用过程中，它最多存储了30个元素，30除以0.75等于40，如果HashTable要扩容，它存储的元素数量需要大于100乘以0.75 = 75，而在整个使用过程中最多存储30个元素，所以在使用过程中，不会发生扩容。当然了，如果不从业务实际出发，单纯为了不让HashTable扩容而设置一个比较大的初始容量，这也会造成内存浪费，因此在使用HashTable时，一定要从实际业务出发。
如果有很多数据元素需要存储到HashTable中，创建一个初始容量足够大的HashTable可以达到更高效的存储数据的效果，因为它减少了reHash的次数。当然了，一切要以实际业务需要。
使用Iterator遍历HashTable时，也是Fail-Fast，当HashTable的Iterator对象创建后，如果HashTable的结构发生变体了，再使用此Iterator时，则会有异常抛出，在程序设计和使用时，应该主动避免这种情况，而不是使用try-catch去捕获和处理此异常。这个和ArrayList等数据结构的处理方案是一样的。
HashTable是线程安全的，如果不考虑线程安全的话，建议使用HashMap，如果需要设计和使用线程安全的高并发的业务，推荐使用java.util.concurrent.ConcurrentHashMap代替HashTable。
HashTable的存储结构为数组+链表，
private transient Entry<?,?>[] table;
每个插入的key-value对被封装成一个Entry<K, V>对象，put方法执行后，把Entry对象放置于table[]的指定位置，如果发生冲突，则使用链表在冲突的元素后面插入。
函数介绍
- public synchronized boolean contains(Object value)
这个方法的时间复杂度比containsKey(Object key)的时间复杂度要高很多
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
// table为数组，直接使用for循环遍历
for (int i = tab.length ; i-- > 0 ;) {
// 遍历到第i个元素后，查看它的value是否和参数value相equals
for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
// 此操作比较耗时，最坏情况，它需要遍历完数组和所有链表
}
- public synchronized boolean containsKey(Object key)
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;
// 取得key的hashCode值
int hash = key.hashCode();
// 根据定位方法找到其在tab[]数组中的位置，到此所有操作都是常数时间复杂度
int index = (hash & 0x7FFFFFFF) % tab.length;
// 遍历Entry后面的链表查找key
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
// 此操作的时间复杂度为O(n)，其实跟常数差不多，因此链表的长度不会很长
}
- protected void rehash()
rehash()操作就是为了扩容，也是为了更高效地存取数据，此操作自动进行，也就是在执行put函数时，如果发现capacity或是load factor超限，则自动执行rehash操作。
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
// 扩容，左移操作，容量double，但是为什么加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++;
// 此处如果loadFactor不大于1的话，newCapacity * loadFactory永远不会大于MAX_ARRAY_SIZE + 1，可是从实际代码上看，loadFactory确实是不会大于1，不知为何添加这个Math.min函数的判断
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;
}
}
}
为什么rehash()函数没有被synchronized关键字修饰呢？
这需要从函数的调用逻辑看，rehash在private void addEntry(int hash, K key, V value, int index)函数中调用，而addEntry被public synchronized V put(K key, V value)函数调用，而put函数被synchronized关键字修饰了，从synchronized关键字的传递性和作用阈来看，addEntry和rehash都是发生在put函数的作用阈中，所以rehash函数不需要用synchronized关键字修饰。
网友评论