电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 从代码层读懂Java HashMap的实现原理（2） [打印本页]

作者: yuyang911220 时间: 2017-4-22 17:22 标题: 从代码层读懂Java HashMap的实现原理（2）

HashMap源码：
package java.util;
import java.io.*;
public class HashMap<K,V>    extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable {
//  默认的初始容量（容量为HashMap中桶的数目）是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) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
      // 将m中的全部元素逐个添加到HashMap中
      putAllForCreate(m);
}
static int hash(int h) {
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);
}
// 返回索引值
// h & (length-1)保证返回值的小于length
static int indexFor(int h, int length) {
      return h & (length-1);
}
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[0]位置！
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为null”，则将该键值对添加到table[0]中。
      if (key == null)
         return putForNullKey(value);
      // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
      int hash = hash(key.hashCode());
      int i = indexFor(hash, table.length);
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
         Object k;
         // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
         }
      }
      // 若“该key”对应的键值对不存在，则将“key-value”添加到table中
      modCount++;
      addEntry(hash, key, value, i);
      return null;
}

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)