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

2020-06-17  本文已影响0人  黎繁介

版本:
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的特性:

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

缺点:

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内部结构:

    //节点,通过内部内实现
    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值节点便通过链表的形式存放。

具体计算过程如图所示。(这里需要注意的是,因为数组的长度始终是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.总结

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

上一篇下一篇

猜你喜欢

热点阅读