当前位置：首页 > news >正文

HashTable详解

news 来源：原创 2024/5/6 13:27:51

一、HashTable简介：这里给出jdk1.8的中文翻译：

　　这个类实现了一个hash table,能够map K到V。任何非空对象可以被用做K或V.

　　为了成功从hashtable中存取对象，被当作K的对象必须实现hashCode()和equals()方法。

　　一个Hashtable实例有2个能影响其表现的参数：initial capacity(初始容量)和load factor(加载因子)。容量是hash table中桶的数量，初始容量是hash table 被创建时的容量。提示：hash table是开放的：当“哈希碰撞（hash collision）”的情况下,一个单一桶存储多个必须被顺序查找的entry。load factor是一个方法关于多满的hash table被允许得到，在他的容量自动增长之前。初始容量和加载因子仅仅提示了实现。像何时和是否进行rehash的精确的被调用的细节是依赖实现的。

　　通常，默认加载因子(.75)提供了时间和空间开销的较好的平衡。更大的值减少了空间开销，但是增加了寻找entry（在大多数hashtable操作中被反映，包括get()和put()方法）的时间开销。

　　初始容量控制了奢侈空间和所需rehash操作的平衡，rehash操作是耗时的。rehash将从不发生，如果初始容量比Hashtable将包含的entry最大数除以其加载因子更大。可是，设置初始容量太高会浪费空间。

　　如果大量的entry写入Hashtable，创建它通过一个足够大的容量可以允许entry被快速插入，而不是让它执行自动rehash来达到其所需的空间大小。

　　给一个创建数字hashtable的实例。它使用数据作为K：

1 Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
2      numbers.put("one", 1);
3      numbers.put("two", 2);
4      numbers.put("three", 3);

　　取值操作，使用以下代码：

1 Integer n = numbers.get("two"); 2 if (n != null) { 3 System.out.println("two = " + n);} 　

　　通过collections的iterator()方法是fail-fast机制的: 如果在iterator被创建后发生结构上的修改，将抛出ConcurrentModificationException异常。从而，在面对同步修改操作，iterator快速利落的失败，而不是冒着风险，不确定的行为和不确定的时间在将来. 　

　　通过Hashtable的K和元素方法返回的枚举不是fail-fast机制的。　

　　提示：iterator的fail-fast行为不被保证，通常来说，不可能保证防止异步的同步修改方法。Fail-fast iterators尽力抛出ConcurrentModificationException异常，因此，依靠这个异常来保证程序正确性是错误的：这近被用做检测BUG.

　　作为Java 2 platform v1.2版本, 这个类被改装实现Map接口，成为了Java Collections Framework的成员。不像新的集合实现类, Hashtable是同步的。如果一个线程安全的实现不被需要，建议使用HashMap代替Hashtable。如果一个线程安全的高同步的实现被需要，建议使用 ConcurrentHashMap代替Hashtable。

　　　　---------------------------- 以上便是jdk1.8中ArrayList的中文翻译 ----------------------------

二、HashTable数据结构：

　　1.基本结构：可见其实一个数据链表。

private transient Entry<?,?>[] table;
//Entry的结构方法
private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
        //...等等操作不一列举
}

　　2.GET方法：

 1  public synchronized V get(Object key) {
 2         Entry<?,?> tab[] = table;
 3         int hash = key.hashCode();
 4         int index = (hash & 0x7FFFFFFF) % tab.length;
 5         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 6             if ((e.hash == hash) && e.key.equals(key)) {
 7                 return (V)e.value;
 8             }
 9         }
10         return null;
11 }

　　3.PUT方法：

  public synchronized V put(K key, V value) {
        // 确保值非空
        if (value == null) {
            throw new NullPointerException();
        }

        // 确保K在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;
    }

　　4.rehash方法：增加容量并且在内部重组hashtable,为了完成和进入它的entry更快。这个方法被自动调用当在hashtable中K的数量超过这个hashtable的容量和加载因子。

@SuppressWarnings("unchecked")
    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;
            }
        }
}