分析java.util.Hashtable源码

博客 动态
0 118
优雅殿下
优雅殿下 2022-07-15 17:01:51
悬赏:0 积分 收藏

分析 java.util.Hashtable 源码

分析 java.util.Hashtable 源码 简单描述Hashtable的结构以及主要的一些功能

概述

基于J11,该类已经淘汰,如果使用线程安全的则用 ConcurrentHashMap ,用线程不安全的则使用 HashMap 。仅与HashMap进行比较

结构以及依赖关系

HashTable 的结构如下图

当遇到有同样 Hash 值的情况,会通过链表来解决冲突问题(链接法,通过链表解决冲突问题)。
链接法会随着冲突的增多导致查询时间越来越慢。会出现一种恶劣的情况,当散列算法特别差时;元素总数n和某个槽位数 m 中的 k 相等,如下图所示

在这种情况下,查找的时间为 $O(1+a)$ 其中 $O(1)$ 为hash

通过下图可以得知 Hashtable 与其他类的关系

classDiagramdirection BTclass Cloneable {<<Interface>>}class Dictionary~K, V~class Hashtable~K, V~class Map~K, V~ {<<Interface>>}class Serializable {<<Interface>>}Hashtable~K, V~ ..> Cloneable Hashtable~K, V~ --> Dictionary~K, V~ Hashtable~K, V~ ..> Map~K, V~ Hashtable~K, V~ ..> Serializable

实际上,Hashtable中的每个元素都是一个 Map.Entry<k,v> ,Entry 是 Map 的集合形式 用来遍历Map 。Hashtable实现了该接口,Hashtable就是一个集合,不过存储的是一个一个链表。

private static class Entry<K,V> implements Map.Entry<K,V> {	final int hash;	final K key;  	V value;  	Entry<K,V> next;		public K getKey(){...}	public V getValue(){...}	public V setValue(V value){...}}

Hashtable有几个关键的字段需要注意:

private int threshold; // 可容纳的极限长度,容量*负载因子private float loadFactor; // 负载因子 该值默认为0.75

如果把Hashtbale比做桶,负载因子就表明一桶水能装半桶还是装满桶还是装四分之一桶。
负载因子越大,能装的水就越多。负载因子总和临界值配合,临界值用来表示什么时候扩容,也就是水装不下了得换一个大一点的桶装水。Hashtable每一次扩容都会扩大到原来的两倍大。

负载因子是对时间和空间的平衡,当负载因子增大空间会比较充足就不需要总是扩容,空间用的较多;如果负载因子小需要不断扩容,但是空间用的少。

通过一个put方法来了解

下图简述了put的流程

计算位置

Hashtable中计算位置特别简单,就是简单的除法

Entry<?,?> tab[] = table;int hash = key.hashCode();  int index = (hash & 0x7FFFFFFF) % tab.length;

插入元素

首先,Hashtable需要知道当前put操作是更新旧值还是插入新值。如果更新旧值就返回旧值并更新它
下面就是一个不断查找链表的过程

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

如果是插入新值则创建一个 Entry 并插入,这是在容量没有超过临界值的情况:

Entry<K,V> e = (Entry<K,V>) tab[index];  tab[index] = new Entry<>(hash, key, value, e);  count++;  modCount++;

当然,如果容量超过临界值则需要扩容

扩容

if (count >= threshold) {      // 扩容,并重新计算每个元素的hash值    rehash();  	// 扩容之后插入新值    tab = table;      hash = key.hashCode();      index = (hash & 0x7FFFFFFF) % tab.length;  }

扩容的关键是 rehash() 这个方法。该方法也很简单,只有以下几个步骤:

  1. 计算新的临界值
  2. 新临界值超过最大能接受的容量则不再扩充
  3. 创建一个新table(新的大桶)
  4. 逐个计算hash值并重新装填table

线程安全性

Hashtable是线程安全的,主要是通过为每个方法加入一个同步锁来解决,如put方法

public synchronized V put(K key, V value) {...}

但是这样性能还是比较低的,同时不能保证组合方法的线程安全性。
例如 get 和 remove

public V getAndRemove(Object o){	V v = get(o);	remove(o);	return v;}

这样是不能保证线程安全的

posted @ 2022-07-15 16:58 Xrtero 阅读(0) 评论(0) 编辑 收藏 举报
回帖
    优雅殿下

    优雅殿下 (王者 段位)

    2018 积分 (2)粉丝 (47)源码

    小小码农,大大世界

     

    温馨提示

    亦奇源码

    最新会员