HashMap与LinkedHashMap——java技术栈系列文章

IT黑名单 2017-3-1 16:22:04

目录

HashMap

数据结构:数组+链表
不支持线程同步

 如上,一个元素进来时,会根据hashCode值计算hash值,hash值得到元素存放到数组的位置,如果hash相同会放在同一下标的数组元素中(以链表的形式存储)。也就是说如果abc三个hash相同的元素依次存进来,计算的下标为x,那么存入顺序为:1、a存进下标为x的元素entryA;2、b存进下标为x的元素entryB,entryB.next指向entryA;3、c存进下标为x的元素entryC,entryC.next指向entryB

hashMap存取伪代码:
int hash = key.hashCode();
int index = hash % Node[].length;
Entry[i] = value;

       如果很多元素hashCode值相同,单纯按hashCode计算存储位置将导致很多元素存储在同一个下标,造成链表过长。这样在查询时只通过hashCode并不能拿到value,还需要遍历一次链表,查询速度就慢了。为了让元素均匀的散列在数组中,这里计算hash的方法是hashCode对数组长度取模,在实现时为了运算的高效使用hash&(Node[].length -1),两者的结果是相同的。


hashMap resize
      因为数组的长度是固定的,当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高。为了提高查询效率,这时候需要对hash表扩容,也就是增加hashMap数组长度。数组长度扩容后,原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。resize是非常耗费性能的

      resize是非常耗费性能的,那么频繁的resize肯定不是期望的,那么HashMap什么时候进行扩容呢?当HashMap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值,可以自行修改。数组默认大小为16,也就是说默认情况下,当HashMap中元素个数超过16*0.75=12时即会进行扩容。每次扩容数组长度扩大一倍,也就是默认情况下数组长度为2的N次幂,感兴趣的可以搜下为什么数组长度设置为2的次幂,跟均匀散列有关。
      在resize时要注意两个参数:标识HashMap最大容量即数组最大长度的参数initialCapacity和负载因子loadFactor。负载因子是衡量空间使用程度,越大表示空间利用程度越高,对应的查询时间越长,如果负载因子过小会造成大量空间浪费。

LinkedHashMap

继承自HashMap并重新定义了数组中保存的元素Entry,该Entry除了保存当前对象还保存了其上下一个元素的引用,从而在哈希表基础上又构成了双向链表,支持按访问顺序或插入顺序访问。
LinkedHashMap extends HashMap implements Map {
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
}

LinkedHashMap在存值时调用父类HashMap的方法,但是重写了put的子方法afterNodeAccess、afterNodeInsertion,删除时重写了afterNodeRemoval方法。
HashMap.java

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap重写了父类的get方法,如果排序方式为按访问排序,则将访问的元素置于链表头,并从原位置删除,该操作基于链表,操作是常量级别,不会带来性能损耗。
LinkedHashMap.java
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null) //调用父类方法
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}



转载请注明来源【IT黑名单

本文链接:http://blog.itblacklist.cn/20170301/8444.html

© Copyright 2016 IT黑名单 Inc.All Rights Reserved. 豫ICP备15018592号-2