Java之HashMap解析

HashMap可能是我们使用最多的键值对型的集合类了，它的底层基于哈希表，采用数组存储数据，使用链表来解决哈希碰撞。

HashMap特点

• HashMap是基于哈希表的Map接口实现。
• HashMap底层采用的是Entry数组和链表实现。
• HashMap是采用key-value形式存储，其中key是可以允许为null但是只能是一个，并且key不允许重复(如果重复则新值覆盖旧值)。
• HashMap是线程不安全的。
• HashMap存入的顺序和遍历的顺序有可能是不一致的。
• HashMap保存数据的时候通过计算key的hash值来去决定存储的位置。

HashMap源码解析

MyHashMap.java

import java.util.Map;
import java.util.Objects;

public class MyHashMap {

    // 初始默认的数组容量
    static final int INIT_CAPACITY = 1<<4;
    //数组最大的容量,因为 数组设置为 2的整次方倍，而 31 次方为负数，所以最大只能为 1 << 30
    static final int MAX_CAPACITY = 1<<30;
    // 默认的装填因子
    static final float DEFAULT_LOADFACTOR = 0.75f;


    /**
     * Entry 类 为map中基本的单元
     *
     * key 为键，value 为值
     * next 是在哈希冲突时，指向的下一个 Entry
     * h 为传入的hash值
     */
    static class Entry{
        Object key;
        private Object value;
        private Entry next;
        int h;

        public Entry(int h,Object key, Object value, Entry next) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.h = h;
        }

        public Entry() {

        }

        public Object getKey() {
            return key;
        }


        public Object getValue() {
            return value;
        }

        public Object setValue(Object newValue) {
            Object oldValue=value;
            this.value = newValue;
            return oldValue;

        }

        public Entry getNext() {
            return next;
        }

        public void setNext(Entry next) {
            this.next = next;
        }

