关于1.7和1.8的HashMap的总结

发表于 | 分类于

前言

工行的项目中，我们大量的使用了Map，但对于7和8的版本有哪些区别还比较模糊，特此来总结归纳一下，在日常的开发过程中，HashMap是我常用的数据结构体，在分析1.7和1.8的HashMap之间的区别之前，先了解一下HashMap。

简介

  • HashMap类

    1
    2
    public class HashMap<K,V> extends AbstractMap<K,V> 
             implements Map<K,V>, Cloneable, Serializable

  • 类介绍
    定义：基于哈希表的Map接口的实现类，继承了AbstractMap抽象类，同时实现了Map（基于Map），Cloneable（可克隆）,Serializable（序列化）接口。
    特点：允许空值空键，非安全线程，不保证有序。

    HashMap的实现

    简单来说，HashMap是基于数组+链表的形式来实现的。HashMap的初始容量是16，扩容因子是0.75。意思是当put到13个键值对的时候（13 > 16 * 0.75），HashMap会进行扩容,从16扩容到32。
    数组的元素就是键值对（一个链表），数组的下标就是Key的hash值，数组的大小就是HashMap的容量。由于不同的Key计算的hash值可能会相同（hash冲突），链表就是用于解决这种冲突的。即发生冲突时，新元素插入到链表头中，新元素总是添加到数组里，旧元素移到单列表中。
    假设自己设计一个类似HashMap的类，可以采用数组+Entry的形式实现，Entry对象用来存放Key和Value。其插入和查询的都是O(n)级别的。

示意图

HashMap示意图

API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
V get(Object key); // 获得指定键的值
V put(K key, V value);  // 添加键值对
void putAll(Map<? extends K, ? extends V> m);  // 将指定Map中的键值对 复制到 此Map中
V remove(Object key);  // 删除该键值对

boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value);  // 判断是否存在该值的键值对；是 则返回true

Set<K> keySet();  // 单独抽取key序列，将所有key生成一个Set
Collection<V> values();  // 单独value序列，将所有value生成一个Collection

void clear(); // 清除哈希表中的所有键值对
int size();  // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空

1.7与1.8HashMap的区别

以上的分析主要是针对1.7的分析，其与1.8版本中最大的区别是加入了红黑树。即：数组+链表+红黑树。
在实现过程中将原先1.7的Entry换成了Node。当链表长度小于等于8时，两个版本无异，都是链表存放。当链表长度大于8时，就会将链表改成红黑树。
由于链表过长的话会导致索引变慢，而红黑树具有快速增删改查的优点，因此长度大于8时采用数组+红黑树的形式实现。
有关于红黑树的介绍。
当我们put一个键值对的时候：
put<k,v>

问题探究

当 key ==null时，该键值对存放什么位置？

当 key ==null时，将该 key-value 的存储位置规定为数组table 中的第1个位置，即table [0]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 /**
     * 函数使用原型
     */
      if (key == null)
           return putForNullKey(value);

   /**
     * 源码分析：putForNullKey(value)
     */
      private V putForNullKey(V value) {  
        // 遍历以table[0]为首的链表，寻找是否存在key==null 对应的键值对
        // 1. 若有：则用新value 替换 旧value；同时返回旧的value值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
          if (e.key == null) {   
            V oldValue = e.value;  
            e.value = value;  
            e.recordAccess(this);  
            return oldValue;  
        }  
    }  
    modCount++;  

    // 2 .若无key==null的键，那么调用addEntry（），将空键 & 对应的值封装到Entry中，并放到table[0]中
    addEntry(0, null, value, 0); 
    // 注：
    // a. addEntry（）的第1个参数 = hash值 = 传入0
    // b. 即 说明：当key = null时，也有hash值 = 0，所以HashMap的key 可为null
    // c. 对比HashTable，由于HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
    // d. 此处只需知道是将 key-value 添加到HashMap中即可，关于addEntry（）的源码分析将等到下面再详细说明，
    return null;  

}

equals 和 == 的区别，hashCode 与它们之间的联系？

equals是针对于内容，==是针对于地址或者基本数据类型的值。在Object中，equals就是==，即是否指向同一对象。
equals于hashCode的联系是：
原则 1 ： 如果 x.equals(y) 返回 “true”，那么 x 和 y 的 hashCode() 必须相等 ；
原则 2 ： 如果 x.equals(y) 返回 “false”，那么 x 和 y 的 hashCode() 有可能相等，也有可能不等 ；
原则 3 ： 如果 x 和 y 的 hashCode() 不相等，那么 x.equals(y) 一定返回 “false” ；

HashMap是如何判别一个键值对是否已经添加？

当我们put一个键值对的时候，首先根据键key计算hash值得到插入的数组索引i，根据i获取i位置的元素是否为空。如果为空，则直接添加（遍历插入），如果不为空，则直接覆盖。

HashMap 的长度为什么是 2 的幂次？

多线程同时往 HashMap 中 put 数据会发生什么？