引言

上一篇博客学习了HashMap的源码，了解了hash函数设计原理和基本的增删改查及扩容实现，今天我们依葫芦画瓢，基于数组和单链表尝试手写简单的HashMap,实现它的put\get\remove\resize操作。

Map接口

包含了基本的操作:put\get\remove\size方法:

package hash;

/**
 * Created by chenming on 2018/6/10
 * 基本的map接口
 */
public interface Map<K, V> {
    /**
     * 大小
     * @return
     */
    int size();

    /**
     * 添加元素
     * @param key
     * @param object
     */
    void put(K key, V object);

    /**
     * 查找元素
     * @param key
     * @return
     */
    V get(K key);

    /**
     * 删除元素
     * @param key
     * @return
     */
    V remove(K key);
}

节点Node定义

节点为单链表节点,思路和JDK一样

package hash;

/**
 * Created by chenming on 2018/6/10
 */
public class Node<K, V> {
    private int hash;//桶中的hash值,与key不一样
    private K key;
    private V value;
    public Node next;

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

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final String toString() {
        return key + "=" + value;
    }

    public int getHash() {
        return hash;
    }

    public void setHash(int hash) {
        this.hash = hash;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public void setValue(V value) {
        this.value = value;
    }
}

hash函数

参考JDK1.8，具体设计思想参考上篇的源码分析，这里不在赘述

   /**
     * 对key重新hash
     *
     * @param key
     * @return
     */
    private int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

   /**
     * hash函数，hash到索引的映射
     *
     * @param hash
     * @param len
     * @return
     */
    private int indexFromHash(int hash, int len) {
        int index = (len - 1) & hash;
        return index;
    }

判断key命中

前提:
1.hashcode相等;
2.key对象相同。

   /**
     * 判断key是否命中
     *
     * @param key
     * @param n
     * @return
     */
    private boolean isNodeHit(K key, Node n) {
        int hash = hash(key);
        if (n.getHash() == hash) {
            if (key == n.getKey() || (key != null) && (key.equals(n.getKey()))) {
                return true;
            }
        }
        return false;
    }

put方法

   /**
     * put操作
     * @param key
     * @param value
     */
    @Override
    public void put(K key, V value) {
        int hash = hash(key);
        int index = indexFromHash(hash, table.length);
        Node first = table[index];
        if (first == null) {//空坑直接占上
            first = new Node(hash, key, value);
            table[index] = first;
        } else {
            Node p = first;
            while (p.next != null) {
                if (isNodeHit(key, p)) {//链表中存在hit的node
                    //替换value,直接反馈
                    p.setValue(value);
                    return;
                }
                p = p.next;
            }
            p.next = new Node(hash, key, value);
        }
        if (++size > threhold) {
            resize();//扩容
        }
        return;
    }

程序结构和JDK1.8有出入，思路是一样的.

get方法

   /**
     * 获取方法
     * @param key
     * @return
     */
    @Override
    public V get(K key) {
        int index = indexFromHash(hash(key), table.length);
        Node<K, V> first = table[index];
        if (first == null) {
            return null;
        } else {
            Node<K, V> p = first;
            while (p != null) {
                if (isNodeHit(key, p)) {//如果命中则返回节点值
                    return p.getValue();
                }
                p = p.next;
            }
        }
        return null;
    }

remove方法

    /**
     * 删除元素
     * @param key
     * @return
     */
    @Override
    public V remove(K key) {
        int index = indexFromHash(hash(key), table.length);
        Node<K, V> first = table[index];
        V oldVal = null;
        if (first != null) {
            if (first.next == null) {//桶里面只有一个元素，直接删除
                oldVal = first.getValue();
                //直接删除
                table[index] = null;
            } else {
                if (isNodeHit(key, first)) {//头结点命中，则删除头结点
                    //直接删除头结点
                    table[index] = first.next;
                } else {
                    //开始遍历，查找key命中的节点
                    Node<K, V> pre = first;
                    Node<K, V> p = pre.next;
                    while (p != null) {
                        if (isNodeHit(key, p)) {//找到命中节点
                            oldVal = p.getValue();
                            pre.next = p.next;//删除操作
                            p.next = null;
                            break;
                        }
                        pre = p;
                        p = p.next;
                    }

                    if (p == null) {//没找到命中节点,直接返回
                        return null;
                    }
                }

            }
        }
        size--;
        return oldVal;
    }

思路:如果对应位置只有一个元素，则直接删除，否则遍历单链表，删除节点。

扩容操作

 /**
     * 扩容操作
     */
    private void resize() {
        int oldCap = table.length;
        int newCap = oldCap << 1;
        threhold = (int) (newCap * DEFAULT_LOAD_FACTOR);
        Node<K, V>[] newTable = new Node[newCap];
        for (int i = 0; i < oldCap; i++) {
            Node<K, V> first = table[i];

            if (first != null) {
                int hash = first.getHash();
                if (first.next == null) {
                    newTable[indexFromHash(hash, newCap)] = first;
                } else {//拆分单链表成两个部分，一个挂载低索引，另外一个挂载高索引
                    Node<K, V> next;//保存旧链表的后继节点
                    //两个单链表的首尾指针
                    Node<K, V> loHead = null, loTail = null;
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> p = first;
                    do {
                        next = p.next;
                        if ((oldCap & p.getHash()) == 0) {//低位索引
                            if (loTail == null) {
                                loHead = p;
                            } else {
                                loTail.next = p;
                            }
                            loTail = p;
                        } else {//高位索引
                            if (hiTail == null) {
                                hiHead = p;
                            } else {
                                hiTail.next = p;
                            }
                            hiTail = p;
                        }
                    } while ((p = next) != null);

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

                    if (hiHead != null) {
                        hiTail.next = null;
                        newTable[i + oldCap] = hiHead;
                    }
                }
            }
        }
        table = newTable;//替换旧数组
    }

单链表的拆分操作和设计思想和jdk一样，具体分析看上篇文章。
最后献上测试代码:

   /**
     * 测试哈希基本操作
     */
    @Test
    public void testHashMap() {
        HashA a = new HashA("ABC");
        HashB b = new HashB("ABC");
        //HashMap的key可以为空
        hash.HashMap<Object, String> hashMap = new hash.HashMap<>();
        hashMap.put(null, "90");
        System.out.println(hashMap.get(null));

        hash.HashMap<Object, String> myHashMap = new hash.HashMap<>();
        hash.HashMap<Object, String> myHashCrashMp = new hash.HashMap<>();
        System.out.println("=====哈希冲突测试====");
        myHashCrashMp.put(a, "a");
        myHashCrashMp.put(b, "b");
        System.out.println(myHashCrashMp.get(a));
        System.out.println(myHashCrashMp.get(b));
        List<HashA> keys = new LinkedList<>();
        for (int i = 0; i < 13; i++) {
            HashA hashObj = new HashA("ABC" + i);
            keys.add(hashObj);
            myHashMap.put(hashObj, "" + i);
        }
        System.out.println("=====哈希删除测试====");
        int delIndex = 4;
        myHashMap.remove(keys.get(delIndex));
        keys.remove(delIndex);
        System.out.println("=====哈希大小====");
        System.out.println(myHashMap.size());
        System.out.println("=====哈希打印====");
        for (int i = 0; i < keys.size(); i++) {
            HashA hashObj = keys.get(i);
            String v = myHashMap.get(hashObj);
            System.out.println(v);
        }
    }

完整代码地址:数据结构与算法学习JAVA描述GayHub地址