Java集合 Hashtable

wuchangjian2021-11-06 11:32:01编程学习

Hashtable

简介

  1. HashTable继承Dictionary类,实现Map接口。

    其中Dictionary类是任何可将键映射到相应值的类(如 Hashtable)的抽象父类。
    在任何一个 Dictionary 对象中,每个键至多与一个值相关联。Map是**“key-value键值对”**接口。

  2. 每个键和每个值都是一个对象。

  3. HashTable采用"拉链法"实现哈希表,它定义了几个重要的参数:table、count、threshold、loadFactor、modCount

  • table:为一个Entry[]数组类型,Entry代表了“拉链”的节点,每一个Entry代表了一个键值对,哈希表的"key-value键值对"都是存储在Entry数组中的。
  • count:HashTable的大小,注意这个大小并不是HashTable的容器大小,而是他所包含Entry键值对的数量。
  • threshold:Hashtable的阈值,用于判断是否需要调整Hashtable的容量。threshold的值=“容量*加载因子”
  • loadFactor:加载因子。
  • modCount:用来实现“fail-fast”机制的(也就是快速失败)。所谓快速失败就是在并发集合中,其进行迭代操作时,若有其他线程对其进行结构性的修改,这时迭代器会立马感知到,并且立即抛出ConcurrentModificationException异常,而不是等到迭代完成之后才告诉你(你已经出错了)。
  1. 默认开始的时候,容量为11,加载因为为0.75

  2. 每次扩容2倍+1

  3. 线程安全

  4. 键和值都不能为 null

  5. 添加已有key元素则覆盖,新key则放在链表最前面,并且不会树化

构造方法

Hashtable() 构造一个新的,空的散列表,默认初始容量(11)和负载因子(0.75)。
Hashtable(int initialCapacity) 构造一个新的,空的哈希表,具有指定的初始容量和默认负载因子(0.75)。
Hashtable(int initialCapacity, float loadFactor) 构造一个新的,空的哈希表,具有指定的初始容量和指定的负载因子。
Hashtable(Map<? extends K,? extends V> t) 构造一个与给定Map相同的映射的新哈希表。

方法

voidclear() 清除此散列表,使其不包含键。
Objectclone() 创建这个散列表的浅拷贝。
Vcompute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 尝试计算指定键的映射及其当前映射的值(如果没有当前映射, null )。
VcomputeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 如果指定的键尚未与某个值相关联(或映射到 null ),则尝试使用给定的映射函数计算其值,并将其输入到此映射中,除非 null
VcomputeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 如果指定的密钥的值存在且非空,则尝试计算给定密钥及其当前映射值的新映射。
booleancontains(Object value) 测试一些键映射到这个哈希表中的指定值。
booleancontainsKey(Object key) 测试指定的对象是否在此哈希表中的键。
booleancontainsValue(Object value) 如果此哈希表将一个或多个键映射到此值,则返回true。
Enumeration<V>elements() 返回此散列表中值的枚举。
Set<Map.Entry<K,V>>entrySet() 返回此Map中包含的映射的Set视图。
booleanequals(Object o) 根据Map界面中的定义,将指定的对象与此Map进行比较以相等。
voidforEach(BiConsumer<? super K,? super V> action) 对此映射中的每个条目执行给定的操作,直到所有条目都被处理或操作引发异常。
Vget(Object key) 返回到指定键所映射的值,或 null如果此映射包含该键的映射。
VgetOrDefault(Object key, V defaultValue) 返回到指定键所映射的值,或 defaultValue如果此映射包含该键的映射。
inthashCode() 按照Map界面中的定义返回此Map的哈希码值。
booleanisEmpty() 测试这个哈希表是否将值映射到值。
Enumeration<K>keys() 返回此散列表中键的枚举。
Set<K>keySet() 返回此Map中包含的键的Set视图。
Vmerge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) 如果指定的键尚未与值相关联或与null相关联,则将其与给定的非空值相关联。
Vput(K key, V value) 将指定的 key映射到此 key value中指定的value。
voidputAll(Map<? extends K,? extends V> t) 将所有从指定Map的映射复制到此散列表。
VputIfAbsent(K key, V value) 如果指定的键尚未与值相关联(或映射到 null )将其与给定值相关联并返回 null ,否则返回当前值。
protected voidrehash() 增加这个散列表的内部重组能力,从而更有效地适应和访问其条目。
Vremove(Object key) 从此散列表中删除键(及其对应的值)。
booleanremove(Object key, Object value) 仅当指定的密钥当前映射到指定的值时删除该条目。
Vreplace(K key, V value) 只有当目标映射到某个值时,才能替换指定键的条目。
booleanreplace(K key, V oldValue, V newValue) 仅当当前映射到指定的值时,才能替换指定键的条目。
voidreplaceAll(BiFunction<? super K,? super V,? extends V> function) 将每个条目的值替换为对该条目调用给定函数的结果,直到所有条目都被处理或该函数抛出异常。
intsize() 返回此哈希表中的键数。
StringtoString() 以一组条目的形式返回此 Hashtable对象的字符串表示形式,其括在大括号中,并以ASCII字符“ , ”(逗号和空格)分隔。
Collection<V>values() 返回此Map中包含的值的Collection视图。