        public  final int hashcode(){
            return Objects.hashCode(key)^Objects.hashCode(value);
        }

    }


    // 返回 hash值 ，如果 key 为 null，返回 0
    // 重新计算的哈希值为  原来的hashCode 和 高八位进行相与，
    // 这样做的好处： 如果不这样，当数组较短的时候，只能有低位进行运算，高位无效，分布不均

    static final int hash(Object key){
        int h;
        return (key==null) ? 0 : (h=key.hashCode())^(h >>> 16);
    }


    // 数组长度，通过这个运算得到
    // 扩容后的大小总是 2的 n 次方倍，且是离未扩容前的数字最近的那个 2的n次方
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAX_CAPACITY) ? MAX_CAPACITY : n + 1;
    }



    Entry[] table;

    // table 桶中的个数--数组的大小;
    int size;


    // 修改次数
    int modCount;

    // 扩容的阈值, capacity * load factor
    int threshold;

    // 装填因子
    float loadFactor;

    public MyHashMap(int initCapacity,float loadFactor) {
        if(initCapacity<0)
            throw new IllegalArgumentException("初始化容量失败: "+
                                                    initCapacity);
        if(initCapacity>= MAX_CAPACITY)
            initCapacity= MAX_CAPACITY;
        if(loadFactor<=0||Float.isNaN(loadFactor))
            throw new IllegalArgumentException("装填因子不合法"+
                                                    loadFactor);
        this.loadFactor=loadFactor;
        this.threshold=tableSizeFor(initCapacity);

    }

    /**
     * 只传入数组容量大小的
     * @param initCapacity
     */
    public MyHashMap(int initCapacity) {
        this(initCapacity,DEFAULT_LOADFACTOR);
    }

    /**
     * 无参的，全部默认
     */
    public MyHashMap() {
        this.loadFactor=DEFAULT_LOADFACTOR;
    }


    public MyHashMap(Map m){
        this.loadFactor=DEFAULT_LOADFACTOR;

    }

    /**
     * 当key是Map的时候才调用
     * @param m
     * @param evict
     */

    final void putEntries(Map m,boolean evict){
        int s=m.size();
        if(s>0){
            if(table==null){
                float ft=(float) s/loadFactor+1.0f;

                int t=(ft<(float) MAX_CAPACITY)?(int)ft: MAX_CAPACITY;

                // 如果 原来的 hashmap的 table 的大小为0（第一次添加数字）；
                // 那么就将他按照现在的 添加的table 大小进行扩容
                if(t>threshold){
                    threshold=tableSizeFor(t);
                }


            }
            // 如果添加的 entries 的 table 大小大于 阈值，就扩容
            else if(s>threshold){
                resize();
            }

            // 把各个 Entry 放入到 map中
            for( Object e :  m.entrySet()){

                Object key = ((Map.Entry) e).getKey();
                Object value = ((Map.Entry) e).getValue();
                putVal(hash(key),key,value,false,evict);
            }
        }
    }


    /**
     * 存放单个元素时调用
     */

    public Object put(Object key,Object value){
        return putVal(hash(key),key,value,false,true);
    }

    /**
     * 存放单个元素的操作
     * @param hash 哈希值，由key的高16位和低16位异或得到
     * @param key 键
     * @param value 值
     * @param onlyIfAbsent
     * @param evict
     * @return
     */
    private Object putVal(int hash, Object key, Object value, boolean onlyIfAbsent, boolean evict) {
            Entry[] tab;
            Entry p;
        int n,i;
        // 如果第一次 进行存放数据，进行初始化，table 被延迟到进行数据存放时才初始化
        if((tab = table) == null || (n = table.length)==0){
            n = (tab = resize()).length;
        }
        // 如果table 索引上没有存放元素
        if((p = table[i = ((n - 1) & hash)]) == null){
            tab[i] = newEntry(hash,key,value,null);
        }

        else {
            Entry e;
            Object k;
            // 如果 key 相同，那么就直接将 value 覆盖
            // 为什么要比较这么多次

            // 1.首先判断 哈希值是否相同
            if(p.h == hash &&
                    // 2.判断两个key是否相等，使用 '==' 是非字符串情况，之比较两个的内容，使用'equals' 是针对字符串
                    (((k = p.key) == key) || (key != null && key.equals(k))))
                // 覆盖value值
                e = p;

            // 这个是树的情况
            //else if(p instance of TreeNode)

            // 链
            else{
                for(int binCount=0;;++binCount){
                    // 遍历到最后，插入
                    if((e = p.next) == null){
                        p.next = newEntry(hash,key,value,null);

                        /*
                          如果 binCount > 转化树的阈值 ,则将链表转化为树
                        if(binCount >= TREEIFY_THRESHOLD-1)
                            treeifyBin(tab,hash);
                        */
                        break;
                    }
                    if(p.h == hash &&
                            (((k = p.key) == key) || (key != null && key.equals(k))))
                        break;
                    // 移动到下一个
                    p = e;
                }

                // 如果有相应的映射
                if(e != null){
                     Object oldValue = e.value;
                     if(!onlyIfAbsent || oldValue == null)
                         e.value = value;
                     return oldValue;
                }

            }

        }
        // 修改次数 ++
        ++ modCount;

        // 大于阈值就扩容
        if(++size >threshold)
            resize();

        // 插入元素
        //afterNodeInsertion(evict);

        return null;

    }

    public Object get(Object key){
        Entry e;

        return (e = getNode(hash(key),key)) == null ? null : e.value;

    }

    /**
     * 查找键值对
     * @param hash
     * @param key
     * @return 查找的元素或者 null
     */

    private Entry getNode(int hash, Object key) {
        Entry[] tab;
        Entry first,e;
        int n;
        Object k;

        if((tab=table) != null && (n=tab.length) >0 &&
                (first = tab[(n-1) & hash]) !=null){

            // 检查链表中的第一个
            if (first.h == hash &&
                    (((k = first.key) == key ) || (key !=null && key.equals(k)))){
                return first;
            }
            if ((e = first.next) != null){
                // 判断是否为树形结构
                // if (e instanceof TreeNode)
                // 然后调用 TreeNode的搜索方法

                //这个是在链表中查找元素
                do{
                    if (e.h == hash &&
                            (((k = e.key) == key) || (key !=null && key.equals(k))))
                        return e;
                }while ((e = e.next) != null);
            }

        }

        return null;
    }


    /**
     * map中是否有这个 键
     * @param key
     * @return false or true
     */
    public boolean containsKey(Object key){
        return getNode(hash(key),key) != null;
    }
    private Entry newEntry(int hash, Object key, Object value, Entry entry) {
        return new Entry(hash,key,value,entry);
    }

    /**
     * 扩容函数
     *   使用情景: 1.初始化数组table，
     *           2.++size>threshold.
     * @return 新的数组table
     *         或者是扩容一倍长度超过最大值，返回原来的table数组
     */
    final  Entry[] resize() {
        // 定义旧的数组为 Entry 类型的数组，oldTab
        Entry[] oldTab = table;
        // 如果oldTab==null  则返回 0，否则返回数组大小
        int oldCap = (oldTab==null) ? 0 : oldTab.length;

        int oldThreshold = threshold;

        int newCap,newThreshold=0;

        // 说明已经不是第一次 扩容，那么已经初始化过，容量一定是 2的n次方，所以可以直接位运算
        if(oldCap>0){
            // 如果 原来的数组大小已经大于等于了最大值，那么阈值设置为 Integer的最大值,即不会再进行扩容
            if(oldCap >= MAX_CAPACITY){
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }

            // 因此已经不是第一次扩容，一定是2的n次方
            else if ((newCap = oldCap << 1) < MAX_CAPACITY &&
                      oldCap >= INIT_CAPACITY)

                newThreshold = oldThreshold << 1;

        }
        // 如果oldThreshold > 0,并且oldCap == 0，说明是还没有进行调用resize方法。
        // 说明输入了初始值，且oldThreshold为 比输入值大的最小的2的n次方
        // 那么就把 oldThreshold 的值赋给 newCap ，因为这个值现在为 比输入值大的最小的2的n次方
        else if(oldThreshold>0)
            newCap = oldThreshold;

        // 这个是只有使用无参构造器的时候才能满足的条件。，全部是否默认的值
        else{
            newCap = INIT_CAPACITY;
            newThreshold = (int) (INIT_CAPACITY * DEFAULT_LOADFACTOR);
        }

        //
        if(newThreshold == 0){

            float ft = (float) (newCap * loadFactor);
            newThreshold =(newCap < MAX_CAPACITY && ft < (float) MAX_CAPACITY ?
                    (int )ft : Integer.MAX_VALUE);
        }

        threshold = newThreshold;

        Entry newTable[] = new Entry[newCap];
        table=newTable;

        // 将原来数组中的所有元素都 copy进新的数组
        if(oldTab != null){
            for (int j = 0; j < oldCap; j++) {
                Entry e;

                if((e = oldTab[j]) != null){
                    oldTab[j] = null;

                    // 说明还没有成链，数组上只有一个
                    if(e.next == null){
                        // 重新计算 数组索引 值
                        newTable[e.h & (newCap-1)] = e;

                    }
                    // 判断是否为树结构
                    //else if (e instanceof TreeNode)


                    // 如果不是树，只是链表,即长度还没有大于 8 进化成树
                    else{
                        // 扩容后，如果元素的 index 还是原来的。就使用这个lo前缀的
                        Entry loHead=null, loTail =null;

                        // 扩容后  元素index改变，那么就使用 hi前缀开头的
                        Entry hiHead = null, hiTail = null;
                        Entry next;
                        do {
                            next = e.next;
                            //这个非常重要，也比较难懂，
                            // 将它和原来的长度进行相与，就是判断他的原来的hash的上一个	bit 位是否为 1。
                            //以此来判断他是在相同的索引还是table长度加上原来的索引
                            if((e.h & oldCap) == 0){
                                // 如果 loTail == null ,说明这个 位置上是第一次添加，没有哈希冲突
                                if(loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else{
                                if(hiTail == null)
                                    loHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e ;
                            }

                        }while ((e = next) != null);


                        if(loTail != null){
                            loTail.next = null;
                            newTable[j] = loHead;
                        }

                        // 新的index 等于原来的 index+oldCap
                        else {

                            hiTail.next = null;
                            newTable[j+oldCap] = hiHead;
                        }

                    }
                }

            }
        }

        return newTable;
    }

}