龙空技术网

详解HashMap的使用及其实现

程序汪布丁 84

前言:

如今兄弟们对“如何实现hashmap”大概比较珍视,各位老铁们都需要剖析一些“如何实现hashmap”的相关文章。那么小编也在网上搜集了一些关于“如何实现hashmap””的相关资讯,希望看官们能喜欢,你们快快来了解一下吧!

1.概述

HashMap可以说是在java中应用最频繁Map类型了。HashMap 是基于哈希表的 Map 接口的非同步实现====>这里可以说明,它不能保证映射的顺序,特别是它不能保证该顺序亘古不变,因为加入的元素是根据哈希值来存储的。HashMap允许存储null的key值和null的value值。

由于HashMap是基于哈希表来实现的,所以此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高或将加载因子设置得太低。

需要注意的是:HashMap 不是同步的,如果多个线程同时访问一个 HashMap,而其中至少一个线程从结构上(指添加或者删除一个或多个映射关系的任何操作)修改了,则必须保持外部同步,以防止对映射进行意外的非同步访问。

2.实现原理

HashMap中的存储方式是数组+链表+红黑树。其中数组的类型是Entry类型的数组,当我们往HashMap内填充元素时,首先会计算其key的hashcode来重新计算key的hash值,并找到数组中对应的下标,如果该位置目前并没有元素,则直接将该元素放入数组中;如果该位置目前已经有了元素,则把新的元素加入到链表中。当元素的长度超过阈值(JDK1.8中该值为8)时,链表则会转换为红黑树(转换为红黑树还需要满足其他的条件,链表长度达到阈值只是其中的一个条件),这样会大大提高我们查找的效率。

HashMap的存储结构图。当链表过长时(>=8),会转换成红黑树来存储,以便提高查找效率:

使用这种存储方式是为了解决哈希碰撞的问题,换言之,链表中的每个key,都具有相同的哈希值。最极端的情况就是,当所有的元素都具有相同的哈希值,那么HashMap会退化为一个链表,查找时间也从O(1)上升到O(N)。当N越来越大时,get(key)方法的开销也越来越大。因此,在JDK1.8里面加入了一个红黑树:当某个桶内的记录过大的话(>=8),HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好,是O(logn),而不是糟糕的O(n)。它是如何去工作的呢:

前面产生冲突的那些key对应的记录只是简单的追加到一个链表后面,这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树,使用哈希值作为树的分支变量,如果两个哈希值不等,但指向同一个桶的话,较大的那个会插入到右子树里。如果哈希值相等,HashMap希望key值最好是实现了Comparable接口的,这样它可以按照顺序来进行插入。

3.源码及分析

首先看一下HashMap的定义以及一些属性