源码分析

public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

定位index的方法:

int index = (hash & 0x7FFFFFFF) % tab.length;

put()方法:

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 因为hash可能为负数,所以就先和0x7FFFFFFF相与
    // 在HashMap中,是用 (table.length - 1) & hash 计算要放置的位置
    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;
}

在这里插入图片描述

  • ① 由于直接使用key.hashcode(),而没有向hashmap一样先判断key是否为null,所以key为null时,调用key.hashcode()会出错,所以hashtable中key也不能为null;
  • ②hashtable中对hash值进行寻址的方法为hash%数组长度(与hashmap的index = hash & (tab.length – 1)不同,所以不要求数组长度必须为2的n次方);
  • ③遍历table[index]所连接的链表,查找是否已经存在key与需要插入的key值相同的节点,如果存在则直接更新value,并返回旧的value;
  • ④如果table[index]所连接的链表上不存在相同的key,则通过addEntry()方法将新节点加到链表的开头

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++;
}
  • 如果加入新节点后,hashtable中元素的个数超过了阈值threshold,则利用rehash()对数组进行扩容。
  • e=table[index],并将新节点加在了e节点的前面,最后table[index]=e。相当于把把新节点放在table[index]位置,即整个链表的首部。

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;
        }
    }
}

rehash()方法中我们可以看到容量扩大两倍+1,同时需要将原来HashTable中的元素一一复制到新的HashTable中,这个过程是比较消耗时间的,同时还需要重新计算hashSeed的,毕竟容量已经变了。

关于阀值: 比如初始值11、加载因子默认0.75,那么这个时候阀值threshold=8 (11 * 0.7 5),当容器中的元素达到8时,HashTable进行一次扩容操作,容量 = 8 * 2 + 1 = 17,而阀值threshold = 17*0.75 = 13,当容器元素再一次达到阀值时,HashTable还会进行扩容操作,依次类推。

get()方法:

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

遍历table[index]链表,找到key值相同的节点的value返回,注意同样在该过程中使用到了key的equal方法,所以key被应用与hashtable时不仅要实现hashcode方法还有实现equal方法。

als(key)) {
return (V)e.value;
}
}
return null;
}


遍历table[index]链表,找到key值相同的节点的value返回,注意同样在该过程中使用到了key的equal方法,所以key被应用与hashtable时不仅要实现hashcode方法还有实现equal方法。



> 附源码注释文章: https://www.cnblogs.com/wupeixuan/p/8620197.html

相关文章

输出类型SPER能自动删除公司间STO里的内向交货单?

输出类型SPER能自动删除公司间STO里的内向交货单?

输出类型SPER能自动删除公司间STO里的内向交货单? 在公司间ST...

Hystrix断路器

分布式系统面临的问题: 首先先了解下分布式系统面临的问题:...

6运算符(很简单我就调难一点的来说)

算数运算符 运算符名称实例+加x + y-减x - y*乘x...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。