Java HashMap原理与实现

说明

  • 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 > 100size > 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("", "");
    }
}

原文出处:https://malaoshi.top/show_1IX3bYvbc1jh.html