首页 > 代码库 > HashMap源码分析

HashMap源码分析

  最近一直特别忙,好不容易闲下来了。准备把HashMap的知识总结一下,很久以前看过HashMap源码。一直想把集合类的知识都总结一下,加深自己的基础。我觉的java的集合类特别重要,能够深刻理解和应用这些集合类能够让自己写的程序上一步台阶。  

  本文主要根据自己学习与使用HashMap来解析HashMap的源码,深入到HashMap的内部结构和实现,增强自己的基础知识。同时会借鉴网上的相关资料,深入理解HashMap.

HashMap的内部存储结构

  一提到HashMap我们就知道键值对,即一个键对应一个值。可能我们经常会使用HashMap,但是并不关注里面的内部实现。今天我们就来学习一下HashMap的内部实现。

  HashMap是一种以键值对存储数据的容器,每个对象在java中都会有一个hashCode,HashMap正是借每个对象的HashCode来组织键值对的存储,因为HashCode的特性,使得HashMap以非常快速和高效地地根据键值key进行数据的存取。键值对的具体实现在HashMap内部会封装成一个Entry[] table,Entry[] table是键值对的表现形式。下图为HashMap的存储结构。HashMap中Value可以相同,但是键不可以相同.

技术分享

 

  上图可以看出来HashMap是数组+链表的存储结构,数组的每一个元素是一个链表的表头。这样的结构能够综合2个经常使用的数据结构的特点,数组查找、遍历快,链表增加、删除快。

HashMap的属性

  static final int DEFAULT_INITIAL_CAPACITY = 16;//默认初始化加载容量,即table数组的长度。

  static final int MAXIMUM_CAPACITY = 1 << 30;//最大的容量。1左移30位,2的30次方:1073741824

  static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认加载因子为0.75

   transient Entry[] table;//table数组,上图的黄色部分。Entry为蓝色部分  

   transient int size;//HashMap存储元素的数量。

  int threshold;//阀值  table的长度*加载因子(默认wei0.75)

  final float loadFactor;//加载因子

  transient volatile int modCount;//修改次数

  注:如果用transient声明一个实例变量,当对象存储时,它的值不需要维持。换句话来说就是,用transient关键字标记的成员变量不参与序列化过程。

    volatile为同步变量,保证每次都读取的值是最新的。

HashMap的构造方法

  public HashMap() {//最常用的改造方法
        this.loadFactor = DEFAULT_LOAD_FACTOR;//默认加载因子,0.75
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//阀值  默认的容量*加载英子。12
        table = new Entry[DEFAULT_INITIAL_CAPACITY];//table数组的默认为16,容量为16,切记容量不等于HashMap存储的元素数量,容易混淆。
        init();//初始化方法,里面是个空
    }

  默认的构造方法开辟16个大小的空间。还有另外一个构造方法我们使用的比较少,当你觉的默认的HashMap的存储空间浪费时(容量达到3/4时HashMap就会调用resize扩大为原来的2倍),可以使用下面一个。

   public HashMap(int initialCapacity, float loadFactor) {//初始化容量,加载因子
        if (initialCapacity < 0)//容量不能小于0
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)//大于允许最大的容量时,设置未最大值
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))//加载因子小于大于0或者不是数字的时候,报非法加载因子异常
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)//实际的开辟的空间要大于传入的第一个参数的值。
            capacity <<= 1;//这是一个重点,capacity才是容量。
        this.loadFactor = loadFactor;//加载因子设置为传入的值
        threshold = (int)(capacity * loadFactor);//阈值
        table = new Entry[capacity];//数组
        init();
    }

  此外还有2个构造方法基本上很少用到,感兴趣的可以自己看看。HashMap最重要的方法是put和get方法,下面我们重点看看这2个方法。

HashMap的put方法分析

      public V put(K key, V value) {//很熟悉的方法
        if (key == null)//如果key==null,直接设置空的
            return putForNullKey(value);
        int hash = hash(key.hashCode());//获得hash值
        int i = indexFor(hash, table.length);//根据hash值找到此键值对应该放在数组的第几个位置。
        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 = http://www.mamicode.com/e.value;
                e.value = http://www.mamicode.com/value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);//不存在就新增
        return null;
    }

  put方法会先判断键是不是空,如果为空就调putForNullKey方法。方法如下:

  private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {//获得第一个链表,遍历查找是否原来就存储为null的键值对
            if (e.key == null) {//如果存在
                V oldValue = http://www.mamicode.com/e.value;//记录下老的值
                e.value = http://www.mamicode.com/value;//把新值设置进去
                e.recordAccess(this);
                return oldValue;//返回老值
            }
        }
        modCount++;
        addEntry(0, null, value, 0);// Key 为null,则将Entry<null,Value>放置到第一桶table[0]中
        return null;
    }

  计算Hash值的方法如下:

  static int hash(int h) {//根据特定的hashcode 重新计算hash值
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

  static int indexFor(int h, int length) {//匹配到具体的桶当中,
        return h & (length-1);//相当于int i = hash % Entry[].length;得到i后,就是在Entry数组中的位置
    }

  整个put方法的流程如下:

  1. 首先判断键是否为空,如果为空在判断是否已经存在键为空的键值对,存在就更新值,不存在就新增;
  2. 如果键不为空,则获取这个Key的hashcode值,根据此值确定键值对的存储位置;
  3. 遍历所在桶中的Entry<Key,Value>链表,查找其中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,若已存在,定位到对应的Entry<Key,Value>,其中的Value值更新为新的Value值;返回旧值;若不存在,则根据键值对<Key,Value> 创建一个新的Entry<Key,Value>对象,然后添加到这个桶的Entry<Key,Value>链表的头部。
  4. 当前的HashMap的大小(即Entry<key,Value>节点的数目)是否超过了阀值,若超过了阀值(threshold),则增大HashMap的容量(即Entry[] table 的大小),并且重新组织内部各个Entry<Key,Value>排列。

 HashMap的get方法分析

  public V get(Object key) {
        if (key == null)//如果键等于null,调用getForNullKey
            return getForNullKey();
        int hash = hash(key.hashCode());//获得hash值,
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {//indexfor计算存储位置,根据位置遍历链表
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;//拿到对应的值
        }
        return null;
    }

  如果键等于null,调用getForNullKey

  private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {//键为null的键值对存储在数组的第一个元素,
            if (e.key == null)//如果存在则返回值
                return e.value;
        }
        return null;//不存在返回null
    }

  get方法比较简单,比较容易理解。主要流程如下:

  1. 首先判断键是否为空,如果为空在table[0]中取键为空的键值对,如果不存在为空的则返回null。
  2. 如果键不为空,则获取这个Key的hashcode值,根据此值确定该键值对的存储位置;
  3. 遍历所在桶中的Entry<Key,Value>链表,查找其中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,若已存在,定位到对应的Entry<Key,Value>,获得Value值;返回旧值;若不存在,则返回空。

HashMap的总结

  本文主要讲了HashMap的存储结构以及基本属性、构造方法,同时分析了比较常用的put和get方法。其他方法请读者自行查看。在看HashMap的源码时,我认为以下几个方面比较重要,能够理解到以下的几点,搞定HashMap基本不成问题。

  1. HashMap的存储结构,以及为什么要这样进行存储。
  2. HashMap的各个属性的含义,以及其扩容的策略(扩容算法)。
  3. Hash值的计算.确定桶的位置。
  4. HashMap中的value可以相同,键不可以相同。
  5. HashMap是非线程安全的。

HashMap源码分析