Map全家桶之HashTable

一、摘要

在集合系列的第一章,咱们了解到,Map 的实现类有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties 等等。


image.png

本文主要从数据结构和算法层面,探讨 Hashtable 的实现,如果有理解不当之处,欢迎指正。

二、 介绍

Hashtable 一个元老级的集合类,早在 JDK 1.0 就诞生了,而 HashMap 诞生于 JDK 1.2,在实现上,HashMap 吸收了很多 Hashtable 的思想,虽然二者的底层数据结构都是 数组 + 链表(不知道链表的可以看我之前的文章) 结构,具有查询、插入、删除快的特点,但是二者又有很多的不同。

打开 Hashtable 的源码可以看到,Hashtable 继承自 Dictionary,而 HashMap 继承自 AbstractMap。

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

HashMap 继承自 AbstractMap,HashMap 类的定义如下:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    .....
}

其中 Dictionary 类是一个已经被废弃的类,翻译过来的意思是这个类已经过时,新的实现应该实现 Map 接口而不是扩展此类,这一点我们可以从它代码的注释中可以看到:

/**
 * <strong>NOTE: This class is obsolete.  New implementations should
 * implement the Map interface, rather than extending this class.</strong>
 */
public abstract
class Dictionary<K,V> {
    ......
}

Hashtable 和 HashMap 的底层是以数组来存储,同时,在存储数据通过key计算数组下标的时候,是以哈希算法为主,因此可能会产生哈希冲突的可能性。
通俗的说呢,就是不同的key,在计算的时候,可能会产生相同的数组下标,这个时候,如何将两个对象放入一个数组中呢?
而解决哈希冲突的办法,有两种,一种开放地址方式(当发生 hash 冲突时,就继续以此继续寻找,直到找到没有冲突的hash值),另一种是拉链方式(将冲突的元素放入链表)。

Java Hashtable 采用的就是第二种方式,拉链法!

于是,当发生不同的key通过一系列的哈希算法计算获取到相同的数组下标的时候,会将对象放入一个数组容器中,然后将对象以单向链表的形式存储在同一个数组下标容器中,就像链子一样,挂在某个节点上,如下图:
image.png

与 HashMap 类似,Hashtable 也包括五个成员变量:

/**由Entry对象组成的数组*/
private transient Entry[] table;

/**Hashtable中Entry对象的个数*/
private transient int count;

/**Hashtable进行扩容的阈值*/
private int threshold;

/**负载因子,默认0.75*/
private float loadFactor;

/**记录修改的次数*/
private transient int modCount = 0;

具体各个变量含义如下:

  • table:表示一个由 Entry 对象组成的链表数组,Entry 是一个单向链表,哈希表的key-value键值对都是存储在 Entry 数组中的;
  • count:表示 Hashtable 的大小,用于记录保存的键值对的数量;
  • threshold:表示 Hashtable 的阈值,用于判断是否需要调整 Hashtable 的容量,threshold 等于容量 * 加载因子;
  • loadFactor:表示负载因子,默认为 0.75;
  • modCount:表示记录 Hashtable 修改的次数,用来实现快速失败抛异常处理;

接着来看看Entry这个内部类,Entry用于存储链表数据,实现了Map.Entry接口,本质是就是一个映射(键值对),源码如下:

private static class Entry<K,V> implements Map.Entry<K,V> {
         /**hash值*/
        final int hash;
        /**key表示键*/
        final K key;
        /**value表示值*/
        V value;
        /**节点下一个元素*/
        Entry<K,V> next;
        ......
}

我们再接着来看看 Hashtable 初始化过程,核心源码如下:

public Hashtable() {
    this(11, 0.75f);
}

this 调用了自己的构造方法,核心源码如下:

public Hashtable(int initialCapacity, float loadFactor) {
        .....
        //默认的初始大小为 11
        //并且计算扩容的阈值
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

可以看到 HashTable 默认的初始大小为 11,如果在初始化给定容量大小,那么 HashTable 会直接使用你给定的大小;
扩容的阈值threshold等于initialCapacity * loadFactor,我们在来看看 HashTable 扩容,方法如下:

protected void rehash() {
        int oldCapacity = table.length;
        //将旧数组长度进行位运算,然后 +1
        //等同于每次扩容为原来的 2n+1
        int newCapacity = (oldCapacity << 1) + 1;
        
        //省略部分代码......
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
}

可以看到,HashTable 每次扩充为原来的 2n+1。
我们再来看看 HashMap,如果是执行默认构造方法,会在扩容那一步,进行初始化大小,核心源码如下:

final Node<K,V>[] resize() {
    int newCap = 0;

    //部分代码省略......
    newCap = DEFAULT_INITIAL_CAPACITY;//默认容量为 16
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}

可以看出 HashMap 的默认初始化大小为 16,我们再来看看,HashMap 扩容方法,核心源码如下:

final Node<K,V>[] resize() {
    //获取旧数组的长度
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int newCap = 0;

    //部分代码省略......
    //当进行扩容的时候,容量为 2 的倍数
    newCap = oldCap << 1;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}

可以看出 HashMap 的扩容后的数组数量为原来的 2 倍;
也就是说 HashTable 会尽量使用素数、奇数来做数组的容量,而 HashMap 则总是使用 2 的幂作为数组的容量。
我们知道当哈希表的大小为素数时,简单的取模哈希的结果会更加均匀,所以单从这一点上看,HashTable 的哈希表大小选择,似乎更高明些。
Hashtable 的 hash 算法,核心代码如下:

//直接计算key.hashCode()
int hash = key.hashCode();

//通过除法取余计算数组存放下标
// 0x7FFFFFFF 是最大的 int 型数的二进制表示
int index = (hash & 0x7FFFFFFF) % tab.length;

从源码部分可以看出,HashTable 的 key 不能为空,否则报空指针错误!
但另一方面我们又知道,在取模计算时,如果模数是 2 的幂,那么我们可以直接使用位运算来得到结果,效率要大大高于做除法。所以在 hash 计算数组下标的效率上,HashMap 却更胜一筹,但是这也会引入了哈希分布不均匀的问题, HashMap 为解决这问题,又对 hash 算法做了一些改动,具体我们来看看。
HashMap 的 hash 算法,核心代码如下:

/**获取hash值方法*/
static final int hash(Object key) {
     int h;
     // h = key.hashCode() 为第一步 取hashCode值(jdk1.7)
     // h ^ (h >>> 16)  为第二步 高位参与运算(jdk1.7)
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//jdk1.8
}

/**获取数组下标方法*/
static int indexFor(int h, int length) {
    //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

HashMap 由于使用了2的幂次方,所以在取模运算时不需要做除法,只需要位的与运算就可以了。但是由于引入的 hash 冲突加剧问题,HashMap 在调用了对象的 hashCode 方法之后,又做了一些高位运算,也就是第二步方法,来打散数据,让哈希的结果更加均匀。

与此同时,在 jdk1.8 中 HashMap 还引进来红黑树实现,当冲突链表长度大于 8 的时候,会将链表结构改变成红黑树结构,让查询变得更快,具体实现可以参见《集合系列》中的 HashMap 分析。

三、常用方法介绍

3.1、put方法

put 方法是将指定的 key, value 对添加到 map 里。

image.png

打开 HashTable 的 put 方法,源码如下:

public synchronized V put(K key, V value) {
        //当 value 值为空的时候,抛异常!
        if (value == null) {
            throw new NullPointerException();
        }

        Entry<?,?> tab[] = table;

        //通过key 计算存储下标
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        
        //循环遍历数组链表
        //如果有相同的key并且hash相同,进行覆盖处理
        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;
}

put 方法中的 addEntry 方法,源码如下:

private void addEntry(int hash, K key, V value, int index) {
        //新增修改次数
        modCount++;

        Entry<?,?> tab[] = table;
        if (count >= threshold) {
           //数组容量大于扩容阀值,进行扩容
            rehash();
            
            tab = table;
            //重新计算对象存储下标
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        //将对象存储在数组中
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
}

addEntry 方法中的 rehash 方法,源码如下:

protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        //每次扩容为原来的 2n+1
        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;
            }
        }
}

总结流程如下:

1、通过 key 计算对象存储在数组中的下标;
2、如果链表中有 key,直接进行新旧值覆盖处理;
3、如果链表中没有 key,判断是否需要扩容,如果需要扩容,先扩容,再插入数据;
有一个值得注意的地方是 put 方法加了synchronized关键字,所以,在同步操作的时候,是线程安全的。

3.2、get方法

get 方法根据指定的 key 值返回对应的 value。

get 流程图如下:

image

打开 HashTable 的 get 方法,源码如下:

public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        //通过key计算节点存储下标
        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;
}

同样,有一个值得注意的地方是 get 方法加了synchronized关键字,所以,在同步操作的时候,是线程安全的。

3.3、remove方法

remove 的作用是通过 key 删除对应的元素。

remove 流程图如下:

image

打开 HashTable 的 remove 方法,源码如下:

public synchronized V remove(Object key) {
        Entry<?,?> tab[] = table;
        //通过key计算节点存储下标
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        Entry<K,V> e = (Entry<K,V>)tab[index];
        //循环遍历链表,通过hash和key判断键是否存在
        //如果存在,直接将改节点设置为空,并从链表上移除
        for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
}

同样,有一个值得注意的地方是 remove 方法加了synchronized关键字,所以,在同步操作的时候,是线程安全的。

四、总结

总结一下 Hashtable 与 HashMap 的联系与区别,内容如下:

  • 1、虽然 HashMap 和 Hashtable 都实现了 Map 接口,但 Hashtable 继承于 Dictionary 类,而 HashMap 是继承于 AbstractMap;
  • 2、HashMap 可以允许存在一个为 null 的 key 和任意个为 null 的 value,但是 HashTable 中的 key 和 value 都不允许为 null;
  • 3、Hashtable 的方法是同步的,因为在方法上加了 synchronized 同步锁,而 HashMap 是非线程安全的;

尽管,Hashtable 虽然是线程安全的,但是我们一般不推荐使用它,因为有比它更高效、更好的选择 ConcurrentHashMap,在后面我们也会讲到它。

最后,引入来自 HashTable 的注释描述:

If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

简单来说就是,如果你不需要线程安全,那么使用 HashMap,如果需要线程安全,那么使用 ConcurrentHashMap。

HashTable 已经被淘汰了,不要在新的代码中再使用它。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,284评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,115评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,614评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,671评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,699评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,562评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,309评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,223评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,668评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,859评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,981评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,705评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,310评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,904评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,023评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,146评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,933评论 2 355

推荐阅读更多精彩内容