说明

• JAVA8之前：HashMap 实现方式：数组 + 链表

• JAVA8：HashMap 实现方式：数组 + 链表 + 红黑树

实现原理

1. 创建 长度是 16 的数组

2. 使用 hash()函数，对 key 算出 hashcode 值，并对 16 取模，算出的值，就是数组中的位置，将 元素 放入到该位置

3. 但是，会发生冲突，原因如下：

   • hash()函数算出 hashcode 值会冲突
   • 由于数组长度是 16，当元素个数超过 16 时，比如会冲突

4. 解决冲突：数组存的是链表，当冲突时，将元素放入到链表中

下图是 JAVA8的实现方式，当链表长度大于8时，转为红黑树，查询数据更快

put() 方法实现过程

https://zhuanlan.zhihu.com/p/21673805

扩容机制

当 HashMap 中的元素个数超过 数组大小*loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75
就是说：默认情况下，数组大小为 16 ，那么当 HashMap 中元素个数超过 16*0.75=12 的时候，就把数组的大小扩展为 2*16=32 ，即扩大一倍

然后 重新计算每个元素在数组中的位置，而这是一个 非常消耗性能的操作

https://www.cnblogs.com/miaosj/p/11088613.html

提高性能

（不考虑 hashcode 冲突）
不发生扩容，性能就能提高，所以如果 预知元素的个数，那么预设元素的个数能够有效的提高性能。

比如，有 100 个 key/value，创建集合时指定容量： new HashMap(100)

但是 new HashMap(100) 还不是更合适的，因为 元素个数超过 0.75*100 时，数组就会发生扩容。

就是说为了让 0.75 * size > 100，size > 100/0.75 = 134，即创建集合时，指定 new HashMap(134) 才最合适

java代码

Node 节点类

package testmap;

public class Node {

    private String key;
    private Object value;
    private Node next;


    public Node(String key, Object value) {
        this.key = key;
        this.value = value;
    }

    public String getKey() {
        return key;
    }

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

    public Object getValue() {
        return value;
    }
    public void setValue(Object value) {
        this.value = value;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }


}

MyHashTable

package testmap;

public class MyHashTable {

    /**
     * 数组长度
     */
    private int ARR_LEN = 16;

    private Node[] table = new Node[ARR_LEN];

    private int size = 0;


    public void put(String key,Object value){
        // 根据 hashcode，算出应该在 数组中的哪个位置
        int index = Math.abs(key.hashCode()%ARR_LEN);

        // 从数组中取出 头结点
        Node l = table[index];
        // 如果为空，说明第一次添加，创建
        if(l == null){
            table[index] = new Node(key, value);
            size++;
        }else{// 不是第一次添加
            // 判断是否有该key
            Node resNode = get(l,key);
            // 如果key存在，就替换
            if(resNode != null){
                resNode.setValue(value);
            }else{// 不存在就添加到链表
                Node newNode = new Node(key,value);
                addTail(l, newNode);
                size++;
            }
        }

    }
    /**
     * 根据第一个节点Node和key，取出Node的key与该key相同的节点
     * @param head
     * @param key
     * @return
     */
    private Node get(final Node head,String key){
        Node ret = head;
        while( ret != null ){
            if(ret.getKey().equals(key)){
                break;
            }
            ret = head.getNext();
        }
        return ret;
    }
    /**
     * 添加到链表尾部
     * @param node
     * @param newNode
     */
    private void addTail(final Node node,Node newNode){
        Node tail = null;
        Node temp = node;

        while( temp != null ){
            tail = temp;
            temp = node.getNext();
        }
        tail.setNext(newNode);
    }
    public Object get(String key){
        int index = Math.abs(key.hashCode()%ARR_LEN);
        Node l = table[index];

        return get(l, key).getValue();
    }

    public int size(){
        return size;
    }
}

测试类

package testmap;

import java.util.Date;
import java.util.HashMap;

public class Test {

    public static void main1(String[] args) {
        MyHashTable mht = new MyHashTable();

//        System.out.println("重地".hashCode());
//        System.out.println("通话".hashCode());

        mht.put("name", "李雷");
        mht.put("set", "男");
        mht.put("length", 1.82);
        mht.put("birthday", new Date());
        mht.put("age", 20);
        mht.put("name", "韩梅梅");
        mht.put("name", "lucy");
        mht.put("重地", "123");
        mht.put("通话", "456");

        System.out.println(mht.get("name"));
        System.out.println(mht.get("set"));
        System.out.println(mht.get("length"));
        System.out.println(mht.get("birthday"));
        System.out.println(mht.get("age"));
        System.out.println(mht.get("重地"));
        System.out.println(mht.get("通话"));
        System.out.println(mht.size() );
    }
    public static void main(String[] args) {
        HashMap hm = new HashMap();
        hm.put("", "");
    }
}