public class HashMap<K,V> extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable {    private static final long serialVersionUID = 362498820763181265L;    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16    static final int MAXIMUM_CAPACITY = 1 << 30;    static final float DEFAULT_LOAD_FACTOR = 0.75f;    static final int TREEIFY_THRESHOLD = 8;    transient Node<K,V>[] table;    transient Set<Map.Entry<K,V>> entrySet;    transient int size;    transient int modCount;    int threshold;    final float loadFactor;

在这里我们可以看到,HashMap是继承于AbstractMap,并且实现了Map, Cloneable, Serializable接口。其默认的初始容量为16(DEFAULT_INITIAL_CAPACITY = 1 << 4),最大容量为2的30次幂(MAXIMUM_CAPACITY = 1 << 30),默认的加载因子为0.75(即当HashMap目前存储的元素超过其初始值加载因子,即160.75=12时,HashMap会进行扩容)。其他的我们可以看到TREEIFY_THRESHOLD = 8;表明当链表长度超过8时,会转化为红黑树。

HashMap中涉及的数据结构:

static class Node<K,V> implements Map.Entry<K,V> {      //以下4行即为一个Entry        final int hash;        final K key;        V 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;        }

HashMap的构造函数:

//构造函数1:指定初始容量和加载因子    public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        /*指定的初始容量如果大于最大容量,则默认以最大容量座作为初始容          *量,则2的30次幂          */           if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        //加载因子必须为正数        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        this.loadFactor = loadFactor;        //新的扩容阈值        this.threshold = tableSizeFor(initialCapacity);    }//构造函数2:指定初始容量    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }//构造函数3:无参数   /**     * Constructs an empty <tt>HashMap</tt> with the default initial capacity     * (16) and the default load factor (0.75).     *///可以通过注释看到默认的初始值和加载因子    public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted    }//构造函数4:    public HashMap(Map<? extends K, ? extends V> m) {        this.loadFactor = DEFAULT_LOAD_FACTOR;        putMapEntries(m, false);    }

我们可以看到,即便我们指定了初始容量,初始容量也未必就是我们指定的大小,因为HashMap的容量始终都是2的次幂,所以当我们传入一个指定的容量时,还会调用一个tableSizeFor(int cap)方法来计算容量的大小:

/**     * Returns a power of two size for the given target capacity.     */    static final int tableSizeFor(int cap) {        int n = cap - 1;        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    }

HashMap的存取:

1)首先来看存储:

public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }    /**     * Implements Map.put and related methods.     *     * @param hash hash for key     * @param key the key     * @param value the value to put     * @param onlyIfAbsent if true, don't change existing value     * @param evict if false, the table is in creation mode.     * @return previous value, or null if none     */    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node<K,V>[] tab; Node<K,V> p; int n, i;        //当当前数组为空时,先进行扩容        //可以看出,在我们第一次调用put方法往HashMap添加元素之和,HashMap的size才开始是初始容量        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        //当数组的当前位置为空时,直接创建一个新的节点并放进去        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        //当前位置非空,产生哈希冲突        else {            Node<K,V> e; K k;            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) {                    //当遍历到链表的尾端时,则把需要put的元素加进去                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        //判断冲突的节点数是否已经达到阈值8                        //如果达到8,则判断HashMap的size是否已经>=64,如果没有则只进行扩容                        //当HashMap的size >= 64并且冲突的节点数达到8时,用红黑树去存储产生冲突的节点                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            //如果有相同的key,则用新的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;            }        }        ++modCount;        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }

通过源码可以看到,put(key, value)的过程为:

①检查tab[]是否为空或null,如果是,则进行扩容

②根据键值计算其在数组中的下标i,如果tab[i] == null,则直接插入新建的节点

③若tab[i]已经有元素存储了,则判断当前处理节点的方式为链表还是红黑树,分别处理

在存储的时候,有一个细节需要注意一下:注意到p = tab[i = (n - 1) & hash],其中的数组下标是通过(n-1)&hash的方式来计算出来的,这里处理的非常巧妙:

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序得到的 hash 码值总是相同的。我们首先想到的就是把 hash 值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,而HashMap的底层数组的大小总是为2的n次幂,此时,h& (length-1)运算等价于对 length 取模,也就是 h%length。

举个例子说明:

我们可以看到,当数组长度为15时,8或9与其相遇,都会产生相同的结果,此时就会发生哈希冲突,8和9都会放到数组中的同一个位置,形成链表,这样会降低了查询的效率。同时,我们可以发现,当数组长度不为2的n次幂时,table.length-1永远会有0存在,而0无论是和1还是0相与,结果都为0。比如说,长度为15,那么15-1=14,其二进制为1110,此时,无论什么数与1110相与,末尾都为0,这时候,0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!而当数组的长度为2的n次幂时,table.length-1得到的二进制数的每个位上的值都为 1,这使得在低位上&时,得到的和原 hash 的低位相同,就使得只有相同的 hash 值的两个值才会被放到数组中的同一个位置上形成链表。所以说,当数组长度为 2 的 n 次幂的时候,不同的 key 算得得 index 相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了

2)HashMap的读取:

