Java 中 HashMap 详解

Java 中 HashMap 详解

2.HashMap 的 put 和 get 操作过程

3.HashMap 的扩容

4.关于 transient 关键字

HashMap 的存储结构

1. HashMap 总体是数组+链表的存储结构， 从 JDK1.8 开始，当数组的长度大于 64，且链表的长度大于 8 的时候，会把链表转为红黑树。

2. 数组的默认长度是 16。数组中的每一个元素为一个 node，也就是链表的一个节点，node 的数据包含: key 的 hashcode, key, value,指向下一个 node 节点的指针。

部分源码如下：

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {        this.hash = hash;        this.key = key;        this.value = value;        this.next = next;    }

...}3. 随着 put 操作的进行，如果数组的长度超过 64，且链表的长度大于 8 的时候， 则将链表转为红黑树，红黑树节点的结构如下,TreeNode 继承的 LinkedHashMap.Entry 是继承 HashMap.Node 的，所以 TreeNode 是上面 Node 的子类。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}//...}4. HashMap 类的主要成员变量：

/* ---------------- Fields -------------- */

/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */transient Node<K,V>[] table;
/** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */transient Set<Map.Entry<K,V>> entrySet;
/** * The number of key-value mappings contained in this map. */transient int size;
/** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash).  This field is used to make iterators on Collection-views of * the HashMap fail-fast.  (See ConcurrentModificationException). */transient int modCount;
/** * The next size value at which to resize (capacity * load factor). * * @serial */// (The javadoc description is true upon serialization.// Additionally, if the table array has not been allocated, this// field holds the initial array capacity, or zero signifying// DEFAULT_INITIAL_CAPACITY.)int threshold;
/** * The load factor for the hash table. * * @serial */final float loadFactor;

View CodeHashMap 的 put 操作过程本小节讲述 put 操作中的主要步骤，细小环节会忽略。

1. map.put(key, value)，首先计算 key 的 hash，得到一个 int 值。

2.如果 Node 数组为空则初始化 Node 数组。这里注意，Node 数组的长度 length 始终应该是 2 的 n 次方，比如默认的 16, 还有 32,64 等

3.用 hash&(length-1) 运算得到数组下标，这里要提一句，其实正常我们最容易想到的，而且也是我之前很长一段时间以为的，这一步应该进行的是求模运算: hash % length ,这样得到的正好是 0~length-1 之间的值，可以作为数组的下标， 那么为何此处是位与运算呢？

先说结论： 上面提到数组的长度 length 始终是 2^n,在这个前提下，hash & (length-1) 与 hash % length 是等价的。 而位与运算更快。这里后面会另开一遍进行详解。

4. 如果 Node[hash&(length-1)]处为空，用传入的的 key, value 创建 Node 对象，直接放入该下标；如果该下标处不为空，且对象为 TreeNode 类型，证明此下标处的元素们是按照红黑树的结构存储的，将传入的 key，value 作为新的红黑树的节点插入到红黑树；否则，此处为链表，用 next 找到链表的末尾，将新的元素插入。如果在遍历链表的过程中发现链表的长度超过了 8，此时如果数组长度<64 则进行扩容，否则转红黑树。

5. 如果 key 的 hash 和 key 本身都相等则将该 key 对应的 value 更新为新的 value

6. 需要扩容的话则进行扩容。

注意：

1. 如果 key 是 null 则返回的 hash 为 0，也就是 key 为 null 的元素一直被放在数组下标为 0 的位置。

2. 在 JDK 1.8 以前，链表是采用的头部插入的方式，从 1.8 改成了在链表尾部插入新元素的方式。 这么做是为了防止在扩容的时候，多线程时出现循环链表死循环。具体会新开一遍进行详细演绎。

HashMap 的 get 操作过程 get 的过程比较简单。

1. map.get(key). 首先计算 key 的 hash。

2. 根据 hash&(length-1)定位到 Node 数组中的一个下标。如果该下标的元素(也就是链表/红黑树的第一个元素)中 key 的 hash 的 key 本身 都和传入的 key 相同，则证明找到了元素，直接返回即可。

