中北软院创新实验室源码解析

HashMap了解一下

2018-05-10  本文已影响4人  HikariCP

前言

本文基于jdk1.8

HashMap

先来看一下Java官方描述

HashMap类继承图

image

HashMap属性

静态属性：

成员属性：

image

HashMap简单总结：

HashMap构造函数

HashMap的构造函数共4个。

image

HashMap(int initialCapacity, float loadFactor)

我们可以看到loadFactor参数Java官方还对其进行了Float.NaN(0.0f/0.0f)的判断。可以说考虑的非常周到了

同时在构造函数的最后一行，在为threshold赋值的时候，调用了tableSizeFor()函数来对输入的初始容量进行判断，来保证该初始容量是2的整数次幂。

image

函数具体释义可参考：HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）

首先我们先来了解一下threshold这个属性：

image

threshold这个成员变量是阈值，决定了是否要将散列表扩容充重散列。它的值应该是：(capacity * loadfactor）才对的。

其实这里仅仅是一个初始化，当创建哈希表的时候，它会在resize函数中根据一些条件判断来重新定义赋值的。

HashMap(Map<? extends K, ? extends V> m)

image

这个构造函数其实本质上和刚才我们所看的给初始容量和负载因子的构造函数一致。函数最终做的除了参数上可以看出来的，把一个Map实例中的元素都插入到HashMap实例中外，由于负载因子没有显示指定所以赋予了loadFactory默认值。

并且把具体的Map迭代放在了调用的putMapEntries函数中。从该函数注释中看出，该函数是服务于putAll函数和constructor构造函数的。

从putMapEntries函数注释中也可以看出，如果这个函数在初始化Map时被调用evict参数传入的是false。而如果这个函数是在afterNodeInsertion函数后调用的，那么则需要传入的是true。

从putMapEntries函数的具体代码实现上可以看出，其在Map第一次初始化的时候和我们刚才所看的构造函数一致，都是在真正构造HashMap前先为阈值赋予一个可靠地初值。然后才迭代入参map集合，将其元素都插入到HashMap中。

其余的构造函数都是大同小异。就不一一赘述了

总结：

从构造函数中我们可以看出，HashMap的构造函数其实工作就只有一个。赋值

HashMap常见Api解析

put(K key, V value)

 /**
 * 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.
 *
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

可以看出put函数具体实现其实是调用了putVal函数。并且从注释中可以得知如果该映射存在，新值会替换掉旧值。

还可以看到的是传入了5个参数，我们来了解简单一下这5个参数。

 /**
 * 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) {

注释很直白解释的很清楚，按序号来

  1. key的哈希值
  2. key
  3. value
  4. 如果映射存在不替换原值？
  5. 如果是false，代表当前HashMap正处于创建阶段。

我们大概知道了这5个参数是干嘛的了，就可以针对第一个参数具体的去了解一下key的哈希值是如何计算得了。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里就比较疑惑了，为什么不直接用key类型对应的hashcode函数直接得到对应的哈希码呢？从这段代码可以看出来Java官方拿key的哈希码和其哈希码向右移位16位的结果进行异或操作。我们知道右移高位补0，由于哈希码返回的是一个4字节32位int类型的值。所以总共可以看成是高16位，低16位组成的。

而这里对其哈希码进行右移16位之后高位空缺补0，原高位到了现低位。然后再拿原哈希码与现哈希码进行异或操作，而我们知道任何数跟0异或都是其本身。所以可以看出Java官方最终目的，是想让哈希码原低16位与其高16位进行异或操作。而原高16位却不变，原来如此~

image

但为什么要这样呢？

其实这个与HashMap中元素插入时对应位置table数组下标的计算有关。

image

核心代码：

n = (tab = resize()).length;
i =（n-1） & hash

我们暂且不看resize函数，putVal函数在初次进来的时候该resize函数做的其实就是哈希表初始化的工作。由于DEFAULT_INITIAL_CAPACITY变量的存在，我们暂且认为该哈希表的大小length为16。即n=16

那么在计算元素插入位置的时候，由于底层是数组。所以真正存储的位置就是[0-15]。所以n-1。

而因为，table的length属性都是2的幂，因此i仅与hash值的低n位有关（此n非table.length，而是2的幂指数）
假设table.length=2^4=16。

image

由上图可以看到，32位的hash值只有低4位参与了运算。
仅有4位的异或很容易产生碰撞。但是由于table.length的大小只能由插入数据的多少来改变，而hash值得高16位又由于与操作置0了，所以设计人员相出一个好办法就是通过对key的hash值进行高16位与低16位异或来将高位与低位整合。这样不但可以保留原来key哈希值的差异性(高位地位同时作用)，同时来增加低16位2进制数值在计算时的差异性进而减少这种哈希冲突的情况。

参考：HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

接下来便可以继续分析真正的put函数了。

总结下来就是：

这样我们的putVal函数其实思路就理清了，看上去很复杂，其实宗旨没变，也就是判断，扩容，找位置，去除特殊情况，元素插入，只不过数据结构的差异性导致其特殊情况较多，判断的复杂了些。接下来该分析resize函数了。我们可以明显的看到putVal函数多出调用了resize函数。所以要想彻底理清HashMap实例是如何构建的，resize函数必然需要了解一下。

目前对resize的了解：table==null时，调用resize初始化table。元素数量>=threshold时，调用resize扩容。

Node<K,V>[] resize()

/**
 * 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
 */
final Node<K,V>[] resize() {
}

从该函数的开头我们也可以确认我们刚才的观点。用来初始化和给table扩容的。

总结下来就是：

哈细表扩容：

数据迁移：

get(Object key)

从注释中可以看出，返回 null 值并不一定 表明该映射不包含该键的映射关系；也可能该映射将该键显示地映射为 null。可使用 containsKey 操作来区分这两种情况。

 /**
 * ·····
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 * ·····
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

函数具体查询逻辑封装到了getNode函数。


简单来说：

remove(Object key)

/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @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 remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

从函数的注释中可以看出，该函数删除key对应的Entry并返回与 key 关联的旧值；如果 key 没有任何映射关系，则返回 null。但需要注意的是： 返回 null 还可能表示该映射之前将 null 与 key 关联。

函数再次把元素的通过hash函数包装传了进去，这很好理解，因为底层是哈希表嘛，不这样怎么能找到key到底在哈希表什么位置呢。我们可以看到删除逻辑的具体逻辑封装到了removeNode函数中。

removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)

先来对removeNod函数的多个参数进行一番分析。

 * @param hash hash for key 
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
  1. hash(key)
  2. key
  3. 对应matchValue参数，如果matchValue为true。那么删除key时其value必须与value相等，否则跳过这次删除
  4. 如果true。只有当值相等时才删除。
  5. 如果为false，那么在删除节点时不移动其他节点。

总的来说：

HashMap与HashTable对比

我们从一开始就曾说，两者从存储结构和实现来讲基本上都是相同的。两者最大的差别就是HashTable是线程安全的，而HashMap是线程不安全的。并且在数据存储时，HashMap允许key和value为null。而HashTable则不允许。并且HashTable规定用作键的对象必须实现 hashCode 方法和 equals 方法。

HashTable在Map映射中的地位有点儿像Vector在List集合中的定位。也是比较过时的类，设计上有一些缺陷，不需要线程安全的情况下可以使用HashMap替代它，而需要线程安全的情况下也可以用ConcurrentHashMap来替代它。

总结

上一篇下一篇

猜你喜欢

热点阅读