转载

Java源码系列(10) -- Hashtable

一、类签名

HashTable 的方式使用 synchronized 修饰以保证线程安全，相比 HashMap 来说优化策略少。由于 HashTable 的实现相当原始，源码没有阅读难度。 

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

二、数据成员

// 哈希表
private transient Entry<?,?>[] table;

// 元素总数
private transient int count;

// 重哈希阀值
private int threshold;

// 负载因子
private float loadFactor;

// 结构修改次数，或元素添加次数
private transient int modCount = 0;

三、构造方法

// 指定初始容量和负载因子
public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

// 仅指定初始容量
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

// 默认构造方法，初始容量为11，初始负载因子为0.75
public Hashtable() {
    this(11, 0.75f);
}

// 使用指定哈希表进行初始化
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

Hashtable(Void dummy) {}

四、成员方法

4.1 包含

// 查找是否有指定值
public synchronized boolean contains(Object value) {
    // 不支持value为null
    if (value == null) {
        throw new NullPointerException();
    }
    
    // 遍历哈希表，查找是否有指定值
    Entry<?,?> tab[] = table;
    // 从哈希表的拉链首元素开始往后遍历
    for (int i = tab.length ; i-- > 0 ;) {
        for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
            // 直到找到对应值
            if (e.value.equals(value)) {
                return true;
            }
        }
    }
    return false;
}

// 查找是否有指定key
public synchronized boolean containsKey(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) {
        // 匹配哈希值且key完全相同
        if ((e.hash == hash) && e.key.equals(key)) {
            return true;
        }
    }
    return false; // 不匹配
}

4.2 获取

// 获取指定key的value，没有则返回null
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode(); // 计算key的哈希值
    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; // 没有匹配到指定key，返回null的value
}

// 获取指定key的value，没有则返回defaultValue
@Override
public synchronized V getOrDefault(Object key, V defaultValue) {
    // 依赖get(key)方法，然后看是否为null再返回defaultValue
    V result = get(key);
    return (null == result) ? defaultValue : result;
}

4.3 重哈希

// 数组最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 // 扩容并冲哈希所有键值
@SuppressWarnings("unchecked")
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 上溢检查
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // 已经到达最大值，不能再扩容
            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; 
        }
    }
}

4.4 添加

private void addEntry(int hash, K key, V value, int index) {
    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // 超过阀值大小，哈希表执行扩容
        rehash();

        tab = table;
        hash = key.hashCode(); // 取键的哈希值
        index = (hash & 0x7FFFFFFF) % tab.length; // 算哈希索引
    }

    // 创建新的Entry，存入key和value
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e); // 把Entry放入哈希索引中
    count++; // 总数递增
    modCount++; // 修改次数递增
}

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException();
    }

    Entry<?,?> tab[] = table;
    int hash = key.hashCode(); // 计算key的哈希值
    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)) {
            // 如果已存在相同key的Enty，则替换该Entry的value
            V old = entry.value;
            entry.value = value;
            return old; // 返回旧的value
        }
    }
    
    // 不存在该Entry，创建新Entry
    addEntry(hash, key, value, index);
    return null; // 创建新的Entry就一定返回null作为value
}

// 递归调用put()
public synchronized void putAll(Map<? extends K, ? extends V> t) {
    for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
        put(e.getKey(), e.getValue());
}

// 仅在key对应的Entry不存在的时候才创建的新Entry，否则直接返回旧value
@Override
public synchronized V putIfAbsent(K key, V value) {
    Objects.requireNonNull(value);

    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)) { // 从拉链匹配对应Entry
            V old = entry.value;
            // 旧value为null，直接放入
            if (old == null) {
                entry.value = value;
            }
            return old; // 直接返回oldValue
        }
    }
    
    // 没有旧的Entry，创建新的并存入
    addEntry(hash, key, value, index);
    return null;
}

4.5 清除

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length; // 计算哈希桶索引
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index]; // 获取哈希桶
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        // 哈希值相同，且key相同
        if ((e.hash == hash) && e.key.equals(key)) {
            // 节点从链表中解除引用
            if (prev != null) {
                prev.next = e.next; // 中间节点解除引用
            } else {
                tab[index] = e.next; // 头结点解除引用
            }
            modCount++; // 修改递增
            count--; // 元素数量递减
            V oldValue = e.value; // 获取旧值
            e.value = null; // 置空回收
            return oldValue;
        }
    }
    return null; // key匹配不到Entry
}

// 参考删除方法，此方法只是增加检查value是否一致，仅在一致的时候才移除
@Override
public synchronized boolean remove(Object key, Object value) {
    Objects.requireNonNull(value);

    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length; // 计算哈希桶索引
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index]; // 获取哈希桶
    for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            e.value = null; // 置空以便GC
            modCount++;
            count--;
            return true;
        }
    }
    return false;
}