3.如果第一个元素不是要找的，如果第一个元素的类型是 TreeNode，则按照红黑树的查找方法查找元素，如果不是则证明是链表，按照 next 指针找下去，直到找到或者到达队尾。

HashMap 的扩容先说这里的两个概念: size, length.

size：是 map.size() 方法返回的值，表示的是 map 中有多少个 key-value 键值对儿

length: 这里是指 Node 数组的长度，比如默认长度是 16.

如下面的代码：

    Map<Integer,String> map = new HashMap<>();    map.put(1,"a");    map.put(2,"b");    map.put(3,"c");    

没有在构造函数中指定 HashMap 的大小，则数组的长度 length 取默认的 16，put 了 3 个元素，则 size 为 3.

Q: 何时需要扩容呢？A: 在 put 方法中，每次完成了 put 操作，都判断一下++size 是否大于 threshold,如果大于则进行扩容: 调用 resize()方法。

Q: 那么 threshold 又是如何得到的呢？A: 简单来讲 threshold = length * loadfactor(默认为 0.75)。 也就是说默认情况下，map 中的键值对的个数(size)大于 Node 数组长度(length)的 75%时，就需要扩容了。

Q: 扩容时具体做什么呢？A: 首先计算出新的数组长度和新的 threshold(阈值). 简单来讲，新的 length/capacity 是原来的 2 倍（位运算左移一位），新的 threshold 为原来的 2 倍。 还有一些细节此处不再赘述。创建新的 Node 数组，将原来数组中的元素重新映射到新的数组中。

关于 transient 关键字 transient 关键字的作用：用 transient 关键字修饰的字段不会被序列化

查看下面的例子:

public class TransientExample implements Serializable{private String firstName;private transient String middleName;private String lastName;

public TransientExample(String firstName,String middleName,String lastName) {    this.firstName = firstName;    this.middleName = middleName;    this.lastName = lastName;}@Overridepublic String toString() {    StringBuilder sb = new StringBuilder();    sb.append("firstName:").append(firstName).append("\n")            .append("middleName:").append(middleName).append("\n")            .append("lastName:").append(lastName);    return sb.toString();

}

public static void main(String[] args) throws Exception {    TransientExample e = new TransientExample("Adeline","test","Pan");
    ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("/path/testObj"));    oos.writeObject(e);
    ObjectInputStream ois = new ObjectInputStream(new FileInputStream("/path/testObj"));    TransientExample e1 = (TransientExample) ois.readObject();
    System.out.println("e:"+e.toString());    System.out.println("e1:"+e1.toString());

}

}

View Code 输出结果：

e:firstName:AdelinemiddleName:testlastName:Pan

e1:firstName:AdelinemiddleName:nulllastName:Pan 被 transient 关键字修饰的 middleName 字段没有被序列化，反序列化回来的值是 null

Q：HashMap 类是实现了 Serializable 接口的，那么为何其中的 table, entrySet 变量都标为 transient 呢？A：我们知道，table 数组中元素分布的下标位置是根据元素中 key 的 hash 进行散列运算得到的，而 hash 运算是 native 的，不同平台得到的结果可能是不相同的。举一个简单的例子，假设我们在目前的平台有键值对 key1-value1,计算出 key1 的 hash 为 1， 计算后存在 table 数组中下标为 1 的地方，假设 table 被序列化了，并传输到了另外的平台，并反序列化为了原来的 HashMap，key1-value1 仍然存在下标 1 的位置，当在这个平台运行 get("key1")的时候，可能计算出 key1 的 hash 为 2，就有可能到下标为 2 的地方去找该元素，这样就出错了。

Q：那么 HashMap 是如何实现的序列化呢？A：HashMap 是通过实现如下方法直接将元素数量(size), key, value 等写入到了 ObjectOutputStream 中，实现的定制化的序列化和反序列化。在 Serializable 接口中有关于这种做法的说明。

private void writeObject(java.io.ObjectOutputStream out)

throws IOException

private void readObject(java.io.ObjectInputStream in)

throws IOException, ClassNotFoundException;