阅读 2317

深入理解HashMap(一)

HashMap主要用来做什么?为什么要这么做?

hashmap我们都用过很多次了,主要目的就是为了加快我们的查找速度。我们学过数据结构的都知道,数组的查询和修改速度很快,但是增加一个元素或者删除一个元素就很慢,但是链表就反过来,链表是增加和删除一个元素很快,查询和修改就很慢。 通常来说,我们为了提高查询的速度,那么在插入元素的时候就要定义各种规则,就是增加复杂度了。 有不理解的可以 查询相关算法书里 查找这一章。而我们的hashmap正是将数组和链表结合起来增加查询速度的一种数据结构,对应的,我们 就要好好理解hashmap的put操作。

#图解hashmap的数据结构

前面我们说过hashmap是数组和链表结合起来的一种结构。

那么看这张图,数组的每一个元素实际上就是一个链表。我们都知道hashmap在使用的时候是key-value的键值对查找。 那么在最理想的时候 应该是数组的每一个元素,也就是对应的链表只有一个节点。这样的效率就是最快的。 因为这样几乎就相当于在数组里查找一个元素了。

但是如果脸不好,或者hash算法写的一般。就会出现 这个数组其他元素都是空,然后我们插入的数据全部在一个位置上对应的链表里:

这样查找起来就很慢了。前者o(1) 后者o(n)

看图也可以了解到,我们的hashmap是允许key为null的,但是最多也只能有一个元素的key为null,虽然允许key为null, 但是我们并不鼓励这么做。

理解负载因子

   /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
复制代码

这是一段我电脑上jdk8的hashmap的源码,注意这里我们可以知道,默认我们构造一个hashmap的时候默认大小是16个元素的数组。

那么这个DEFAULT_LOAD_FACTOR是干啥的呢?

我们都知道如果我们的hashmap的数组大小如果只有16个的话,当我们的数据也刚好是16的时候,最好的情况就是 一个元素 对应的链表只有2个结点。如果要插入32个数据的话,最好的结果 一个链表有2个节点。如果要插入128个数据的话,一个链表 就有8个节点了。查找起来速度肯定会降低。 为了提高我们的查找速度,我们显然应该扩充数组的大小, 那么何时扩充数组大小?就是当元素个数 大于 数组长度*负载因子 的时候,我们就要扩充数组大小为原来的一倍了。 比方说: 1.初始默认数组长度为16 2.当插入的元素已经到了12个以上的时候,我们就要扩充数组长度到32了。

为啥这个负载因子的值是0.75,我也不知道。。。。反正你知道有这么个东西即可。0.75应该是最好的算法把。

扩充数组长度的意义和目的?

前面我们说到,扩充数组长度以后可以增加查找数据的速度。可能有人理解的不够透彻,这里我们举一个简单的例子帮助大家理解。

  1. 假设我们的数组长度只有2. 并且要插入5,7,9 这3个元素。 hash算法我们选择 元素值和数组长度取模。

  2. 那么显然, 579和2 取模以后,值都为1,那么 5,7,9 这3个元素 都会插入在这个长度为2的数组的位置1上。

  3. 那么我们要查到579这3个元素,显然就比较慢了,因为都要去a[1]这个位置对应的链表上去找。所以我们开始增加数组长度

  4. 扩充数组长度为4. 那么579对4 取模以后,分别的值就为 1,3,1, 显然 5和9就被放到了a[1]这个位置上。7被放到了 a[3] 这个位置上。

  5. 再扩充一次长度,那么数组长度就是8,579对8取模以后,分别对应的值就是5,7,1 显然的5,7,9这3个元素对应的位置 就 是 a[5],a[7],a[1],此时我们的查找效率和只有长度为2时候的数组对比 效率明显提高。

上述的这过程,我们称之为rehash

理解jdk7 中的hashmap的源码

前文说过,对于hashmap来说,put操作是最重要的。我们就来看看jdk7种的put操作

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        //如果数组为空 先构造一个数组
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //如果key为null的情况要特殊处理
        if (key == null)
            return putForNullKey(value);
        //通过传进来的key的值 我们计算出一个hash的值    
        int hash = hash(key);
        //用hash的值和数组长度一起计算出 这个key-value应该放入数组的位置,也就是数组中的索引值
        int i = indexFor(hash, table.length);
        //看看数组这个索引位置下的链表有没有key和传进来的key是相等的,如果有那么就替换掉,并且把老的值返回
        //发生这种情况时,因为return了 所以函数到这里就结束掉了
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //如果没发生上述情况 就意味着一个新的元素被增加进来
        addEntry(hash, key, value, i);
        return null;
    }
    
    
     /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        //h是计算出来的hash值,length是数组长度 实际上这里就是取模操作。
        //和我们前文中的例子是一样的,就等于 h%length.这种写法效率更高而已
        return h & (length-1);
    }
    
    
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //这里也好理解哈,如果发生了要扩充数组长度的情况,那么hash值要重新计算
        //重新计算的hash值 也要再利用一次重新计算出再数组中的索引位置
        //threshold其实就是前文我们提到的 数组长度*负载因子
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        
        createEntry(hash, key, value, bucketIndex);
    }

    //这里我们重点看一下这个resize的操作
     void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        
        //构造出一个新的数组 容量当然翻倍啦
        Entry[] newTable = new Entry[newCapacity];
        //然后把老的数组的值放到新的数组里面
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        //然后把新的数组的索引赋值
        table = newTable;
        //最后重新计算这个阀值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    
    //接着看我们的transfer函数 实际上jdk7和8 关于hashmap最大的不同就在这里了
      void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //就跟前文中的例子一样,构建新数组的时候,老数组中的哪些元素在新数组中的索引我们都要重新计算一遍
                //仅此而已
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
    
    //这个也比较简单,实际上插入元素的时候,我们都是把新来的元素 放入链表的头部,然后让新来的元素的next指针指向
    //来之前的链表的头部元素,所以jdk7的插入元素是在链表头部插入。
    //在这个地方我们也可以再想明白一个问题,在transfer函数中,我们重新计算索引的时候,先去老的链表里从链表头部
    //取一个元素出来放入到新数组的索引里,取完第一个再取第二个
    //那么后面的元素也是后计算出索引放入到新的数组对应的链表里。既然是后放入,那么肯定后放入的会在链表的头部了
    //这就代表一个结果:因为我们每次插入元素是在链表头部插,所以如果新的数组构造出来以后,我们的索引计算出来
    //仍旧相等的话,这2个元素仍旧会放到一个索引对应的链表中,只不过之前在头部的,现在去了尾部。
    //也就是说在transfer的过程中,链表的顺序被倒置
     void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }


