Java基础之Collections框架Map接口实现类HashMap及其源码分析（1）

HashMap是基于哈希表的Map接口的实现。 此实现提供所有可选的映射操作，并允许空值和空键。 （HashMap类与HashTable大致等效，不同之处在于它是不同步的，并且允许为null）。此类不保证映射的顺序。它不能保证顺序会随着时间的推移保持恒定。
假设哈希函数将元素正确分散在存储桶中，则此实现为基本操作（获取get和放置put）提供恒定时间的性能。 集合视图上的迭代所需的时间与HashMap实例的“容量”（存储桶数the number of buckets）及其大小（键-值映射数the number of key-value mappings）成正比。 因此，如果迭代性能很重要，则不要将初始容量设置得过高（或负载因子过低），这一点非常重要。
HashMap的实例具有两个影响其性能的参数：初始容量和负载因子。 容量是哈希表中存储桶的数量，初始容量只是创建哈希表时的容量。 负载因子是在自动增加其散列表容量之前允许散列表获得的满度的度量。 当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表将被重新哈希（即，内部数据结构将被重建），因此哈希表的存储桶数约为两倍。
通常，默认负载因子（0.75）在时间和空间成本之间提供了一个很好的权衡。 较高的值会减少空间开销，但会增加查找成本（在HashMap类的大多数操作中都得到体现，包括get和put）。 设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以最大程度地减少重新哈希操作的次数。 如果初始容量大于最大条目数除以负载因子，则将不会发生任何哈希操作。
如果将许多映射存储在HashMap实例中，则创建具有足够大容量的映射将比让其根据需要增长表的自动重新哈希处理更有效地存储映射。 请注意，使用具有相同hashCode（）的许多键是降低任何哈希表性能的肯定方法。 为了改善影响，当键为Comparable时，此类可以使用键之间的比较顺序来帮助打破这种关系。

HashMap的简单使用

Map<String,String> mapHash = new HashMap<String,String>();
//向map中添加值
mapHash.put("key","tony");
mapHash.put("key2", "tony2");
mapHash.put("key3","shanghai");
System.out.println(mapHash.toString());
//判断map中包含指定的key
System.out.println(mapHash.containsKey("key"));
//判断是否包含指定的值
System.out.println(mapHash.containsValue("tony2"));
//移除元素
mapHash.remove("key");
System.out.println(mapHash.toString());
//移除指定的key和值
mapHash.remove("key2", "tony2");
System.out.println(mapHash.toString());
//获取mapHash大小
int size = mapHash.size();
System.out.println(size);
//遍历
for(Map.Entry<String,String> entry: mapHash.entrySet())
    System.out.println(entry.getKey() + " " + entry.getValue());

//批量添加
Map<String,String> putAllMap = new HashMap<String,String>();
putAllMap.put("key4", "wuhan");
putAllMap.put("key5", "pdxq");
mapHash.putAll(putAllMap);
System.out.println(mapHash.toString());
...

HashMap的源码分析

HashMap中的默认值

//默认的大小 1 << 4 为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
//最大容量，如果任何一个构造函数使用参数隐式指定了更高的值，则必须为2的乘方<= 1 << 30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的扩容因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
 为容器使用树而不是列表时的容器计数阈值。当向至少有这么多节点的bin中添加元素时，bin被转换为树。该值必须大于2，并且至少应该是8，以符合在树移除时关于在收缩时转换回普通箱的假设。
*/
static final int TREEIFY_THRESHOLD = 8;
/**
在调整大小操作期间用于取消树状化（拆分）bin的bin计数阈值。 应小于TREEIFY_THRESHOLD，并且最多为6以与移除下的收缩检测相啮合。
*/
static final int UNTREEIFY_THRESHOLD = 6;
//可将其分类为树木的最小table容量
static final int MIN_TREEIFY_CAPACITY = 64;

构造函数

//使用指定的初始容量和负载因子构造一个空的HashMap
public HashMap(int initialCapacity, float loadFactor) {
	//如果容量小于0 ，抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
    //检查最大的容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //检查扩容因子的格式    
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    //tableSizeFor：对于给定的目标容量，返回两倍大小的幂
    this.threshold = tableSizeFor(initialCapacity);
}
//构造一个空的<tt> HashMap </ tt>，具有指定的初始容量和默认的负载系数（0.75）
public HashMap(int initialCapacity) {
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用默认的初始容量和默认的加载因子构造一个空的HashMap
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//构造一个新的HashMap，其映射与指定的Map相同。HashMap是使用默认负载因子和足以将映射保存在指定的Map中的初始容量创建的。
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    //putMapEntries：实现Map.putAll和Map构造函数
    putMapEntries(m, false);
}

tableSizeFor方法解析

//对于给定的目标容量，返回两倍大小的幂
//为什么会是2的次幂：减少hash的次数，和尽可能让hash平均分布
static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1; //n = n | n >>> 1;
  n |= n >>> 2; //n = n | n >>> 2;
  n |= n >>> 4; //n = n | n >>> 4;
  n |= n >>> 8; //n = n | n >>> 8;
  n |= n >>> 16;//n = n | n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Node<K,V>内部类

