java8之Hashmap

发表于 | 分类于
字数统计: 2,385 | 阅读时长 ≈ 9

Java8-HashMap变化

数据的存储结构从：数组+链表 演变为了 数组+链表+红黑树

Map 家庭族谱

Map

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

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

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

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

总结

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

HashMap简介

Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

我们知道HashMap的数据存储结构就是：数组加上链表。通过对于key的值做hash运算，获得对应的值找到对应的数组下标，然后再存储值。存储值的过程中可能当前数组已经存在值（这个称之为冲突） 然后再生成一个链表存储冲突的值。

HashCode() 和 Hash() 方法实现得足够好，能够尽可能地减少冲突的产生，那么对 HashMap 的操作几乎等价于对数组的随机访问操作，具有很好的性能。但是，如果 HashCode() 或者 Hash() 方法实现较差，在大量冲突产生的情况下，HashMap 事实上就退化为几个链表，对 HashMap 的操作等价于遍历链表，此时性能很差。

解决冲突的方法：开放地址法和链地址法

HashMap特点

  • 允许null为key

  • 输出无序

    如果想要输出有序，那以使用继承他的LinkedHashMap，元素输出顺序跟输入顺序一致,他提供了一个节点保存输入的元素的顺序。
    想要对元素的值进行排序 推荐TreeMap（因为他继承了SortedMap)

  • 非线程安全

  • 数组+链表存储方式
    hashMap内存结构图

Java8特性

HashMap是数组+链表+红黑树

hashMap内存结构图

存储算法：

map.put("kingge","shuai")
系统将调用kingge”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

高位运算和取模运算

好的hash算法和扩容机制是解决冲突和高效存取的命题

HashMap 重要的几个属性

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;

Node[] table(Hash桶)始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

分析HashMap的put方法

put方法图解，详情可以去看源码

hashMapput方法执行流程图

public V put(K key, V value) {
      // 对key的hashCode()做hash
      return putVal(hash(key), key, value, false, true);
  }
 
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
      Node<K,V>[] tab; Node<K,V> p; int n, i;
      // 步骤①：tab为空则创建
     if ((tab = table) == null || (n = tab.length) == 0)
         n = (tab = resize()).length;
     // 步骤②：计算index，并对null做处理 
     if ((p = tab[i = (n - 1) & hash]) == null) 
         tab[i] = newNode(hash, key, value, null);
     else {
         Node<K,V> e; K k;
         // 步骤③：节点key存在，直接覆盖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转换为红黑树进行处理
                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                         treeifyBin(tab, hash);
                     break;
                 }
                    // key已经存在直接覆盖value
                 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;
 }

为什么说HashMap是线程不安全的

个人觉得有两个表现，如果还有其他的希望大家补充，或者以后等楼主源码研究透了再补充

表现一

我们知道当插入数据超过了threshold(threshold=length * Load factor),那么就会扩容，扩容会去调用resize和transfer方法，这个时候原先hash桶里面的所有数据都会重新计算，对应的位置–称之为rehash，这个成本很大

最根本的原因是出现时死循环-也就是在死锁问题出现在了transfer方法上面,而且是因为在扩容转换的过程中采用的是链表的头插法的形式
进行插入数据。例如原来在数组arr[0]的位置又链表1–>2–>3 那么扩容后，采用头插法就变成了arr[0]：3–>2–>1

为什么采用头插法，因为时间复杂度为O(1)，想象一下尾插法，那么需要遍历找到最尾元素然后插入时间复杂度是O(n)

具体源码分析参见：http://www.importnew.com/22011.html

表现二

多个线程同时操作一个hashmap就可能出现不安全的情况：
比如A B两个线程(A线程获数据 B线程存数据) 同时操作myHashMap
1.B线程执行存放数据
modelHashMap.put(“1”,”2”);
2.A线程执行get获取数据
modelHashMap.get(“1”)
A线程获取的值本来应该是2，但是如果A线程在刚到达获取的动作还没执行的时候，
线程执行的机会又跳到线程B，此时线程B又对modelHashMap赋值 如：modelHashMap.put(“1”,”3”);
然后线程虚拟机又执行线程A，A取到的值为3，这样map中第一个存放的值 就会丢失。。。。。
—原子性

解决HashMap非线程安全

其实上面我已经有提过了：

三个方法：

  • Hashtable替换HashMap

  • Collections.synchronizedMap将HashMap包装起来

private Map map = Collections.synchronizedMap(new HashMap());
替换
private HashMap map = new HashMap();

  • ConcurrentHashMap替换HashMap

private ConcurrentHashMap map = new ConcurrentHashMap();
替换
private HashMap map = new HashMap();

好的博文

http://blog.csdn.net/lyg468088/article/details/49464121

如果你感觉文章对你又些许感悟，你可以支持我！！
-------------本文结束感谢您的阅读-------------
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微薄 豆瓣 一键分享 更多