复制代码

jdk8与jdk7的不同

主要有两点。

1.hash冲突,也就是如果计算出来hash值相同的时候,我们不是放到一个链表里面吗?jdk7是在头部插入新的元素, jdk8是在尾部插入新来的元素。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        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;
            //如果hash相等key也相等 那么先拿着引用 等会直接替换掉老值 
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)//这边是红黑树的逻辑,jdk8在链表长度超过8的时候会转红黑树,这属于数据结构
            //的范畴 我们日后再说。
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //这边应该明显的看出来,新来的元素在链表的位置是在尾部的,而不是jdk7种的头部
                        p.next = newNode(hash, key, value, null);
                        //转红黑树的操作 如果链表长度大于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;
                }
            }
            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;
    }

复制代码
  1. 第二点也就是最大的不同,jdk8的resize()操作比jdk7快了很多,并且jdk7 resize链表会倒过来,而jdk8不会。

    考虑如下场景:

    初始长度为16的数组,我们加入2个元素 一个hashcode是5 一个hashcode是21. 我们对16取余之后, 计算出来的索引位置 5 对应的是a[5],21对应的是也是a[5] 于是这2个就存在同一个链表中。

    当元素越来越多终于超过阈值的时候,数组扩充到32这个长度,这个时候5 和21 再对32取余 5对应的还是a[5],而21对应的就是a[21] 这个位置了,我们注意 21这个hashcode,之前对应的位置 是在a[5] 扩充一倍以后在21 位置增加了16 ,这个16 实际上就是扩充的长度,这个数学公式可以抽象为

    扩充前位置 oldIndex 扩充后位置 要么保持不变 要么是oldIndex+扩充前的长度.

    有了这套数学规律,我们在resize的时候就可以优化一下了,不需要像jdk7中重新计算hash和index了。

    下面就是jdk8种resize的主要过程

if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = 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
                        //这个链表用来表示扩充以后 新增bit为0的链表 也就是说这个链表上的元素扩充前后位置不变
                        Node<K,V> loHead = null, loTail = null;
                        //这个用来表示扩充以后要挪动位置的链表 挪动位置也就是说新增的bit为1了。
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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;
                        }
                    }
                }
            }
        }
复制代码

多线程中的hashmap

众所周知的hashmap明显是不支持线程同步的,最大的原因就是hashmap的resize过程中极易被线程干扰, 很有可能中间的resize操作 transfer操作 的执行顺序被打乱,要知道transfer操作的是链表, 很容易出现 你指向我我指向你这种循环链表,一旦出现循环链表的情况,基本程序就是死循环要报错了。

何况即使不出现这种极端情况,put操作不加锁的话,随意的修改值,也会导致get出来的和你put进去的并不一致。

我们的hashtable就是采用的比较极端的方法,直接对put方法进行加锁了。这样虽然一劳永逸,但是效率极低。 不推荐使用。

当然我们还可以换一种方法。

HashMap hm=new HashMap();
Collections.synchronizedMap(hm);
复制代码

这样也可以保持线程同步。看看原理:

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
        return new SynchronizedMap<>(m);
    }

    /**
     * @serial include
     */
    private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            mutex = this;
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }

        public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        }
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }

        public V put(K key, V value) {
            synchronized (mutex) {return m.put(key, value);}
        }
        public V remove(Object key) {
            synchronized (mutex) {return m.remove(key);}
        }
        public void putAll(Map<? extends K, ? extends V> map) {
            synchronized (mutex) {m.putAll(map);}
        }
        public void clear() {
            synchronized (mutex) {m.clear();}
        }

        private transient Set<K> keySet;
        private transient Set<Map.Entry<K,V>> entrySet;
        private transient Collection<V> values;

复制代码

比hashtable好一点,但是锁加的还是太多了。有提升但是依旧不够好。

ConcurrentHashMap 才是解决此类问题的最终方案。

简单来说,ConcurrentHashMap比上述方案效率都要更高的原因主要就是

我们可以把hashmap当做银行的集合,比如说 这个集合里面 有工商银行,有建设银行,招商银行,农业银行,等等。

前面2者几乎就是 只要你来存钱,不管你是想去哪个银行存,你都得排队。

而ConcurrentHashMap的粒度会降低到,只要你来存钱,只会在你想去的银行门口排队。效率明显更高。

要真正理解ConcurrentHashMap的源码,我们需要对volatile transient 关键字有很深的了解,同时还要了解ReentrantLock这个锁机制,这里先卖个关子,ConcurrentHashMap我们日后再说,大家了解一下即可。

使用时的经验总结

(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。

(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

关注下面的标签,发现更多相似文章
评论