Hashtable和HashMap的区别以及如何实现线程安全

版本：
JDK8

一、结构分析

首先，我们对其各自结构分析。

1.Hashtable

其类在java.util包下，
查看其源码，其类的注解大致介绍了这个类，我们阅读后大概的意思就是：
这是一个线程安全的、实现了哈希表（键值对结构）的一个类。

简单通俗的可以用图来直观表现：


Hashtable结构图.png

没错，就是以数组+链表结构来实现集合操作。

接下来我们所要去研究的就是元素如何存储、如何取值、数据临界操作、使用范围以及注意事项，最终我们从中学习到其目的以及思想，提高我们的思维。

通过源码来分析一波：

  1. 基本私有变量和默认初始化
    /**
     * The hash table data.集合中存放数据的数组
     */
    private transient Entry<?,?>[] table;

    /**
     * The total number of entries in the hash table.当前数组中的元素个数
     */
    private transient int count;

  /**
     * The table is rehashed when its size exceeds this threshold.  (The
     * value of this field is (int)(capacity * loadFactor).)数组需要进行扩容的峰值
     *
     * @serial
     */
    private int threshold;

    /**
     * The load factor for the hashtable.加载因子，即数组实际能存储元素个数的百分比
     *
     * @serial
     */
    private float loadFactor;

    /**
     * The number of times this Hashtable has been structurally modified
     * Structural modifications are those that change the number of entries in
     * the Hashtable or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the Hashtable fail-fast.  (See ConcurrentModificationException).
     */
    private transient int modCount = 0;

    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).默认出初始化数组大小11，加载因子0.75
     */
    public Hashtable() {
        this(11, 0.75f);
    }
  1. put操作

//这里使用synchronized关键字来保证线程安全
 public synchronized V put(K key, V value) {
        //这里限定了HashTable中value不允许为null
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        //要存入的元素已经存在的情况下的操作
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        /**
         * 这里通过hash值和数组长度来确定元素存储的位置
         */
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        //这里判定是否是存在的key
        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;
    }

private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;
        //数组中的元素数量是否到达了临界值，是进行扩容操作
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        //这里使用到了一个链表操作，即同一个hash值的不同对象key的最新的元素永远在链表的最前端
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }
  1. get操作
 public synchronized V get(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) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }
  1. 扩容操作
protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code 扩容大小为 x2 + 1
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                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;
            }
        }
    }

源码基本分析完毕，我们总结出Hashtable的特性：

  • 数组+链表 结构
  • 通过synchronized关键字修饰在方法上保证线程安全

从中我们学到的一些方法：

  • 通过key的hashCode和数组的长度来确定元素位置，这样可以保证查询效率为O(1)
  • 在key的hashCode的值相同的时候，通过链地址法(其实就是链表结构数据)来解决所谓的哈希冲突

缺点：

  • 由于基本的查询、插入、修改方法都是使用synchronized关键字修饰来保证线程安全的，即对象锁，所以多线程下执行效率肯定低下。

2.HashMap

一、HashMap的结构及其原理

1.什么是HashMap

HashMap是基于哈希表的Map接口的非同步实现。是双列集合，一次储存键与值键与值一一对应（键是唯一性，值不唯一，同时键与值都可以是null）。

2.数据结构

Java中最基本的数据结构是数组和引用（指针），HashMap通过这两个数据结构实现。HashMap是一个==“链表散列”==的数据接口，即通过数组+链表结合实现。而从jdk1.8起，为了进一步提高效率，引入了红黑树，即数组+链表/红黑树。（当同一hash索引下的节点个数超过8个的话，就通过红黑树的形式存储起来，当然若数组大小小于64即为扩容）

HashMap结构图.png

为什么要采取这种结构呢？
这里我们简单的说一下，不做深究：
1.数组的查找通过索引查找是非常快的，时间复杂度o(1)。
2.链表呢，我们删除和增加效率是非常高的。
3.红黑树，将普通链表的查找速度由o(n)降低到了o(logn)

所以这几者相结合，将会达到很好的效果，具体如何结合的，我们通过下面的分析一步一步探究。

3.通过源码一步一步研究HashMap的存储元素过程

去看了源码，密密麻麻的好多代码啊，难道要一行一行的去研究吗？
不用，研究他们的核心部分即可，那从何处开始研究呢？
我们就通过我们使用HashMap的步骤去研究：

1.HashMap map = new HashMap();

附上这行代码的源码：