public V get(Object key) {        Node<K,V> e;        return (e = getNode(hash(key), key)) == null ? null : e.value;    }    /**     * Implements Map.get and related methods.     *     * @param hash hash for key     * @param key the key     * @return the node, or null if none     */    final Node<K,V> getNode(int hash, Object key) {        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;        //找到第一个插入的node        if ((tab = table) != null && (n = tab.length) > 0 &&            (first = tab[(n - 1) & hash]) != null) {            if (first.hash == hash && // always check first node                ((k = first.key) == key || (key != null && key.equals(k))))                return first;            //当first节点不是所查找的节点时            if ((e = first.next) != null) {                //判断是否当前是否用红黑树来存储                if (first instanceof TreeNode)                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);                //遍历链表                do {                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        return e;                } while ((e = e.next) != null);            }        }        return null;    }

在调用get(key)方法时,会先获取可以的hash值,并计算得到此key在数组中的位置:first = tab[(n - 1) & hash],如果first节点不是需要获取的key,则往下遍历,直到找到需要获取的键值,并返回对应的value即可。

HashMap的扩容机制

/**     * Initializes or doubles table size.  If null, allocates in     * accord with initial capacity target held in field threshold.     * Otherwise, because we are using power-of-two expansion, the     * elements from each bin must either stay at same index, or move     * with a power of two offset in the new table.     *     * @return the table     */    final Node<K,V>[] resize() {        Node<K,V>[] oldTab = table;        int oldCap = (oldTab == null) ? 0 : oldTab.length;        int oldThr = threshold;        int newCap, newThr = 0;        if (oldCap > 0) {            if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE;                return oldTab;            }            //旧表的长度不为0,则把新表的容量设置为旧表容量的两倍            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)                newThr = oldThr << 1; // double threshold        }        else if (oldThr > 0) // initial capacity was placed in threshold            newCap = oldThr;        //如果旧表的长度为0,则说明是第一次初始化        else {               // zero initial threshold signifies using defaults            newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }        if (newThr == 0) {            float ft = (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);        }        threshold = newThr;        @SuppressWarnings({"rawtypes","unchecked"})        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];        table = newTab;        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {                Node<K,V> e;                if ((e = oldTab[j]) != null) {                    oldTab[j] = null;                    //e.next为null说明此位置没有形成链表                    if (e.next == null)                        newTab[e.hash & (newCap - 1)] = e;  //重新计算该元素在新表中的位置并插入                    //判断是否为红黑树存储方式                    else if (e instanceof TreeNode)                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                    else { // preserve order                        Node<K,V> loHead = null, loTail = null;                        Node<K,V> hiHead = null, hiTail = null;                        Node<K,V> next;                        //遍历链表                        do {                            next = e.next;                            //将链表的节点拆分为两队,e.hash&oldCap结果为0的一队,结果为1的为另一队                            if ((e.hash & oldCap) == 0) {                                if (loTail == null)                                    loHead = e;                                else                                    loTail.next = e;                                loTail = e;                            }                            else {                                if (hiTail == null)                                    hiHead = e;                                else                                    hiTail.next = e;                                hiTail = e;                            }                        } while ((e = next) != null);                        if (loTail != null) {                            loTail.next = null;                            newTab[j] = loHead;                        }                        if (hiTail != null) {                            hiTail.next = null;                            newTab[j + oldCap] = hiHead;                        }                    }                }            }        }        return newTab;    }

当HashMap中的元素越来越多的时候,产生哈希冲突的几率也就越来越大,毕竟数组的长度是固定的。为了减小哈希冲突的几率,同时也是为了提高查询效率,我们需要对HashMap适当的进行扩容。而扩容也不是产生哈希冲突之后就开始执行,而是要满足一定条件之后才扩容:当HashMap中元素的个数已经达到阈值,则table.length * loadFactory,比如说采用无参数构造器去创建一个HashMap,那么table.length * loadFactory = 16 * 0.75 == 12,即当HashMap中的元素个数达到12时,HashMap才开始扩容。扩容之后的大小为之前的两倍。我们在源码中可以看到,扩容是一项很费时的操作,如果我们能够预知HashMap中元素的个数,那么在初始化时指定初始值以及加载因子来规避扩容,也是提高性能的一种方法。

Fail-Fast机制

原理

fail-fast 机制是 java 集合(Collection)中的一种错误机制。 当多个线程对同一个集合的内容进行操作时,就可能会产生 fail-fast 事件。

比如说,在线程A通过 iterator去访问集合时,如果有其他线程修改了该集合,那么A线程这里就会抛出 ConcurrentModificationException 异常,产生 fail-fast 事件。

我们知道,java.util.HashMap不是线程安全的,在多线程的环境中,如果A线程正在通过iterator去访问这个map,而其他线程则修改了该map,那么A线程就会抛出一个ConcurrentModificationException异常。

这个策略在源码中的实现则是通过modCount,每一次修改map中的内容,modCount的值都会增加,在迭代器开始的过程中,会把modCount的值赋给迭代器的 expectedModCount:

HashIterator() {            expectedModCount = modCount;            Node<K,V>[] t = table;            current = next = null;            index = 0;            if (t != null && size > 0) { // advance to first entry                do {} while (index < t.length && (next = t[index++]) == null);            }        }

在迭代过程中,判断 modCount 跟 expectedModCount 是否相等,如果不相等就表示已经有其他线程修改了 map:

final Node<K,V> nextNode() {            Node<K,V>[] t;            Node<K,V> e = next;            if (modCount != expectedModCount)                throw new ConcurrentModificationException();            ...        }

注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。

解决方案

fail-fast 机制,是一种错误检测机制。它只能被用来检测错误,因为 JDK 并不保证 fail-fast 机制一定会发生。若在多线程环境下使用 fail-fast 机制的集合,建议使用“java.util.concurrent 包下的类”去取代“java.util 包下的类”。

与Hashtable的比较

相同点:

①都是基于哈希表实现的,并且里面存储的元素都是key-value对

②当产生哈希冲突时,内部都会通过单链表去解决冲突问题(当然JDK1.8中HashMap中加入了红黑树)

③内部容量不足时,都会自动进行扩容

④都实现了Map、Cloneable、Serializable接口,可以被克隆,支持序列化

区别:

①继承的父类不同

HashMap继承的是AbstractMap,而Hashtable继承的是Dictionary

②线程安全性不同

我们知道,HashMap是线程不安全的,在源码中也可以看到,HashMap中的方法并没有添加synchronized去修饰,在多线程的环境下使用时,需要自己增加同步处理,建议使用Collections包下的synchronizedMap来把map包装起来,例如:

Map<String, String> map = Collections.synchronizedMap(new HashMap<>());

而Hashtable的方法用了synchronized去修饰,所以它是线程安全的。(即便如此,现在也不推荐使用Hashtable了,如果需要在多线程环境下使用时,通常采用上面的方法或者concurrent包下面的ConcurrentHashMap)

③提供的方法不同

Hashtable提供了contains,containsValue和containsKey三个方法,其中contains和containsValue功能相同;而HashMap中则去掉了contains方法,改用containsKey方法和containsValue方法,因为contains方法容易引起误解。

④key-value是否支持null值

在Hashtable中,key-value是不允许为null的,但是在使用put方法将一个null-null的键值对添加进Hashtable时,编译也会通过,只是在运行的时候会抛出一个NullPointerException异常;而在HashMap中,是允许null的key出现的,并且只允许出现一个(当然其他的key也只运允许出现一个),null的key会放在table[0]的位置。

⑤遍历方式

HashMap和Hashtable都使用了iterator迭代器进行遍历,不同的是,Hashtable还使用了Enumeration等方式

⑥数组初始化和扩容机制在默认情况下,Hashtable的初始容量为11,而HashMap为16,

Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。

Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。

标签: #如何实现hashmap