HashMap简介

HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表办理斗嘴问题,容量不敷(高出了阀值)时,同样会自动增长。

HashMap长短线程安详的,只是用于单线程情况下,多线程情况下可以回收concurrent并发包下的concurrentHashMap。

HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆。

HashMap源码分解

HashMap的源码如下(插手了较量具体的注释):

package java.util;    
import java.io.*;    
       
public class HashMapextends AbstractMapimplements Map, Cloneable, Serializable    
{    
       
    // 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必需是2的整数次幂。    
    static final int DEFAULT_INITIAL_CAPACITY = 16;    
       
    // 最大容量(必需是2的幂且小于2的30次方,传入容量过上将被这个值替换)    
    static final int MAXIMUM_CAPACITY = 1 << 30;    
       
    // 默认加载因子为0.75   
    static final float DEFAULT_LOAD_FACTOR = 0.75f;    
       
    // 存储数据的Entry数组,长度是2的幂。    
    // HashMap回收链表法办理斗嘴,每一个Entry本质上是一个单向链表    
    transient Entry[] table;    
       
    // 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;    
        //加载因此不能小于0  
        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() {    
        // 配置“加载因子”为默认加载因子0.75    
        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 m) {    
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,    
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);    
        // 将m中的全部元素逐个添加到HashMap中    
        putAllForCreate(m);    
    }    
       
    //求hash值的要领,从头计较hash值  
    static int hash(int h) {    
        h ^= (h >>> 20) ^ (h >>> 12);    
        return h ^ (h >>> 7) ^ (h >>> 4);    
    }    
       
    // 返回h在数组中的索引值,这里用&取代取模,旨在晋升效率   
    // 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 (Entrye = table[indexFor(hash, table.length)];    
             e != null;    
             e = e.next) {    
            Object k;    
            //判定key是否沟通  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))    
                return e.value;    
        }  
        //没找到则返回null  
        return null;    
    }    
       
    // 获取“key为null”的元素的值    
    // HashMap将“key为null”的元素存储在table[0]位置,但不必然是该链表的第一个位置!    
    private V getForNullKey() {    
        for (Entrye = 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 EntrygetEntry(Object key) {    
        // 获取哈希值    
        // HashMap将“key为null”的元素存储在table[0]位置,“key不为null”的则挪用hash()计较哈希值    
        int hash = (key == null) ? 0 : hash(key.hashCode());    
        // 在“该hash值对应的链表”上查找“键值便是key”的元素    
        for (Entrye = 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 (Entrye = 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++;  
        //将key-value添加到table[i]处  
        addEntry(hash, key, value, i);    
        return null;    
    }    
       
    // putForNullKey()的浸染是将“key为null”键值对添加到table[0]位置    
    private V putForNullKey(V value) {    
        for (Entrye = table[0]; e != null; e = e.next) {    
            if (e.key == null) {    
                V oldValue = e.value;    
                e.value = value;    
                e.recordAccess(this);    
                return oldValue;    
            }    
        }    
        // 假如没有存在key为null的键值对,则直接题阿见到table[0]处!    
        modCount++;    
        addEntry(0, null, value, 0);    
        return null;    
    }    
       
    // 建设HashMap对应的“添加要领”,    
    // 它和put()差异。putForCreate()是内部要领,它被结构函数等挪用,用来建设HashMap    
    // 而put()是对外提供的往HashMap中添加元素的要领。    
    private void putForCreate(K key, V value) {    
        int hash = (key == null) ? 0 : hash(key.hashCode());    
        int i = indexFor(hash, table.length);    
       
        // 若该HashMap表中存在“键值便是key”的元素,则替换该元素的value值    
        for (Entrye = table[i]; e != null; e = e.next) {    
            Object k;    
            if (e.hash == hash &&    
                ((k = e.key) == key || (key != null && key.equals(k)))) {    
                e.value = value;    
                return;    
            }    
        }    
       
        // 若该HashMap表中不存在“键值便是key”的元素,则将该key-value添加到HashMap中    
        createEntry(hash, key, value, i);    
    }    
       
    // 将“m”中的全部元素都添加到HashMap中。 
//本栏目
		 

JAVA 教程

2017-12-28


HashMap简介 HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表办理斗嘴问题,容量不敷(高出了阀值)时,同样会自动增长。 HashMap