/**
     * 哈希表的加载因子
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;
/**  
     * 在构造函数未指定的时候，加载因子的默认值=0.75f
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 其他的属性都是默认值
    }

这里我们要记住的就是loadFactor（加载因子），那么这个加载因子有什么用呢？
这个加载因子是和数组的空间利用率有关，即一个数组的长度为length时，我们所能存储元素的长度只能是length*loadFactor。

2.public V put(K key, V value)，key代表键，value代表值
看这个方法的源代码：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
//继续解刨，看putVal(hash(key),key,value,false,true)
//首先我们看看hash(key)干嘛的
static final int hash(Object key) {
        int h;
        /*
            我们看到，当key为空的时候，会返回值0，不为空的时候，会将key的哈希值的高位（16位）与低位（16位）进行^（异或）计算，然后返回结果值，这个结果有什么用呢，是用来用于后面再次计算得出所在数组中的索引值
        */
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
//这个就是储存每个节点的具体步骤了
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        /*
            变量名解释：tab（数组） p（节点,数组中每个元素）
            n为数组的长度,i为数组的索引
        */
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果tab引用为空指针，或者数组长度为0,即返回一个新的数组，长度为n
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /*
            这里有个(n-1)&hash式子,计算的结果是数组的索引
            这里的逻辑是判断数组中这个索引的对应的值是否为null，若是
            为空的话，将将这个节点储存在这个索引的位置
        */
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {//执行这里，说明这个索引位置储存的不是链表就是红黑树了
            Node<K,V> e; K k;
            /*
            这里的逻辑是，这个索引位置已有节点了，那么就判断添加的的key
            和这里已有节点的key是否是同一个地址的或者是否是内容相同的，是的话，就将添加进来的value值替换掉原有节点的value值
            */
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断当前索引位置的对象是否属于红黑树，是的话，添加上去
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//执行这里说明这里不是红黑树，是链表
                /*
                    遍历循环链表
                */
                for (int binCount = 0; ; ++binCount) {
                    //此节点的下一个节点是否为空节点，是的话，直接赋值节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                            //判断此位置的链表个数是否超过了8个，超过
                            //将执行teeifyBin()方法(扩容或转为红黑树)，并结束并推出循环
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //节点不为空，判断哈希值和key是否是一样的，是的话结束并退出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;//遍历下一个节点
                }
            }
            //判断添加的节点是否为新节点，不是新节点，则将新的value值替换老的value值，并返回老的value值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //记录HashMap结构修改的个数(只有添加了新的节点)
        ++modCount;
        //添加元素后此时数组中元素个数>数组中规定的个数(数组长度*负载因子)时扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

这里我们通过源码分析了我们使用HashMap添加对象的一系列过程，这里我们画个图看看一比较形象的逻辑：


HashMap添加元素逻辑图.png

通过分析put(K key,V value)的源码，我们知道了HashMap内部结构:

  • 数组Node<K key,V value>:
    //节点，通过内部内实现
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//存放hash值（key的）
        final K key; //存放key值
        V value;  //存放value至
        Node<K,V> next; //存放下一个节点的地址

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
       ...
 }

上面就是链表的组成部分，一个一个节点组成的。而数组呢，就是存放每一个hash值相同的节点，从第一个开始存放，往后相同的hash值节点便通过链表的形式存放。

  • hash算法：
    hash算法是我们需要了解的部分，因为你存入的元素放在数组的那个位置是通过这个来计算的，即上面出现的计算公式：
    (n-1)&hash
    计算出索引位置的算法.png

具体计算过程如图所示。（这里需要注意的是，因为数组的长度始终是2的次方幂，这里的与运算，就相当于给length-1取模运算）

注意：通过这样的算法，我们其实可以知道，总会有一种情况，计算得出的值是相同的，所以需要解决哈希冲突，HashMap的解决办法就是一开始我们介绍的形式，数组+链表，即==链表法==。还有一种方法是==开放地址法==（即通过探测算法，当此位置被占用，即寻找下一个可用的位置）。

二.HashMap的哈希表散列运算

我们知道每一个对象都有它的哈希值，这是Object类中的本地方法，具体怎么计算的，目前我也不知道，只要知道这个对于每一个对象得出的值基本不可能即可。
因为通过%（取模运算）是要进行/（除法）运算的，效率低。（其实到底低多少我也不知道）
而通过&（与运算）是直接通过对二进制来计算的，效率高。
那么：
(n-1)&hash
n为什么要-1呢？
首先，我们要知道n是数组的长度，而HashMap的数组长度是==偶数，即长度为2的幂次方，每次扩容都是之前的一倍==。
然后我们知道偶数的二进制最低位是0，那好，偶数的&(与运算)我们可以很明确的得出，结果必然是偶数，所以，如果直接用偶数来进行哈希表散列将浪费一半的空间。
所以，我们将n-1得到奇数，而奇数进行与运算，得到的结果可能是可能是偶数，也可能是奇数，这样就不会浪费空间了！
所以，利用这个特性1&N(N为0/1)，结果可能为0，也可能为1，这就解释了为什么扩容要是2的幂次，因为2的幂次 -的二进制结果所有位都是1，这样结果可能性会增加。

3.总结

通过以上我们总结出两者区别：

  • Hashtable实现了线程安全，HashMap没有实现线程安全
  • Hashtabke是数组+链表结构，HashMap是数组+链表+红黑数结构
  • 不考虑线程安全情况下，HashMap效率要远远高于Hashtable
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,185评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,445评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,684评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,564评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,681评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,874评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,025评论 3赞 408
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,761评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,217评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,545评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,694评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,351评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,988评论 3赞 315
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,778评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,007评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,427评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,580评论 2赞 349