Java 中的HashMap详解和使用示例_动力节点Java学院整理

第1部分 HashMap介绍

HashMap简介

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。

HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。 

HashMap的构造函数

HashMap共有4个构造函数,如下：

// 默认构造函数。
HashMap()
// 指定“容量大小”的构造函数
HashMap(int capacity)
// 指定“容量大小”和“加载因子”的构造函数
HashMap(int capacity, float loadFactor)
// 包含“子Map”的构造函数
HashMap(Map<? extends K, ? extends V> map)

HashMap的API

void   clear()
Object  clone()
boolean  containsKey(Object key)
boolean  containsValue(Object value)
Set<Entry<K, V>> entrySet()
V   get(Object key)
boolean  isEmpty()
Set<K>  keySet()
V   put(K key, V value)
void   putAll(Map<? extends K, ? extends V> map)
V   remove(Object key)
int   size()
Collection<V> values() 

第2部分 HashMap数据结构

HashMap的继承关系

java.lang.Object
 java.util.AbstractMap<K, V>
  java.util.HashMap<K, V>
public class HashMap<K,V>
 extends AbstractMap<K,V>
 implements Map<K,V>, Cloneable, Serializable { } 

HashMap与Map关系如下图：

从图中可以看出：

(01) HashMap继承于AbstractMap类，实现了Map接口。Map是"key-value键值对"接口，AbstractMap实现了"键值对"的通用函数接口。

(02) HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。

　　table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。

　　size是HashMap的大小，它是HashMap保存的键值对的数量。

　　threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。

　　loadFactor就是加载因子。

　　modCount是用来实现fail-fast机制的。

第3部分 HashMap源码解析(基于JDK1.6.0_45)

为了更了解HashMap的原理，下面对HashMap源码代码作出分析。

在阅读源码时，建议参考后面的说明来建立对HashMap的整体认识，这样更容易理解HashMap。 

 package java.util;
 import java.io.*;
 public class HashMap<K,V>
 extends AbstractMap<K,V>
 implements Map<K,V>, Cloneable, Serializable
 {
 // 默认的初始容量是16，必须是2的幂。
 static final int DEFAULT_INITIAL_CAPACITY = 16;
 // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
 static final int MAXIMUM_CAPACITY = 1 << 30;
 // 默认加载因子
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 // 存储数据的Entry数组，长度是2的幂。
 // HashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表
 transient Entry[] table;
 // HashMap的大小，它是HashMap保存的键值对的数量
 transient int size;
 // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
 int threshold;
 // 加载因子实际大小
 final float loadFactor;
 // HashMap被改变的次数
 transient volatile int modCount;
 // 指定“容量大小”和“加载因子”的构造函数
 public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
  throw new IllegalArgumentException("Illegal initial capacity: " +
       initialCapacity);
  // HashMap的最大容量只能是MAXIMUM_CAPACITY
  if (initialCapacity > MAXIMUM_CAPACITY)
  initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
  throw new IllegalArgumentException("Illegal load factor: " +
       loadFactor);
  // 找出“大于initialCapacity”的最小的2的幂
 int capacity = 1;
 while (capacity < initialCapacity)
  capacity <<= 1;
  // 设置“加载因子”
  this.loadFactor = loadFactor;
  // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
  threshold = (int)(capacity * loadFactor);
  // 创建Entry数组，用来保存数据
  table = new Entry[capacity];
  init();
 }
 // 指定“容量大小”的构造函数
 public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
 // 默认构造函数。
 public HashMap() {
  // 设置“加载因子”
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
  threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
  // 创建Entry数组，用来保存数据
  table = new Entry[DEFAULT_INITIAL_CAPACITY];
  init();
 }
 // 包含“子Map”的构造函数
 public HashMap(Map<? extends K, ? extends V> m) {
  this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + ,
   DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
  // 将m中的全部元素逐个添加到HashMap中
  putAllForCreate(m);
 }
 static int hash(int h) {
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> ) ^ (h >>> );
 }
 // 返回索引值
 // h & (length-)保证返回值的小于length
 static int indexFor(int h, int length) {
  return h & (length-);
 }
 public int size() {
  return size;
 }
 public boolean isEmpty() {
 return size == 0;
 }
 // 获取key对应的value
 public V get(Object key) {
  if (key == null)
  return getForNullKey();
  // 获取key的hash值
  int hash = hash(key.hashCode());
  // 在“该hash值对应的链表”上查找“键值等于key”的元素
  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;
 }
 // 获取“key为null”的元素的值
 // HashMap将“key为null”的元素存储在table[]位置！
 private V getForNullKey() {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null)
   return e.value;
  }
  return null;
 }
 // HashMap是否包含key
 public boolean containsKey(Object key) {
  return getEntry(key) != null;
 }
 // 返回“键为key”的键值对
 final Entry<K,V> getEntry(Object key) {
  // 获取哈希值
  // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值
 int hash = (key == null) ? 0 : hash(key.hashCode());
  // 在“该hash值对应的链表”上查找“键值等于key”的元素
  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 != null && key.equals(k))))
   return e;
  }
  return null;
 }
 // 将“key-value”添加到HashMap中
 public V put(K key, V value) {
  // 若“key