转载

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折
说给你听

本文目录
随机标签
书籍教程
Java入门教程 bootstrap3 CSS springboot-demo Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 Struts2教程 MongoDB教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 SpringCloud ANTLR教程 Hive教程 java实例教程 Ant教程 Hazelcast教程 Elastic-Job-Lite XStream教程 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 WebService CXF学习 Hadoop教程 solr教程 JPA教程 ActiveMQ中文指南 Java内存模型 dubbo教程 Linux入门视频教程
近期评论
  1. 1 Spring Boot集成Swagge快速入门Demo
  2. 2 Spring Boot集成sitemapgen4j实现网站地图生成
  3. 3 Spring Boot集成oauth2快速入门demo
  4. 4 Spring Boot集成Spring AI实现快速接入openAI
  5. 5 Spring Boot集成Spring Session快速入门Demo
  6. 6 Spring Boot集成RabbitMQ快速入门Demo
  7. 7 Spring Boot集成Quartz快速入门Demo
  8. 8 Spring Boot集成Mybatis Plus快速入门Demo
  9. 9 Spring Boot集成zipkin快速入门Demo
  10. 10 能用365块大洋去解决的事，千万不要用时间
网站信息
  • 文章总数：155,471 篇
  • 文件总数：468,751 个
  • 标签总数：2,271 个
  • 分类总数：90 个
  • 留言数量：2,542 条
  • 在线人数：637 人
  • 运行天数：4,200天
  • 最后更新：2024年04月27日04点
Loading...

其他链接

关于本站

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

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

问题交流

[HBLOG]公众号 HBLOG HBLOG