// 清空哈希表的所有元素，表长度不会改变
public synchronized void clear() {
    Entry<?,?> tab[] = table;
    for (int index = tab.length; --index >= 0; )
        tab[index] = null;
    modCount++;
    count = 0;
}

4.6 比较

public synchronized boolean equals(Object o) {
    if (o == this)
        return true;

    if (!(o instanceof Map))
        return false;
    Map<?,?> t = (Map<?,?>) o;
    if (t.size() != size())
        return false;

    try {
        for (Map.Entry<K, V> e : entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            if (value == null) {
                if (!(t.get(key) == null && t.containsKey(key)))
                    return false;
            } else {
                if (!value.equals(t.get(key)))
                    return false;
            }
        }
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }

    return true;
}

public synchronized int hashCode() {
    int h = 0;
    if (count == 0 || loadFactor < 0)
        return h; // 返回0

    loadFactor = -loadFactor;
    Entry<?,?>[] tab = table;
    for (Entry<?,?> entry : tab) {
        while (entry != null) {
            h += entry.hashCode();
            entry = entry.next;
        }
    }

    loadFactor = -loadFactor;

    return h;
}

4.7 替换

@Override
public synchronized boolean replace(K key, V oldValue, V newValue) {
    Objects.requireNonNull(oldValue);
    Objects.requireNonNull(newValue);
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length; // 哈希桶索引
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index]; // 获取哈希桶
    for (; e != null; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) { // 查找是否有key对应的Entry
            if (e.value.equals(oldValue)) {
                e.value = newValue; // 同时还有oldValue匹配，才能替换为newValue
                return true; // 替换成功
            } else {
                return false; // 替换失败
            }
        }
    }
    return false;
}

// 用key查找对应Entry，并替换oldValue为value
@Override
public synchronized V replace(K key, V value) {
    Objects.requireNonNull(value);
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length; // 计算哈希索引大概位置
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index]; // 选取哈希桶
    for (; e != null; e = e.next) {
        // 逐个遍历，查找是否有对应Entry
        if ((e.hash == hash) && e.key.equals(key)) {
            V oldValue = e.value;
            e.value = value;
            return oldValue; // 返回旧值
        }
    }
    return null; // 没有对应key，返回null
}

五、哈希项

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash; // 哈希值
    final K key; // 键
    V value; // 值
    Entry<K,V> next; // 下一项的引用
    
    // 构造方法
    protected Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }
    
    // Clone
    @SuppressWarnings("unchecked")
    protected Object clone() {
        return new Entry<>(hash, key, value,
                              (next==null ? null : (Entry<K,V>) next.clone()));
    }
    
    // 获取键
    public K getKey() {
        return key;
    }
    
    // 获取值
    public V getValue() {
        return value;
    }
    
    // 设置值
    public V setValue(V value) {
        if (value == null)
            throw new NullPointerException();
            
        // 设置新值并返回新值
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;

        return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
           (value==null ? e.getValue()==null : value.equals(e.getValue()));
    }

    public int hashCode() {
        return hash ^ Objects.hashCode(value);
    }

    public String toString() {
        return key.toString()+"="+value.toString();
    }
}

  • 上一篇

    Java源码系列(9) -- HashMap

原文  https://phantomvk.github.io/2018/07/02/HashTable/
正文到此结束
所属分类： Java 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 java-demo Maven教程 springcloud-demo hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 ANTLR教程 SpringCloud Ant教程 java实例教程 Hazelcast教程 XStream教程 Elastic-Job-Lite 深入浅出MyBatis ibaties教程 SVN教程 rabittmq教程 Hadoop教程 solr教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 使用 Docker 打包和运行 Vue 应用
  2. 2 Dependency Check命令行方式扫描jar包的安全漏洞
  3. 3 maven使用Dependency-Check来扫描安全漏洞
  4. 4 使用sonarqube分析代码质量
  5. 5 使用screw来对比数据库表和字段差异
  6. 6 Spring Boot 实现防盗链功能
  7. 7 在Spring Boot中的实现国际化（i18n）
  8. 8 一个用于 SMB/CIFS 网络的 Java 库-JCIFS
  9. 9 Spring Boot 3.x嵌入MongoDB 进行测试
  10. 10 java如何解析和生成yaml文件？
网站信息
  • 文章总数：82,737 篇
  • 文件总数：284,312 个
  • 标签总数：2,416 个
  • 分类总数：85 个
  • 留言数量：2,559 条
  • 在线人数：651 人
  • 运行天数：4,439天
  • 最后更新：2024年12月22日19点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG