本图的结构与HashMap拾分相似,所以不用在多线程

2019-09-22 04:54栏目:大奖888官网登录
TAG:

04、小结

在之前很长的一段时间内,我对HashMap的认知仅限于会用它的put(key, value)value = get

但,当我强迫自己每周要输出一篇Java方面的技术文章后,我对HashMap真的“深入浅出”了——散列值、散列冲突、初始容量和负载因子,竟然能站在我面前一直笑——而原先,我见到这些关键字就逃之夭夭了,我怕见到它们。


推荐阅读:

Java泛型的重要目的:别让猫别站在狗队里
Java中食之无味弃之可惜的数组

HashMap存储数据的过程

大概的过程是这样的:

计算hash值

    final int hash(Object k) {
        ... ...
    }

将hash值转换为数组索引

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

对数组进行存储
存储时若该位置有值,则判断是否equals:是,则替换;否,则将其插入链表表头

看一下源码:

    public V put(K key, V value) {
        ... ...(这里忽略了对null键的处理)
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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 = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

通过源码可以看出,我们调用put后:

  1. 先处理null键的情况(阅读源码的处理方式为:存在替换,不存在插入table[0])
  2. 计算hash值
  3. 通过hash值计算数组中索引位置
  4. 遍历该位置的链表
    若存在该值(equals返回true),则替换并返回旧值
    若不存在则调用addEntry方法,我们看一下这个方法:
    void addEntry(int hash, K key, V value, int bucketIndex) {
        ... ...(省略处理resize)
        createEntry(hash, key, value, bucketIndex);
    }

该方法调用了createEntry,再来看一下:

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

在本方法中,将原来的值e变为了新值的next(将新值插入了链表头部

可以看一下Entry的构造方法:

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

HashMap 源码解析,hashmap源码解析

HashMap简介:

  HashMap在日常的开发中应用的非常之广泛,它是基于Hash表,实现了Map接口,以键值对(key-value)形式进行数据存储,HashMap在数据结构上使用的是数组+链表。允许null键和null值,不保证键值对的顺序。

HashMap检索数据的大致流程:

  当我们使用HashMap搜索key所对应的value时,HashMap会根据Hash算法对key进行计算,得到一个key的hash值,再根据hash值算出该key在数组中存储的位置index,然后获取数组在index位置的键值对e,再使用链表对e进行遍历,查找遍历的元素是否和给定的key相符合,若有符合的,则返回其value值。

 自己手动画了一个HashMap的数据结构图:

图片 1

HashMap源码分析:

  HashMap是存储键值对的集合,实现了Map接口,下面我们看一下Map接口的定义:

 

/**
*映射key到value的顶级接口,不能包含重复的key,一个key最多可以映射到一个value,键和值均可为null
*/
public interface Map<K,V> {

    //返回该map包含的键值对的个数,如果键值对的个数超过了Integer.MAX_VALUE,则返会Integer.MAX_VALUE
    int size();

    //如果该Map没有包含键值对,则返回true,否则返回false
    boolean isEmpty();

    //判断该map是否包含指定的key所对应的键值对,key可以为null
    boolean containsKey(Object key);

    //判断该map是否包含指定的value所对应的键值对,若map中包含有一个及以上的key,对应指定的value,则返回true,value可以为null
    boolean containsValue(Object value);

    //返回指定的key所对应的value,若key不存在,则返回null;但是返回null的key,不代表key在map中不存在,有可能是key所对应的value为null
    V get(Object key);

    //将指定的key和value映射为一个键值对,放入map中;若之前该map中包含了指定的Key,则该key所对应的老的值oldValue将会被替换为value
    V put(K key, V value);

    //删除指定的key所对应的键值对,并返回该key对应的value
    V remove(Object key);

    //将指定的map中的键值对复制到当前map中
    void putAll(Map<? extends K, ? extends V> m);

    //清除map中所有的键值对,该操作完成后,该map就是空的了
    void clear();

    //将map中所有的key返回,由于map中的key是不能重复的,所以用Set集合的方式装载所有的key
    Set<K> keySet();

    //将map中所有的value返回,由于map中的value是可重复的,所以用Collection集合的方式装载所有的value
    Collection<V> values();

    //将map中所有的键值对Entry返回,由于map中的键值对是不可重复的(key不可重复),所以用Set集合的方式装载所有的value
    Set<Map.Entry<K, V>> entrySet();

    //Map中承载键值对的数据结构Entry
    interface Entry<K,V> {

        //返回键值对的键值key
        K getKey();

        //返回键值对的value值
        V getValue();

        //将当前键值对的value值 替换为指定的value值
        V setValue(V value);

        //判断指定的对象和当前键值对是否equals相等,若相等,则代表是同一个键值对;
        boolean equals(Object o);

        //返回当前键值对的hashCode值
        int hashCode();
    }

    //判断指定对象和当前Map的equals是否相等
    boolean equals(Object o);

    //返回当前Map的hashCode
    int hashCode();
}

 

 

下面我们具体的看一下HashMap:

    //HashMap是基于hash表来实现Map接口的,HashMap维护了下面几个变量:

    //HashMap默认的初始化大小为16
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    //HashMap包含键值对的最大容量为2^30,HashMap的容量一定要是2的整数次幂
    static final int MAXIMUM_CAPACITY = 1 << 30;

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

    //装载键值对的内部容器Entry数组,长度一定得是2的幂
    transient Entry[] table;

    //HashMap中包含的键值对的个数
    transient int size;

    //HashMap的极限 当键值对的个数达到threshold时,数组table要扩容的
    int threshold;

    //加载因子
    final float loadFactor;

    //HashMap结构上被改变的次数,结构上的改变包括:键值对的大小的改变,修改HashMap的内部结构(比较进行了rehash操作),此属性用来保持fail-fast
    transient volatile int modCount;

接下来我们看一下HashMap的构造函数:

/**
*根据指定的容量initialCapacity和加载因子loadFactor构造HashMap
*/
    public HashMap(int initialCapacity, float loadFactor) {
        //对initialCapacity进行参数校验,若小于0,则抛出IllegalArgumentException异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //若initialCapacity大于MAXIMUM_CAPACITY(2^30),则将MAXIMUM_CAPACITY赋值给initialCapacity
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //对参数loadFactor进行有效性校验,不能<=0,不能非数字,否则抛出IllegalArgumentException异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity 找到一个2的幂的数capacity,使其不小于参数initialCapacity
        int capacity = 1;
        //若capacity小于initialCapacity,则将capacity扩大一倍
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        //设置极限,大小为 capacity * loadFactor,即(容量*负载因子)
        threshold = (int)(capacity * loadFactor);
        //创建一个大小为capacity的Entry数组table,用来保存键值对
        table = new Entry[capacity];
        //调用方法init(),进行额外的初始化操作
        init();
    }
    //init方法是空的,如果你定制额外的初始化操作,可以继承HashMap,覆盖init()方法
    void init() {

    }

    //通过指定的容量initialCapacity来构造HashMap,这里使用了默认的加载因子DEFAULT_LOAD_FACTOR 0.75
    public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    //无参的构造函数 加载因子为DEFAULT_LOAD_FACTOR 0.75,容量为默认的DEFAULT_INITIAL_CAPACITY 16,极限为 16*0.75=12
    public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
            table = new Entry[DEFAULT_INITIAL_CAPACITY];
            init();
    }

 

下面我们看一下HashMap中承载键值对的数据结构Entry的实现,Entry<K,V>是HashMap的一个静态内部类

/**
*Entry是HashMap里面承载键值对数据的数据结构,实现了Map接口里面的Entry接口,除了方法recordAccess(HashMap<K,V> m),recordRemoval(HashMap<K,V> m)外,其他方法均为final方法,表示即使是子类也不能覆写这些方法。
*/
static class Entry<K,V> implements Map.Entry<K,V> {
        //键值,被final修饰,表明一旦赋值,不可修改
        final K key;
        //value值
        V value;
        //下一个键值对的引用
        Entry<K,V> next;
        //当前键值对中键值的hash值
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        //设置value值,返回原来的value值
        public final V setValue(V newValue) {
          V oldValue = value;
            value = newValue;
            return oldValue;
        }
        //比较键值对是否equals相等,只有键、值都相等的情况下,才equals相等
        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            //若k1 == k2(k1,k2引用同一个对象),或者k1.equals(k2)为true时,进而判断value值是否相等
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                //若v1 == v2(v1,v2引用同一个对象),或者v1.equals(v2)为true时,此时才能说当前的键值对和指定的的对象equals相等
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            //其他均为false
            return false;
        }

        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        //此方法只有在key已存在的时候调用m.put(key,value)方法时,才会被调用,即覆盖原来key所对应的value值时被调用
        void recordAccess(HashMap<K,V> m) {
        }
        //此方法在当前键值对被remove时调用
        void recordRemoval(HashMap<K,V> m) {
        }
}

 

下面是Hash的put方法的实现:

/**
*将指定的键key,值value放到HashMap中
*/
public V put(K key, V value) {
    //首先判断键key是否为null,若为null,则调用putForNullKey(V v)方法完成put
    if (key == null)
        return putForNullKey(value);
    //程序走到这,说明key不为null了,先调用hash(int)方法,计算key.hashCode的hash值
    int hash = hash(key.hashCode());
    //再调用indexFor(int,int)方法求出此hash值对应在table数组的哪个下标i上 (bucket桶)
    int i = indexFor(hash, table.length);
    //遍历bucket桶上面的链表元素,找出HashMap中是否有相同的key存在,若存在,则替换其value值,返回原来的value值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //若元素e.hash值和上面计算的hash值相等,并且(e.key == 入参key,或者入参key equals 相等 e.key),则说明HashMap中存在了和入参相同的key了,执行替换操作
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            //在执行替换操作的时候,调用Entry对象的recordAccess(HashMap<K,V> m)方法,这个上面说过了
            e.recordAccess(this);
            return oldValue;
        }
    }
    //程序走到这,说明原来HashMap中不存在key,则直接将键值对插入即可,由于插入元素,修改了HashMap的结构,因此将modeCount+1
    modCount++;
    //调用addEntry(int,K,V,int)方法进行键值对的插入
    addEntry(hash, key, value, i);
    //由于原来HashMap中不存在key,则不存在替换value值问题,因此返回null
    return null;
}

当key为null时,HashMap是这样进行数据插入的:

//先看看HashMap中原先是否有key为null的键值对存在,若存在,则替换原来的value值;若不存在,则将key为null的键值对插入到Entry数组的第一个位置table[0]
private V putForNullKey(V value) {
    //获取Entry数组的第一个元素:table[0],然后通过e.next进行链表的遍历,若遍历过程中有元素e.key为null,则替换该元素的值
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //说明原来之前HashMap中就已经存在key问null的键值对了,现在又插入了一个key为null的新元素,则替换掉原来的key为null的value值
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            //在执行替换操作的时候,调用Entry对象的recordAccess(HashMap<K,V> m)方法,这个上面说过了
            e.recordAccess(this);
            return oldValue;
        }
    }
    //程序走到这,说明HashMap中原来没有key为null的键值对,需要直接插入元素,由于插入元素,修改了HashMap的结构,因此将modeCount+1
    modCount++;
    //调用addEntry(int,K,V,int)方法进行键值对的插入,这里将入参hash设置为0,K为null,插入的位置index也为0,说明key为null的元素插入在bucket[0]第一个桶上
    addEntry(0, null, value, 0);
    return null;
}

 

HashMap在插入数据之前,要根据key值和hash算法来计算key所对应的hash值

//根据key的hashCode值,来计算key的hash值
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

/**
*在HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置,如何计算这个位置就是hash算法.
*HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,
*那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表.
*所以我们首先想到的就是把hashcode对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的,但是,“模”运算的消耗还是比较大的,
*能不能找一种更快速,消耗更小的方式那?java中时这样做的 :将hash值和数组长度按照位与&来运算
*/
static int indexFor(int h, int length) {
    return h & (length-1);
}

下面我们看一看实际进行数据添加的操作addEntry方法

/**
*将指定的key,value,hash,bucketIndex 插入键值对,若此时size 大于极限threshold,则将Entry数组table扩容到原来容量的两倍
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
    //取出原来bucketIndex处的键值对e
    Entry<K,V> e = table[bucketIndex];
    //创建一个新的键值对,使用给定的hash、key、value,并将新键值对的next属性指向e,最后将新键值对放在bucketIndex处
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //将size+1,若此时size 大于极限threshold,则将Entry数组table扩容到原来容量的两倍
    if (size++ >= threshold)
        //调用resize(int)方法,进行数组的扩容
        resize(2 * table.length);
}

 

我们知道HashMap采用的数组+链表来实现的,当HashMap中元素的个数size大于极限threshold时,会进行数组的扩容操作,这个操作使用resize(int newCapacity)方法实现的:

/**
*将HashMap中Entry数组table的容量扩容至新容量newCapacity,数组的扩容不但涉及到数组元素的复制,还要将原数组中的元素rehash到新的数组中,很耗时;如果能预估到放入HashMap中元素的大小,最好使用new HashMap(size)方式创建足够容量的HashMap,避免不必要的数组扩容(rehash操作),提高效率
*/
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //如果原数组的大小已经为允许的最大值MAXIMUM_CAPACITY了,则不能进行扩容了,这里仅仅将极限threshold设置为Integer.MAX_VALUE,然后返回
    if (oldCapacity == MAXIMUM_CAPACITY) {
        //将极限threshold设置为Integer.MAX_VALUE
        threshold = Integer.MAX_VALUE;
        return;
    }
    //程序走到这,说明可以进行扩容,先创建容量为newCapacity的新Entry数组newTable
    Entry[] newTable = new Entry[newCapacity];
    //调用tranfer(Entry[] newTable)方法,进行数组元素的移动和rehashing
    transfer(newTable);
    //将新数组newTable赋值给table
    table = newTable;
    //计算极限threshold的最新值
    threshold = (int)(newCapacity * loadFactor);
}

//将原Entry数组table中的所有键值对迁移到新Entry数组newTable上
void transfer(Entry[] newTable) {
    //原数组赋值给src
    Entry[] src = table;
    //新数组长度为newCapacity
    int newCapacity = newTable.length;
    //遍历原数组
    for (int j = 0; j < src.length; j++) {
        //获取原数组中的元素(键值对),赋值给e
        Entry<K,V> e = src[j];
        //若元素e不为null
        if (e != null) {
            //将当前元素设值为null
            src[j] = null;
            //遍历元素e所对应的bucket桶内的所有元素
            do {
                //获取下一个元素next
                Entry<K,V> next = e.next;
                //重新计算键值对e在新数组newTable中的bucketIndex位置(即rehash操作)
                int i = indexFor(e.hash, newCapacity);
                //这步操作,说实话,没看懂,有清楚的,请不吝赐教
                e.next = newTable[i];
                //将当前元素e放入新数组的i位置
                newTable[i] = e;
                //将下一个元素next赋值给当前元素,以便完成遍历
                e = next;
            } while (e != null);
        }
    }
}

 

下面我们看一下HashMap检索数据的操作:

//获取指定key所对应的value值
public V get(Object key) {
    //若key==null,则直接调用getForNullKey()方法
    if (key == null)
        return getForNullKey();
    //到这说明key != null,先获取key的hash值
    int hash = hash(key.hashCode());
    //在indexFor(int hash,int length)获取key落在Entry数组的哪个bucket桶上,获取该bucket桶上的元素e,进而遍历e的链表,找相对应的key,若找到则返回key所对应的value值,找不到则返回null
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        //若元素e.hash == 上面计算的hash值,并且(e.key 和入参key是同一个对象的引用,或者e.key和入参key equals相等),
        //则认为入参key和当前遍历的元素e的key是同一个,返回e的value值
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    //上面遍历了一遍也没有找到,则返回null
    return null;
}

//获取key为null的value值,由上面putForNullKey方法可知,key为null的键值对,被放在了Entry数组table的第一个bucket桶(table[0])
private V getForNullKey() {
    //获取Entry数组table的第一个元素e,从e开始往下遍历,若找到元素e.key 为null的,则直接返回该元素e.value值
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //找到元素e.key 为null的,则直接返回该元素e.value值
        if (e.key == null)
            return e.value;
    }
    //从table[0]开始,遍历链表一遍,没有找到key为null的,则返回null
    return null;
}

//获取指定key所对应的键值对Entry,先获取key的hash值,再获取该hash值应放入哪个hash桶,然后遍历该桶中的键值对,若有则返回该键值对;若没有则返回null
final Entry<K,V> getEntry(Object key) {
    //若key为null,则hash值为0;若key != null,则利用hash(int)计算key的hash值
    int hash = (key == null) ? 0 : hash(key.hashCode());
    //获取该hash值应放入哪个hash桶,并遍历该hash桶
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        //若元素e.hash == hash,并且(e.key == key,或者 key.equals(e.key)为true),则认为入参key和当前遍历的元素e.key是同一个,返回该元素e
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    //若没有则返回null
    return null;
}

 

//判断HashMap中是否含有指定key的键值对,内部用getEntry(Object key)来实现
public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

 

 

//将指定Map中的所有元素(键值对)拷贝到当前HashMap中,对于当前HashMap中存在的key,则进行value值的替换
public void putAll(Map<? extends K, ? extends V> m) {
    //若指定的Map中没有元素,则直接返回
    int numKeysToBeAdded = m.size();
    if (numKeysToBeAdded == 0)
        return;

    //若必要,则进行数组的扩容
    if (numKeysToBeAdded > threshold) {
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        //计算新的容量
        int newCapacity = table.length;
        while (newCapacity < targetCapacity)
            newCapacity <<= 1;
        //若新容量大于目前数组的长度,则调用resize(int)进行扩容
        if (newCapacity > table.length)
            resize(newCapacity);
    }
    //获取指定Map的迭代器,循环调用put(K k,V v)方法,进行键值对的插入
    for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
        Map.Entry<? extends K, ? extends V> e = i.next();
        put(e.getKey(), e.getValue());
    }
}

 

 

下面看下HashMap的remove操作:

/**
* 删除指定key所对应的元素   
*/
public V remove(Object key) {
    //调用方法reomveEntryForKey(Object key)来删除并获取指定的entry
    Entry<K,V> e = removeEntryForKey(key);
    //若entry为null,则返回null;否则返回entry的value值
    return (e == null ? null : e.value);
}

/**
*移除并返回指定key所关联的键值对entry,若HashMap中没有键值对和指定的key相关联,则返回null
*/
final Entry<K,V> removeEntryForKey(Object key) {
    //若key为null,则hash值为0;若key != null,则利用hash(int)计算key的hash值
    int hash = (key == null) ? 0 : hash(key.hashCode());
    //获取key应放入的在数组中的位置索引i
    int i = indexFor(hash, table.length);
    //标识前一个元素
    Entry<K,V> prev = table[i];
    //标识遍历过程中的当前元素
    Entry<K,V> e = prev;
    //遍历bucket桶table[i]中的元素,寻找对应的key
    while (e != null) {
        //当前元素的下一个元素
        Entry<K,V> next = e.next;
        Object k;
        //元素e.hash和上面计算的hash值相等,并且(key == e.key 或者key.equals(e.key) 为true),说明找到了指定key所对应的键值对
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            //由于删除了一个元素,修改了HashMap的结构,因此将modCount+1
            modCount++;
            //将size-1
            size--;
            //若待查找的元素为桶内的第一个元素,则当前元素的下一个元素next放入数组中位置i中
            if (prev == e)
                table[i] = next;
            //否则将上一个元素的next属性指向 当前元素的next
            else
                prev.next = next;
            //当元素被remove时,调用Entry对象的recordRemove(Map<K,V> m)方法
            e.recordRemoval(this);
            //返回找到的当前元素
            return e;
        }
        //程序走到这,说明当前元素不是要查找的元素;则将当前元素赋值给上一个元素,将下一个元素赋值给当前元素,以完成遍历
        prev = e;
        e = next;
    }

    return e;
}

 

 

//判断HashMap中是否包含指定的对象value
public boolean containsValue(Object value) {
    //若value为null,则调用containsNullValue()方法处理
    if (value == null)
        return containsNullValue();
    //将数组table赋值给tab
    Entry[] tab = table;
    //遍历数组tab的每个索引位置(此层循环对应数组结构)
    for (int i = 0; i < tab.length ; i++)
        //对应指定的索引位置i,遍历在索引位置i上的元素(此层循环对应链表结构)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            //若某个元素e.value和指定的value equals相等,则返回true
            if (value.equals(e.value))
                return true;
    //遍历完成没有找到对应的value值,返回false
    return false;
}

//判断HashMap是否包含value为null的元素
private boolean containsNullValue() {
    //将数组table赋值给tab
    Entry[] tab = table;
    //遍历数组tab的每个索引位置(此层循环对应数组结构)
    for (int i = 0; i < tab.length ; i++)
        //对应指定的索引位置i,遍历在索引位置i上的元素(此层循环对应链表结构)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            //若某个元素e.value == null,则返回true
            if (e.value == null)
                return true;
    //没有找到value值为null的,返回false
    return false;
}

 

//清除HashMap中所有的键值对,此操作过后,HashMap就是空的了
public void clear() {
    //要删除所有的元素,肯定会对HashMap的结构造成改变,因此modCount+1
    modCount++;
    Entry[] tab = table;
    //遍历数组,将数组中每个索引位置的设置为null
    for (int i = 0; i < tab.length; i++)
        tab[i] = null;
    //将size 修改为0
    size = 0;
}

 

 

现在看一下上面没有讲的一个构造函数:

//构造一个新的HashMap,以承载指定Map中所有的键值对,使用默认的加载因子DEFAULT_LOAD_FACTOR
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    //调用putAllForCreate(Map<? extends K, ? extends V>)方法完成元素的迁移
    putAllForCreate(m);
}

private void putAllForCreate(Map<? extends K, ? extends V> m) {
    for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
        Map.Entry<? extends K, ? extends V> e = i.next();
        //在迭代器循环中调用putForCreate(K k,V v)来实现元素的创建
        putForCreate(e.getKey(), e.getValue());
    }
}

//该方法和put方法不同,它不会进行数组的扩容resize,和对modCount的检查
private void putForCreate(K key, V value) {
    //若key为null,则hash值为0;若key != null,则利用hash(int)计算key的hash值
    int hash = (key == null) ? 0 : hash(key.hashCode());
    //求key应该放入哪个hash桶(bucket)内
    int i = indexFor(hash, table.length);
    //遍历链表,若key之前在Map中已经有了,则直接返回
    for (Entry<K,V> e = 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;
        }
    }
    //调用createEntry(int hash,K k,V v,int bucketIndex)方法完成键值对的创建并加入到链表中
    createEntry(hash, key, value, i);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    //将bucketIndex位置的元素取出来
    Entry<K,V> e = table[bucketIndex];
    //创建一个新的键值对,使用给定的hash、key、value,并将新键值对next指向e,最后将新键值对放在bucketIndex处
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //将数组大小size + 1
    size++;
}

 

  下面我们讲下HashMap的负载因子loadfactor, 所谓负载因子就是散列表的实际元素数目(n)/散列表的容量(m), 它衡量的是一个散列表的空间的使用程度,默认情况下loadfactor是0.75,它的作用是当HashMap中元素的个数size 大于(HashMap的容量capacity * 负载因子loadfactor)时,该HashMap便会进行扩容resize。

  我们先说下hash冲突:

  当利用HashMap存数据的时候,先根据key的hashcode值来计算key的hash值(利用hash函数),再根据hash值来计算该key在数组table中的位置index(hash & (length-1)),比如我们要存两个键值对key1-value1和key2-value2,

如果key1、key2分别通过hash函数计算的hash值hash1、hash值hash2 相等,那key1和key2一定会落在数组table的同一个位置上,这就产生了冲突,这个冲突是由不同的key值但是却相同的hash值引起的,称之为hash冲突。HashMap解决hash冲突的方式就是链表,虽然key1-value1和key2-value2这两个键值对落在了数组table的同一个位置上,但是它们是链表的方式连接在一起,当HashMap查找key1时,就需要遍历这个链表了。

当负载因子越大的时候,出现hash冲突的可能性越大,这意味着数组table中某个具体的桶bucket上不止有一个元素(此时就构成了链表了)可能性增大,在检索数据的时候需要遍历链表的可能性增大,因此检索的效率就比较低(耗时长),但是空间的利用率越高。

当负载因子越小的时候,出现hash冲突的可能性越小,这意味着数组table中某个具体的桶bucket上不止有一个元素(此时就构成了链表了)可能性减小了,在检索数据的数据需要遍历链表的可能性减小,因此检索的效率就比较高,但是空间利用率越低。

  上面的源码解析了提到了HashMap的容量一定得是2的整数此幂(2^n),这又是问什么呢?

  通过上面的源码我们知道:根据hash值求该hash值在数组中的位置的实现是: hash & (length-1),当数组table的长度length为2的整数次幂的时候,那(length-1)二进制表示形式从低位开始一定都是1,直到为0,如果length依次为2,4,8,16,32,64,则(length-1)一次为1,3,7,15,31,63,那(length-1)的二进制形式依次为1,11,111,1111,11111,我们知道二进制的与运算&,当一方位数全是1的时候,进行&运算的结果完全取决于另外一方。

比如从0开始到15,依次和15进行&运算,看看结果的平均分布情况:

操作数0-15 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
15的二进制 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
进行位与&操作结果 0000 0001 0010  0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

通过位与&操作后,发现0-15完全平均的落在了数组的各个索引位置

 下面通过一个小例子予以验证:

public class HashDemo {


    private final int[] table;

    public HashDemo(int size) {
        this.table = new int[size];
        for (int i = 0; i < size; i++) {
            table[i] = i;
        }
    }

    //求key所对应的在数组中的位置
    public int index(int key){
        //求hash值
        int hash = hash(key);
        //返回key所对应的在数组中的位置
        return hash & (table.length-1);
    }


    //HashMap中hash函数的实现,求hash值
    public int hash(int h){
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }


    public static void main(String[] args) {
        Map<String,Integer> keyToNumber = new HashMap<String, Integer>();
        int size = 16;
        HashDemo hashDemo = new HashDemo(size);
        int testSize = 1000;
        for (int i = 0; i < testSize; i++) {
            int index = hashDemo.index(i);
            Integer number = keyToNumber.get("key" + index);
            if (number == null) {
                keyToNumber.put("key"+index,1);
            }else {
                keyToNumber.put("key"+index,keyToNumber.get("key"+index)+1);
            }
        }
        Iterator<Map.Entry<String, Integer>> it = keyToNumber.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> entry = it.next();
            System.out.println(entry.getKey() + "   == "+entry.getValue());
        }
    }

}

当我们将size设置为16 (2的4次幂)时,控制台输出:

key4   == 62
key3   == 62
key6   == 62
key5   == 62
key0   == 62
key2   == 62
key1   == 62
key10   == 63
key11   == 63
key8   == 63
key7   == 62
key9   == 63
key15   == 63
key14   == 63
key13   == 63
key12   == 63

 由上面的输出可见,数据非常平均的分配在了数组的16个索引位置,

当size设置为非2的整数次幂的时候,比如50,这时控制台输出:

key0   == 120
key17   == 124
key16   == 124
key1   == 120
key49   == 128
key48   == 128
key32   == 128
key33   == 128

由此可见1000个数据只分配在了8个索引位置上。

 

使用HashMap的注意事项:

  1.HashMap采用数组+链表的形式存储数据,当预先知道要存储在HashMap中数据量的大小时,可以使用new HashMap(int size)来指定其容量大小,避免HashMap数组扩容导致的元素复制和rehash操作带来的性能损耗。

  2.HashMap是基于Hash表、实现了Map接口的,查找元素的时候,先根据key计算器hash值,进而求得key在数组中的位置,但是要尽量避免hash冲突造成的要遍历链表操作,因此在我们手动指定HashMap容量的时候,容量capacity一定得是2的整数次幂,这样可以让数据平均的分配在数组中,减小hash冲突,提高性能。

   3.HashMap是非线程安全的,在多线程条件下不要使用HashMap,可以使用ConcurrentHashMap代替。

 

 

 

 

 

 

 

 

 

 

源码解析,hashmap源码解析 HashMap简介: HashMap在日常的开发中应用的非常之广泛,它是基于Hash表,实现了Map接口,以键值对(key-value...

01、Hash

对于HashMap来说,难理解的不在于Map,而在于Hash。

Hash,一般译作“散列”,也有直接音译为“哈希”的,这玩意什么意思呢?就是把任意长度的数据通过一种算法映射到固定长度的域上。

再直观一点,就是对一串数据wang进行杂糅,输出另外一段固定长度的数据er——作为数据wang的特征。我们通常用一串指纹来映射某一个人,别小瞧手指头那么大点的指纹,在你所处的范围内很难找出第二个和你相同的(人的散列算法也好厉害,有没有?)。

对于任意两个不同的数据块,其散列值相同的可能性极小,也就是说,对于一个给定的数据块,找到和它散列值相同的数据块极为困难。再者,对于一个数据块,哪怕只改动它的一个比特位,其散列值的改动也会非常的大——这正是Hash存在的价值!

在Java中,String字符串的散列值计算方法如下:

publicinthashCode(){
inth=hash;
if(h==0&&value.length>0){
charval[]=value;

for(inti=0;i<value.length;i++){
h=31*h+val[i];
}
hash=h;
}
returnh;
}

看得懂看不懂都没关系,我们就当是一个“乘加迭代运算”的算法。借此机会,我们来看一下“沉”、“默”、“王”、“二”四个字符串的散列值是多少。

String[]cmower={"沉","默","王","二"};
for(Strings:cmower){
System.out.println(s.hashCode;
}

输出的结果如下:

沉的散列值:27785
默的散列值:40664
王的散列值:29579
二的散列值:20108

对于HashMap来说,Hash存在的目的是为了加速键值对的查找(你想,如果电话薄不是按照人名的首字母排列的话,找一个人该多困难「我的微信好友有不少在昵称前加了A,好狠」)。通常情况下,我们习惯使用String字符串来作为Map的键,请看以下代码:

Map<String,String>map=newHashMap<>();
String[]cmower={"沉","默","王","二"};
for(Strings:cmower){
map.put(s,s+"月入25万");
}

那HashMap会真的会将String字符串作为实际的键吗?我们来看HashMap的put方法源码:

publicVput(Kkey,Vvalue){
returnputVal,key,value,false,true);
}

虽然只有一个putVal()方法的调用,但是你应该已经发现,HashMap内部会把key进行一个hash运算,具体代码如下:

staticfinalinthash(Objectkey){
inth;
return(key==null)?0:(h=key.hashCode^(h>>>16);
}

假如key是String字符串的话,hash()会先获取字符串的hashCode,再对散列值进行位于运算,最终的值为HashMap实际的键。

既然HashMap在put的时候使用键的散列值作为实际的键,那么在根据键获取值的时候,自然也要先对get方法的key进行hash运算,请看以下代码:

publicVget(Objectkey){
Node<K,V>e;
return(e=getNode,key))==null?null:e.value;
}

参考

http://www.cnblogs.com/xwdreamer/archive/2012/06/03/2532832.html
JDK API:HashMap

03、初始容量和负载因子

HashMap的构造方法主要有三种:

publicHashMap(intinitialCapacity,floatloadFactor){
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}


publicHashMap(intinitialCapacity){
this(initialCapacity,DEFAULT_LOAD_FACTOR);
}


publicHashMap(){
this.loadFactor=DEFAULT_LOAD_FACTOR;
}

其中initialCapacity为初始容量(默认为1 << 4 = 16),loadFactor为负载因子。初始容量是HashMap在创建时的容量(HashMap中桶的数量);负载因子是HashMap在其容量自动增加之前可以达到多满的一种尺度。

当HashMap中的条目数超出了负载因子与当前容量的乘积时,则要对HashMap扩容,增加大约两倍的桶数。

通常,默认的负载因子 是时间和空间成本上的一种折衷。负载因子过高虽然减少了空间开销,但同时增加了查询成本。如果负载因子过小,则初始容量要增大,否则会导致频繁的扩容。

在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少扩容的操作次数。

如果能够提前预知要存取的键值对数量的话,可以考虑设置合适的初始容量(大于“预估元素数量 / 负载因子”,并且是2的幂数)。

HashMap读取数据过程

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

有了上面的基础,这段代码很容易理解。

在平常的开发当中,HashMap是我最常用的Map类,它支持null键和null值,是绝大部分利用键值对存取场景的首选。需要切记的一点是——HashMap不是线程安全的数据结构,所以不要在多线程场景中应用它。

HashMap结构

HashMap的存储容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap做了一些处理。

首先,HashMap里面实现一个静态内部类Entry:

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

        ... ...
    }

