资讯专栏INFORMATION COLUMN

Hashtable源码分析_JDK1.8版本

tunny / 2079人阅读

摘要:简介声明文章均为本人技术笔记,转载请注明出处声明和一样也是散列表,存储元素也是键值对继承于类类声明了操作键值对的接口方法,实现接口定义键值对接口大部分类用修饰,证明是线程安全的基本数据结构键值对数组,每个本质上是一个单向链表的表头阈值装填因

Hashtable简介 声明

文章均为本人技术笔记,转载请注明出处https://segmentfault.com/u/yzwall

Hashtable声明

public class Hashtable extends Dictionary implements Map, Cloneable, java.io.Serializable

Hashtable和HashMap一样也是散列表,存储元素也是键值对;
Hashtable继承于Dictionary类(Dictionary类声明了操作键值对的接口方法),实现Map接口(定义键值对接口);
Hashtable大部分类用synchronized修饰,证明Hashtable是线程安全的;

Hashtable基本数据结构

private transient Entry[] table:键值对/Entry数组,每个Entry本质上是一个单向链表的表头

private int threshold:rehash阈值

private float loadFactor:装填因子

private transient int modCount = 0: Hashtable结构化修改次数,用来实现fail-fast机制;

private transient volatile Set> entrySet:Hastable视图,键值对集合;

private transient volatile Set keySetHastable视图,key集,Hashtable中key不可重复;

private transient volatile Collection valuesHastable视图,value集合,可重复;

Hashtable中key和value是一对多关系;

键值对/Entry
private static class Entry implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Entry next;
    ...
    // 计算键值对的hashCode
    public int hashCode() {
        // "^" 按位异或, hash在调用构造器时传入
        return hash ^ Objects.hashCode(value);
    }
}
Hash函数

键值对

Hashtable方法分析 public synchronized boolean contains(Object value)

public boolean containsValue(Object value)内部调用contains(value);

判断是否含有该value的键值对,在Hashtable中hashCode相同的Entry用链表组织,hashCode不同的存储在Entry数组table中;

// in contains() method.
Entry tab[] = table;
// 查找:遍历所有Entry链表
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;
public synchronized boolean containsKey(Object key)
散列分布策略

int index = (hash & 0x7FFFFFFF) % tab.length;
计算键值对的桶位(本质是键值对在tab数组中的索引),Hashtable本质上采用除数取余法进行散列分布,模运算效率较低

Hash函数

int hash = key.hashCode() Hashtable直接调用key的hashCode()计算hashCode;

containsKey方法体
Entry tab[] = table;
int hash = key.hashCode();
/**
 * 计算index, % tab.length防止数组越界
 * index表示key对应entry所在链表表头
 */
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 true;
    }
}
return false;

public synchronized V get(Object key):根据指定key查找对应value,查找原理与containsKey相同,查找成功返回value,否则返回null;

public synchronized V put(K key, V value)

设置键值对,key和value都不可为null,设置顺序:

如果Hashtable含有key,设置(key, oldValue) -> (key, newValue);

如果Hashtable不含有key, 调用addEntry(...)添加新的键值对;

private void addEntry(int hash, K key, V value, int index)

当键值对个数超过阈值,先进行rehash然后添加entry,否则直接添加entry;

public synchronized V remove(Object key)

remove操作,计算key所在链表表头table[index],然后进行单向链表的节点删除操作

public synchronized Object clone()

对Hashtable的浅拷贝操作,浅拷贝所有bucket(单向链表组织形式)的表头;

protected void rehash()

当Hashtable中键值对总数超过阈值(容量*装载因子)后,内部自动调用rehash()增加容量,重新计算每个键值对的hashCode;
int newCapacity = (oldCapacity << 1) + 1计算新容量 = 2 * 旧容量 + 1;并且根据新容量更新阈值;

...
for (int i = oldCapacity ; i-- > 0 ;) {
    // 拷贝每个Entry链表
    for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
        Entry e = old;
        old = old.next;
        // 重新计算每个Entry链表的表头索引(rehash)
        int index = (e.hash & 0x7FFFFFFF) % newCapacity;
        // 开辟链表节点
        e.next = (Entry)newMap[index];
        // 拷贝
        newMap[index] = e;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66972.html

相关文章

  • 集合框架源码学习之HashMap(JDK1.8)

    摘要:所谓拉链法就是将链表和数组相结合。若遇到哈希冲突,则将冲突的值加到链表中即可。在编写程序中,要尽量避免。 目录: 0-1. 简介 0-2. 内部结构分析   0-2-1. JDK18之前   0-2-2. JDK18之后 0-3. LinkedList源码分析   0-3-1. 构造方法   0-3-2. put方法   0-3-3. get方法   0-3-4. resize方法 ...

    yangrd 评论0 收藏0
  • 这几道Java集合框架面试题在面试中几乎必问

    摘要:若遇到哈希冲突,则将冲突的值加到链表中即可。之后相比于之前的版本,之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值默认为时,将链表转化为红黑树,以减少搜索时间。有序,唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容: Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

    bigdevil_s 评论0 收藏0
  • HashMap源码分析(一):JDK源码分析系列

    摘要:当一个值中要存储到的时候会根据的值来计算出他的,通过哈希来确认到数组的位置,如果发生哈希碰撞就以链表的形式存储在源码分析中解释过,但是这样如果链表过长来的话,会把这个链表转换成红黑树来存储。 正文开始 注:JDK版本为1.8 HashMap1.8和1.8之前的源码差别很大 目录 简介 数据结构 类结构 属性 构造方法 增加 删除 修改 总结 1.HashMap简介 H...

    wdzgege 评论0 收藏0
  • JDK源码(容器篇)

    摘要:三系列用于保存键值对,无论是,还是已弃用的或者线程安全的等,都是基于红黑树。是完全基于红黑树的,并在此基础上实现了接口。可以看到,只有红黑树,且红黑树是通过内部类来实现的。 JDK容器 前言 阅读JDK源码有段时间了,准备以博客的形式记录下来,也方便复习时查阅,本文参考JDK1.8源码。 一、Collection Collection是所有容器的基类,定义了一些基础方法。List、Se...

    Soarkey 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<