手写HashMap

经过HashMap源码分析，我们可以手写一个简单的HashMap

废话不多说，直接上代码

一个简单的HashMap拥有的方法，我把它定义为一个接口

public interface MyMap<K, V> {

	public V put(K k, V v); //插入

	public V get(K k);//获取元素

	public int size();//元素大小

	interface Entry<K, V> {//键值对

		K getKey();

		V getValue();

		V setValue(V value);
	}
}

　　HashMap手写代码

　　

public class MyHashMap<K, V> implements MyMap<K, V> {
    // 1.定义table 存放HasMap 数组元素 默认是没有初始化容器 懒加载
    Node<K, V>[] table = null;
    // 2. 实际用到table 存储容量 大小
    int size;
    // 3.HashMap默认负载因子，负载因子越小，hash冲突机率越低， 根据每个链表的个数
    float DEFAULT_LOAD_FACTOR = 0.75f;
    // 4.table默认初始大小
    static int DEFAULT_INITIAL_CAPACITY = 16;

    @SuppressWarnings("unchecked")
    @Override
    public V put(K key, V value) {
        // 第一次初始化
        if (table == null) {
            table = new Node[DEFAULT_INITIAL_CAPACITY];
        }

        // 扩容 如果数组大小大于 负载因子乘以默认大小 就扩容
        if (size > DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR) {
            resize();
        }
        // 根据key获取 新元素在数组中的下标
        int index = getIndex(key, DEFAULT_INITIAL_CAPACITY);

        // 获取当前节点
        Node<K, V> node = table[index];
        if (node == null) {
            // node为空 代表当前位置的值为空 直接插入。
            node = new Node<>(key, value, null);
            size++;
        } else {// 代表当前元素有值
            // 保存原链表
            Node<K, V> newNode = node;
            while (newNode != null) {
                // 如果发生key冲突，则值直接覆盖 并返回原node
                if (newNode.key.equals(key) || newNode.key == key) {
                    return newNode.setValue(value);
                } else {
                    // 如果未发送key冲突，代表新元素。 插入到链表的头位置。
                    if (newNode.next == null) {
                        node = new Node<>(key, value, node);
                        size++;
                    }
                }
                newNode = newNode.next;
            }
        }
        // 赋值
        table[index] = node;
        return value;
    }

    // 根据Length获取 key在数组的下标
    private int getIndex(K key, int length) {
        int hashCode = key.hashCode();
        int index = hashCode % length;
        return index;
    }

    /**
     * threshold（capacity * loadFactor） 扩容扩容之后的是倒序的链表
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        // 新数组的长度为原数组的二倍
        Node<K, V>[] newTable = new Node[DEFAULT_INITIAL_CAPACITY << 1];
        // 遍历原数组 把原数组的每个元素放入新数组中
        for (int i = 0; i < table.length; i++) {
            Node<K, V> oldNode = table[i];
            table[i] = null;// 赋值为null---为了垃圾回收机制能够回收 将之前的node删除
            while (oldNode != null) {
                // 获取该元素的在新数组的下标
                int index = getIndex(oldNode.key, newTable.length);
                // 保留原Node的下一个
                Node<K, V> oldNext = oldNode.next;
                // 为新数组赋值
                oldNode.next = newTable[index];
                newTable[index] = oldNode;
                // 继续遍历
                oldNode = oldNext;
            }
        }

        table = newTable;
        DEFAULT_INITIAL_CAPACITY = newTable.length;
        newTable = null;/// 赋值为null---为了垃圾回收机制能够回收
    }

    // 根据键获取值
    @Override
    public V get(K k) {
        Node<K, V> node = getNode(table[getIndex(k, DEFAULT_INITIAL_CAPACITY)], k);
        return node == null ? null : node.value;
    }

    // 遍历链表 根据键获取值
    public Node<K, V> getNode(Node<K, V> node, K k) {
        while (node != null) {
            if (node.key.equals(k)) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }

    static class Node<K, V> implements Entry<K, V> {

        final K key;

        V value;

        Node<K, V> next;

        Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            V oldValue = value;
            this.value = value;
            return oldValue;
        }

    }

    // 打印
    public void print() {
        for (int i = 0; i < table.length; i++) {
            Node<K, V> node = table[i];
            System.out.print("下标位置[" + i + "]");
            while (node != null) {
                System.out.print("[ key:" + node.getKey() + ",value:" + node.getValue() + "]");
                node = node.next;
            }
            System.out.println();
        }
    }

}