static class Node<K,V> implements Map.Entry<K,V> {
   final int hash; //hash值
   final K key; //map中的key
   V value; //map中的值
   Node<K,V> next; //下一个node
   //构造一个node
   Node(int hash, K key, V value, Node<K,V> next) {
       this.hash = hash;
       this.key = key;
       this.value = value;
       this.next = next;
   }
   public final K getKey()        { return key; }
   public final V getValue()      { return value; }
   public final String toString() { return key + "=" + value; }
   //object中的hashCode值
   public final int hashCode() {
   		// ^ 两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1,使用key和value的hashCode生成Node的hashCode
       return Objects.hashCode(key) ^ Objects.hashCode(value);
   }
   //设置node的值，并返回之前的值
   public final V setValue(V newValue) {
       V oldValue = value;
       value = newValue;
       return oldValue;
   }
   //node的比较是否一致，会通过key和值进行比较
   public final boolean equals(Object o) {
       if (o == this)
           return true;
       if (o instanceof Map.Entry) {
           Map.Entry<?,?> e = (Map.Entry<?,?>)o;
           if (Objects.equals(key, e.getKey()) &&
               Objects.equals(value, e.getValue()))
               return true;
       }
       return false;
   }
}

putMapEntries方法解析

//将指定的map集合添加到当前HashMap中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  //获取传入Map的大小
  int s = m.size();
  if (s > 0) {
  	  //table为一个Nod<K,V>的数组
      if (table == null) { // HashMap之前的大小
      	  //计算大小
          float ft = ((float)s / loadFactor) + 1.0F;
          //判断是否操作最大值
          int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                   (int)ft : MAXIMUM_CAPACITY);
          if (t > threshold)
          	  //对于给定的目标容量，返回两倍大小的幂
              threshold = tableSizeFor(t);
      }
      else if (s > threshold)
      	  //初始化或增加表大小。
          resize();
      //进行遍历添加值到hashMap中
      for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
          K key = e.getKey();
          V value = e.getValue();
          putVal(hash(key), key, value, false, evict);
      }
  }
}

resize方法解析

//初始化或增加表大小。 如果为空，则根据字段阈值中保持的初始容量目标进行分配。 否则，因为我们使用的是2的幂，所以每个bin中的元素必须保持相同的索引，或者在新表中以2的幂偏移
final Node<K,V>[] resize() {
	//获取之前的table
    Node<K,V>[] oldTab = table;
    //获取之前的Node<K,V>[]容量大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    //设置新的容量和threshold
    int newCap, newThr = 0;
    if (oldCap > 0) {
    	//判断之前的容量是否大于最大容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //进行新容量的设置和进行判断和之前的容量和大小设置
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
        //
         newThr = oldThr << 1; // 双重门槛
    }
    else if (oldThr > 0) // 初始容量处于阈值
        newCap = oldThr;
    else {               // 零初始阈值表示使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  //重新计算阈值 在table多大的时候进行扩容
    }
    if (newThr == 0) {
    	//获得先关的阈值的大小
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //申明一个node<k,V>的数组，并设置数组的大小为newCap
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab; //设置table值
    if (oldTab != null) {
    	//遍历map中之前的node
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                	//将node添加到新的table中
                	//& 发生位与运算
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                	//treeNode为内部类，判断实例
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { //保持顺序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                    	//进行hash碰撞，进行比对
                        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);
                    //进行相关的赋值操作，生产新的newTab
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

putVal方法解析

//实现Map.put并且关联方法
//hash:key的hash key:key value：值 onlyIfAbsent：如果为true将不改变原来的值 evict：如果为false，则table处于创建模式
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; //为空的情况下，为默认长度的tab数组
        //判断table中是否包含相关的key（通过hash进行计算）
    if ((p = tab[i = (n - 1) & hash]) == null)
    	//如果为空的话，将创建一个node，并管理到table的制定索引下
        tab[i] = newNode(hash, key, value, null); //return new Node<>(hash, key, value, next);
    else {
        Node<K,V> e; 
        K k;
        //检查key是否一致
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; //将p复制给e
        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); //return new Node<>(hash, key, value, next);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                ////检查key是否一致
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 如果map中包含相同的key
            V oldValue = e.value; //获取旧值
            //如果改变原来的值或者原来的值为空，就将新值赋值给e.value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;  //返回旧的值
        }
    }
    ++modCount;
    //判断是否map的大小达到阈值
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

putTreeVal方法解析

//返回包含此节点树的根节点
final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}
//树结构的putVal，改方法是在treeNode内部类中定义的
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    //获取树的根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    //遍历进行设置值
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; 
        K pk;
        //得到parent的hash大于指定的hash
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk))) //如果key相等的情况下
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                //进行tree的查找操作
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

这里展示了相应的添加操作的方法。有些方法讲解没有全部写出.上面进行说明的在进行put操作的情况下，会根据传入的key进行hash,将key的hash作为数组的索引进行存储。同时会通过treeifyBin(tab,hash):除非表太小，否则替换给定哈希值的索引中bin中所有链接的节点，在这种情况下，将调整大小.同时会调用resize进行重置大小。在进行putVal操作的时候会进行判断相关的类型，p instanceof TreeNode，这里会调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);操作。其他相关操作，在后面讲继续写出。哈哈

本文地址：https://blog.csdn.net/qian1314520hu/article/details/107333510