提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

透过底层看本质，hashMap原理讲解

2023-02-18 16:31:23 时间

本文主要内容：

1：了解HashMap底层。

2：手写个简单版的hashMap

一：hashMap是什么？底层怎么实现的

HashMap底层实现原理是什么？ HashMap是线程安全的吗？

JDK8和JDK7对HashMap差异在哪？

如果让你来设计HashMap思路是什么?

HashMap在JDK7的时候采用的算法：

数据+链表

先来看看哈希算法：

来看看数组定义： 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，实际复杂度为0(1);对于一般的插入删除操作，涉及到数组中的元素移动，所以其平均复杂度业务O(n).

再来看看链表的定义：

线性链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序来实现的。

对于链表的新增、删除等操作(在指定位置操作位置后)，仅需处理节点间的引用即可，实际复杂度为0(1);

然后查找操作需要遍历链表逐一进行比对的。复杂度为O(n).

HashMap中链表中Entry对象的属性

JDK8之后HashMap底层数据结构发生了变化

数组+链表+红黑树。

为什么要用红黑树呢？

使用红黑树是为了解决，当链表过长的时候，导致循环耗时(循环获取的复杂度是O(N))。

所以JDK8之后，设置的阀值是，当链表的长度为8的时候，会自动转换成红黑树的。

HashMap结合了数组和链表的特性，hashCode值不冲突，不产生链表，怎么会有链表的特性呢？

面试题：

hashMap是否是线程安全的？这个其实就是要考的是，hashMap在扩容的时候，不是线程安全的。这个点的。

二：手写个简单版的HashMap

hashMap接口类：

package com.kaigejava.mymap;

/**
 * @author kaigejava
 */
public interface  KgMap<K,V> {

    public V put(K k,V v);
    public V get(K k);
    public  int size();

    interface  EntryNode<K,V>{
        public K getKey();
        public V getValue();
    }
}

实现类：

package com.kaigejava.mymap.impl;

import com.kaigejava.mymap.KgMap;

public class KgHashMap<K,V> implements KgMap<K,V> {
    private EntryNode<K,V>[] table = null;
    private int size = 0;
    private static  int DEFAULTLENTH =  16;

    public KgHashMap (){
        table = new EntryNode[DEFAULTLENTH];
    }

    public V put(K k, V v) {
        //通过key获取到key所对应的hash之
        int keyHash = getHash(k);
        //根据key算出的hash值判断是否已经存在了
        EntryNode node = table[keyHash];
        if(null == node){
            //不存在。直接把这个node添加进去.这个是next为空
            table[keyHash] = new EntryNode(k,v,keyHash,null);
            size++;
        }else{
            //已经存在了，需要把这个node追加在链表的头部,next指向现在map中存在对于hash的node.
            table[keyHash] = new EntryNode(k,v,keyHash,node);
        }
        return table[keyHash].getValue();
    }

    /**
     * 获取hash值得
     * @param k
     * @return
     */
    private int getHash(K k) {
        int code = k.hashCode()%(DEFAULTLENTH-1);
        return Math.abs(code);
    }

    public V get(K k) {
        //map空对象的直接返回
        if(size == 0){
            return null;
        }
        int keyHah = getHash(k);
        EntryNode<K,V>  v = getEntryValue(k,keyHah);
        return null==v?null:v.getValue();
    }

    /**
     * 根据k和k的hashCode获取
     * @param k
     * @param index
     * @return
     */
    private EntryNode<K,V>  getEntryValue(K k, int index) {
        for(EntryNode<K,V> e = table[index];null != e ;e = e.next){
            //循环获取。需要对key进行比较
            if(index == e.hash&& ((k == e.getKey()) ||k.equals(e.getKey()))){
                return  e;
            }
        }
        return  null;
    }

    public int size() {
        return size;
    }

    class EntryNode<K,V> implements  KgMap.EntryNode{
        K k;
        V v;
        int hash;
        EntryNode<K,V> next;
        public EntryNode(K k,V v,int hash,EntryNode<K,V> next){
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        public K getKey() {
            return k;
        }

        public V getValue() {
            return v;
        }
    }
}

测试类：

package com.kaigejava.mymap;

import com.kaigejava.mymap.impl.KgHashMap;

public class KgMapDemo {
    public static void main(String[] args) {
        KgMap kgHashMap = new KgHashMap();
        kgHashMap.put("6",1);
        kgHashMap.put((3+3),2);
        kgHashMap.put((5+1),3);
        System.out.println(kgHashMap.get((5+1)));
    }
}

相关文章