Java集合框架1HashMap

HashMap定义

• 1 本文以jdk7为准进行说明

package java.util;
import java.io.*;
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Serializable{
        static final Entry<?,?>[] EMPTY_TABLE = {}; // 空桶
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // 桶容器
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // 默认容量
        static final float DEFAULT_LOAD_FACTOR = 0.75f;  // 默认负载因子
       
        transient int modCount;
        // 其他成员变量和方法。。。
}

• 2 主要成员属性
  1）table属性是一个数组，数组的元素是Entry<?, ?>，Entry保存的是key-value键值对。
  2）DEFAULT_INITIAL_CAPACITY属性是默认容量，大小为16，是HashMap的默认size值。
  3）DEFAULT_LOAD_FACTOR 属性是默认负载因子，当HashMap的size超过容量 X 负载因子时，HashMap经被扩容。
  4）modCount成员属性用来实现“fast-fail”机制（也就是快速失败）。即在并发集合中，其进行迭代操作时，若有其他线程对其结构性的修改，这是迭代器会立马感知到，并且立刻抛出ConcurrentModificationException异常。

HashMap的数据结构

• 1 当初始化 HashMap 时，系统会创建一个长度为16的Entry数组，数组里存储的元素Entry也被称为“桶（bucket）”，每个 bucket 都有其指定索引，对于HashMap及其子类而言，它们采用Hash算法来计算元素的索引值，即hash(key.hashCode())。
• 2 如果同时有两个以上的Entry的key.hashCode()一样，那么通过Hash算法计算出来的hash值也一样，这样就发生了hash碰撞，会导致该索引位置同时有多个Entry元素；
• 3 但是HashMap 的每个“桶”只能存储一个元素，这种情况下，会通过Entry里的next引用，将这几个Entry组成一个链表（Java8中，当该链表长度大于8时，会将链表转变成红黑树，来提高查询速度）。

HashMap源码分析

• 1 put方法详解

// put方法
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }

    if (key == null) {
        return putForNullKey(value);
    }          

    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
// addEntry方法
public void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

１）判断table是否为空，如果为空则扩充table，其中包括确保table的大小为2的整数倍。
２）如果key值为null，则特殊处理，调用putForNullKey(V value)，hash值为0，存入table中，返回。
３）如果key值不为null，则计算key的hash值；
４）计算key在table中的索引index;
５）通过索引找到table[index]位置上的Entry“桶”，如果该桶为null，则直接进行增加操作；
6）如果该桶不为null，对其进行遍历，如果发现链表中有Entry的的key一致（hash和equals都一致），则用新值（value）替换旧值（oldValue），并保证key的唯一性；如果Entry“桶”内的所有key没有一个和传进来的key一致的，则进行增加操作。
7）增加操作前先判断是否需要扩容，然后将新加的Entry放到table数组中，之前在table数组中的Entry则被新加的Entry的next引用所指向。例如插入的顺序，原先table[index]的Entry链表是 old1->old2->old3，插入新值之后为new1->old1->old2->old3。

• 2 get方法详解

public V get(Object key) {   
    if (key == null) {
        return getForNullKey();
    }
   
    int hash = hash(key.hashCode()); 
  
    for (Entry<K,V> e=table[indexFor(hash, table.length)]; e!=null; e=e.next) {   
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            return e.value;
        }
    }

    return null;   
}   

1）判断key值是否为null，如果是则特殊处理（在table[0]的链表中寻找）
2）否则计算hash值，进而获得table中的index值
3）在table[index]的链表中寻找，根据hash值和equals()方法获得相应的value。
4）如果找不到，最后返回null。

使用自定义的类的对象作为键

• 1 重写自定义类的equals()和hashCode()方法
• 2 当对象插入到Map中之后不能再被改变

HashMap中的序列化问题

• 1 HashMap实现了Serializable接口，但是对table的定义（transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;）却是transient（不再是对象序列化的一部分）的。
• 2 HashMap的put与get基于hashCode的实现，而hashCode是native方法，对每一个不同的java环境来说，同一个key所计算的hashCode是不相同的，所以反序列化后table的index会发生变化，无法还原
• 3 HashMap默认size到达阈值threshold之后进行扩容，很明显HashMap不可能保证每一个bullet都有数据，很多都为null，如果对这部分数据进行序列化则造成不必要的资源浪费。