jdk1.7-HashMap原理分析

public class ExtHashMap<K, V> implements ExtMap<K, V> {

    // 定义HashMap底层存储结构。一开始不初始化，懒加载
    private Node<K, V>[] table = null;

    // 数组扩容的负载因子，当负载因子太小，会造成频繁扩容。负载因子过大导致链表过长
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // table的初始化容量
    private static int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    // hashMap的实际长度
    private int size;

    /**
     * @Description:判断key是否相同
     */
    private boolean keyEqual(Node node, K k) {
        return node.key.equals(k) && node.key == k;
    }

    /**
     * @Description:计算当前key的hash值
     */
    private int calculateHash(K k, int length) {
        return k.hashCode() % length;
    }

    /**
     * @Description:hashMap进行添加值的方法
     */
    public V put(K k, V v) {
        // 判断table是否初始化
        if (table == null) {
            table = new Node[DEFAULT_INITIAL_CAPACITY];
        }
        // 判断是否需要扩容
        if (size >= (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR)) {
            resize();
        }
        // 将新元素添加到数组中
        Node newNode = new Node(k, v, null);
        // 获取hashCode值，并计算hash值
        int hash = calculateHash(k, DEFAULT_INITIAL_CAPACITY);
        // 获取table中是否有元素
        Node node = table[hash];
        if (node == null) {
            // 当前table下标处为空，需添加新的链表
            table[hash] = newNode;
            size++;
        } else {
            // 当前table下标处具有链表
            if (keyEqual(node, k)) {
                // key相同的情况下，进行数据覆盖
                node.setValue(v);
            } else {
                // key 不同，需要将元素添加到链表最前端
                newNode.next = node;
                table[hash] = newNode;
                size++;
            }
        }
        return v;
    }


    /**
     * @Description:数组进行扩容的方法
     */
    private void resize() {
        // 创建新的table,并且进行数组的扩容
        Node<K, V>[] newTable = new Node[DEFAULT_INITIAL_CAPACITY << 1];
        // 将table中的数据转移到newTable中，同时进行hash重排
        for (int i = 0; i < size; i++) {
            // 获取老的node
            Node oldNode = table[i];
            // 避免出现脏数据
            table[i] = null;
            while (oldNode != null) {
                // 获取oldNode的下一个
                Node oldNodeNext = oldNode.next;
                // 根据新的长度计算新的hash值
                int newHash = calculateHash((K) oldNode.key, DEFAULT_INITIAL_CAPACITY << 1);
                // 在链表最前面添加oldNode
                oldNode.next = newTable[newHash];
                newTable[newHash] = oldNode;
                oldNode = oldNodeNext;
            }
        }
        // 将newTable赋值给table，并且修改默认长度值
        DEFAULT_INITIAL_CAPACITY <<= 1;
        table = newTable;
        // 方便gc回收
        newTable = null;
    }

    /**
     * @Description:hashMap根据key获取value的方法
     */
    public V get(K k) {
        Node node = getNode(k);
        return node == null ? null : (V) node.value;
    }

    /**
     * @Description:根据key获取某个node
     */
    public Node getNode(K k) {
        // 计算hash值
        int hash = calculateHash(k, DEFAULT_INITIAL_CAPACITY);
        Node node = table[hash];
        while (node != null) {
            if (keyEqual(node, k)) {
                return node;
            }
        }
        return null;
    }

    /**
     * @Description:返回hashMap的实际长度
     */
    public int size() {
        return size;
    }

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

    }

    /**
     * @Description:节点
     */
    class Node<K, V> implements Entry<K, V> {
        K key;
        V value;
        Node<K, V> next;

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

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