Java HashMap深度剖析

一、首先再简单重复一下Hash算法
简单的说就是一种将任意内容的输入转换成相同长度输出(有个范围,假设10位的数字,用一个称之为HashTable的容器来存放)的加密方式------hash
如(假设):
“a”---10位数1
123---10位数2

注意:任意内容的输入,范围是无穷无尽,肯定比相同长度输出(如10位数)要大很多,那么就会造成不同的输入,会得到相同的输出(值)----hash冲突
HashMap当然也无法避免冲突问题

二、HashMap源码片段
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;//负载因子,默认0.75
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
//使用的是Entry数组
        init();
}

public V put(K key, V value) {
        if (key == null)//空的情况,允许存空
            return putForNullKey(value);
        int hash = hash(key.hashCode());//根据key的hashCode再来计算一个hash值----根据hash冲突可以知道不同的key对应的hashCode可能一样(如果不被重写的话,Object的hashCode()生成的hashCode存放在Java底层的一个大的HashTable上,不过我想JDK应该已经做过冲突处理,不会使用这么简单的hash算法,除非自己重写hashCode(),否则应该不会有冲突,真的发生冲突估计要内存溢出了)
//就算hashCode不同,通过hash()出来的hash值也可能冲突(后面会讲到)

        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))) {//该位置已经有了,且key也完全是同一个,就覆盖,否则也是走下面的新开(后面会有例子)
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }//已经存在的情况
//以下是新增的情况
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

/**
为给定的hashCode增加一个hash方法,用于抵消低质量的hash函数。这是很关键的,因为HashMap使用power-of-two长度的hash表,否则遇到冲突的hashCode无法区分    
     */

    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);
    }

//根据hashCode及table的长度计算index
static int indexFor(int h, int length) {
        return h & (length-1);
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];//先取原有的元素作为next,index冲突的时候用,形成一个“链条”
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存放自己的下一个
        final int hash;
...
}

//------再看一下get方法
public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
//根据key的hashCode计算出“链条”在table中的index,再到“链条”中查找符合自己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;
  }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wyzxwj.html