JAVA进阶篇——一行代码一行代码嚼烂之超详细注解手写HashMap（二）

HashMap用得顺手吧？不知道让你手写一个HashMap你能不能写出来呢，今天为大家带来的是手写HashMap，一行代码一行代码地嚼一下，看完这个再去看HashMap的源码，帮助你深度理解HashMap的原理。

这里还是很推荐大家去看一下HashMap的源码的，因为所涉及的知识面很广泛，可谓是受益匪浅。话不多说，咱们开始看。

在此之前，推荐大家先去看完这一篇博客JAVA进阶篇——HashMap底层实现解析（一），这篇博客是基于手动写HashMap代码的底层理论，会更加帮助你加深理解。在JDK1.8中是使用数组+尾插链表+树(红黑树)组成的，以下代码是JDK1.7中的数组+头插链表的结构所实现的HashMap。秊

当熟悉以后可在此基础上优化为JDK1.8的HashMap。

package com.gantiexia.hashmap;


public class Entry {
    
    int hash;
    
    K key;
    
    V value;
    
    Entry next;

    
    public Entry(){}
    public Entry(K key, V value){
        this.key = key;
        this.value = value;
    }
    public Entry(int hash, K key, V value, Entry next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    
    public K getKey() {
        return key;
    }
    public void setKey(K key) {
        this.key = key;
    }
    public V getValue() {
        return value;
    }
    public void setValue(V value) {
        this.value = value;
    }
}

这里只实现了HashMap的 put / get / size / 扩容 方法：

package com.gantiexia.hashmap;


public class HashMap {
    
    static final int INITIAL_CAPACITY = 4;
    
    float LOAD_FACTOR = 0.75f;
    
    int COUNT = 0;

    Entry[] table;

    public K put(K key, V value) {

        Entry newEntry = new Entry(key, value);

        // 这里我们没有写可以手动输入初始值的方法，所以直接设置默认容量
        if (table == null) {
            table = new Entry[INITIAL_CAPACITY];
        }

        // 数组下标位置
        int hash = hash(key);

        // 链表模型,如果Hash值相等,则形成链表
        // head代表链表头，此处用的头插法
        Entry head = table[hash];
        
        // 当容量达到初始容量的加载因子时扩容
        if(COUNT > table.length * LOAD_FACTOR){
            resize();
        }

        // 注意数组+链表的概念模型将会再这里产生

        // 如果table[hash]这个位置没有元素，直接赋值
        if (head == null) {
            table[hash] = newEntry;
            COUNT++;
            return key;
        } else {
            // 如果table[hash]这个位置有元素
            Entry tail = new Entry();
            // 如果这个元素的next指针为空，设置指针指向新的键值
            if (head.next == null) {
                head.next = newEntry;
            } else {
                // 如果指针next不为空，找到指针为空的链表上的那一个元素，插入
                do {
                    tail = head;
                } while ( (head = head.next) != null );
                // 该链表上此对象的指针指向新的对象
                tail.next = newEntry;
            }
            COUNT++;
            return key;
        }
    }

到这里中途打断一下，为了更深度地帮助各位理解HashMap数组+链表的结构，这里我画了一张图帮助理解：

继续：

    
    public int resize() {
        // 扩容, << 2 代表 4倍 扩容
        int newCapacity = INITIAL_CAPACITY << 2;
        // 新建一个数组
        Entry[] newTable = new Entry[newCapacity];
        // 数组的copy方法
        System.arraycopy(table, 0, newTable, 0, table.length);
        // 新数组赋值给老数组
        this.table = newTable;
        // 返回新容量
        return newCapacity;
    }

    
    public V get(K key) {
        Entry entry;
        // 二元表达式通过getEntry()方法寻找键值
        return (entry = getEntry(hash(key), key)) == null ? null : entry.value;
    }

    
    public Entry getEntry(int hash, K key) {
        // 新建对象做逻辑判断
        Entry entry = table[hash];
        // 如果 table[hash] 为空,证明不存在此 key 的键值
        if (entry == null) {
            return null;
        } else if (entry != null && entry.next == null) {
            // 如果此元素不为空,并且此元素的next指针为空，证明此链表上只有一个元素，直接返回
            return entry;
        } else if (entry.next != null) {
            // 如果此对象的 next 指针不为空，就要在此链表上去找到 hash 值相等的数据
            do {
                // 如果此元素的hash与该对象的key值的hash相等
                // 并且
                // key相等 或者 key不为空并且key相等
                if (hash == hash(entry.key) && (key == entry.key || (key != null && key.equals(entry.key)))) {
                    // 返回此链表上的对象
                    return entry;
                }
                // 条件是此对象的指针 next 不为空
            } while ( (entry = entry.next) != null );

            // 如果通过以上循环没有找到对象的对像的话，返回空
            return null;
        }
        return null;
    }

    
    public final int hash(K key) {
        // &运算：4 & 5
        // 转化为二进制： 100 & 101 = 100 （同时为1才为1，否则为0）
        // 十进制：4
        // 所以： 4 & 5 = 4
        //
        // 0x7FFFFFFF代表int的最大值
        //
        // 此操作主要是为了取得正整数
        //
        // 后面 %运算 是为了使得返回值数组下标不会越界,即返回值小于数组或者扩容后数组的大小
        return (key == null) ? 0 : ( key.hashCode() & 0x7FFFFFFF % table.length);
    }

    
    public int size(){
        return COUNT;
    }
}

package com.gantiexia.hashmap;


public class TestMyHashMap {
    public static void main(String[] args) {
        HashMap map = new HashMap<>();

        map.put("GanTieXia","肝铁侠");
        map.put("ZhuZhuXia","猪猪侠");
        map.put("ShanDianXia","闪电侠");

        System.out.println("{GanTieXia" + ":" + map.get("GanTieXia")+"}");
        System.out.println("{ZhuZhuXia" + ":" + map.get("ZhuZhuXia")+"}");
        System.out.println("{ShanDianXia" + ":" + map.get("ShanDianXia")+"}");

        System.out.println("-----------------------");

        System.out.println("map集合的大小:" + map.size());
    }
}

运行结果✔：

到这里手写的1.7版本JDK版本的手写HashMap就完成了，相信会手写以后的你再返回去看HashMap的源码的时候，会更加条理清晰。