HashTable详解

2018-07-03 01:01:57来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

  为了成功从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);}  

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

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

  提示:iteratorfail-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更快。这个方法被自动调用当在hashtableK的数量超过这个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;
            }
        }
}

三、hashtable的性质,参见hashtable的结构:

  1.hashtable不接受NULL值;

  2.hashtable是线程同步的;

  3.capacity扩张方法: newCapacity = (oldCapacity << 1) + 1;

  4.初始容量:this(11, 0.75f);

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:图解线程池工作机制,手写线程池?

下一篇:6、SpringBoot+Mybatis整合------参数传递