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

  • 作者: 凯哥Java
  • 面试宝典
  • 时间:2020-08-12 21:42
  • 134人已阅读
简介 本文主要内容:1:了解HashMap底层。2:手写个简单版的hashMap一:hashMap是什么?底层怎么实现的HashMap底层实现原理是什么?HashMap是线程安全的吗?JDK8和JDK7对HashMap差异在哪?如果让你来设计HashMap思路是什么?HashMap在JDK7的时候采用的算法:数据+链表先来看看哈希算法:来看看数组定义:数组:采用一段连续的存储单元来存储数据。对于指定下标

本文主要内容:

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


Top Top