重要的属性有key,value,next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础,而next则是用于链表链接的。我们说HashMap就是由一个线性数组实现,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。由于每一个Entry内部都有指向下一个Entry的引用(next),所以这个数组中的每个元素,实际上是一个链表的头部。

    /**
     * An empty table instance to share when the table is not inflated.
     */
    static final Entry<?,?>[] EMPTY_TABLE = {};

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

图片 2

Hash算法

Hash,一般翻译做“散列”,也直接音译为“哈希”。就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(Hash值)
这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

02、散列值冲突怎么解决

尽管散列值很难重复,我们还是要明白,这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出。

也就是说,key1 ≠ key2,但function有可能等于function——散列值冲突了。怎么办?

最容易想到的解决办法就是:当关键字key2的散列值value与key1的散列值value出现冲突时,以value为基础,产生另一个散列值value1,如果value1与value不再冲突,则将value1作为key2的散列值。

依照这个办法,总会找到不冲突的那个。

Hash表

数组的特点是:寻址容易,插入和删除困难;
链表的特点是:寻址困难,插入和删除容易。
那么综合两者的优势,得到一种寻址容易,插入删除也容易的数据结构,这就是哈希表。哈希表有多种不同的实现方法,这里说的是最常用的一种方法:拉链法,我们可以理解为“链表的数组”,如图(来自于网络):

index = hash % 16;

图中的Hash算法即是:index = hash % 16;。说明:本图的结构与HashMap十分相似,HashMap中存储的是键值对,而本图的数值相当于HashMap的键。

前方涉及很多源码,注意保护眼睛!

通常情况下,我们使用Map的主要目的是用来放入、访问或者删除,而对顺序没有特别的要求——HashMap在这种情况下就是最好的选择。

HashMap的Hash值映射

在使用HashMap时,我们希望这个HashMap里面的元素位置尽量的分布均匀些,最好使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表,这样就大大优化了查询的效率。

最普遍的想法是把hash值对数组长度进行取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中是这样做的:调用indexFor(int h, int length)方法来计算该对象应该保存在table数组的哪个索引处。

方法的代码如下:

static int indexFor(int h, int length) {
    return h & (length-1);
}

这个方法很巧妙,它通过h & (table.length -1)来得到该对象的保存位置,而HashMap底层数组的length总是 2 的n次方(length-1为2^n-1,全一),这是HashMap在速度上的优化。

而这个又会带了一个问题就是hash值往往很长(很可能比length长得多),这样会导致即使hash值不同,但hash值的低位相同,与length-1进行&操作后的值仍然相同,虽然不影响使用,但会降低效率。

这里HashMap使用了一种技巧来计算hash值:

    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

这里使用了hash算法重新计算了hash值,而不是直接使用的hashCode方法。

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);

此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突。

HashMap构造

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashMap(int initialCapacity, float loadFactor) {
        ... ...
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        ... ...
    }

通过源码的注释可以看出:

  1. HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
  2. HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。
  3. HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
  4. HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和负载因子loadFactor。
  5. initialCapacity:HashMap的最大容量,即为底层数组的长度。
  6. loadFactor:负载因子loadFactor定义为:散列表的实际元素数目(n)/ 散列表的容量(m)。

HashMap的resize过程

当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize

在数据存储过程中,调用addEntry时,需要先处理resize(调整大小)的过程:

        if ((size >= threshold) && (null != table[bucketIndex])) {
            // threshold = (int)(capacity * loadFactor);
            resize(2 * table.length);
            ... ...
        }

在这里需要指出:
负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。如果负载因子越大,对空间的利用越充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。

这里是resize的过程,就不赘述了:

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

transfer函数中进行了对hash值的重新计算。

在addEntry函数中可以看出,resize时是*2的(大小变为原来的2倍)。那么,我们会有个疑问:为什么是扩大为原来的2倍呢?

看一看上面定义Entry[] table时,有这样一个注释:
The table, resized as necessary. Length MUST Always be a power of two.
长度必须为2的倍数。那么我们又会有疑问,为什么长度一定要是2的幂呢?这就涉及到HashMap的映射算法了。

版权声明:本文由大奖888-www.88pt88.com-大奖888官网登录发布于大奖888官网登录,转载请注明出处:本图的结构与HashMap拾分相似,所以不用在多线程