浅谈Java中的Hashmap

darkerXi 发布于2019-08-19 10:48 / 3046人阅读

摘要：很多种方式，在这里就不讨论每一种解决方式的利弊，我们只是对于中的作为研究。

在Java中，有一种而且我们使用很频繁的数据结构，叫做HashMap，其实准确的来说，这是散列表的一种冲突解决的实现，那么什么是散列表呢？这个概念在网上可以找到很多专业的回答，这里我们就举一个很简单的例子来说明一下什么是散列表。

首先我们要明确的一点，就是散列表肯定是用来存取东西的，那么如果我们要把西瓜，苹果，草莓这三种东西按照重量存到某个地方，方便我们后面再拿来使用，这个该如何操作呢？首先我们可以拿一个弹簧，然后使用这个弹簧将这些东西按照重量弹出去，因为重量的不同，将会落在不同的区域，这样就将这些东西“保存”了起来。如果我们后面要使用这些东西的时候，只需要按照重量再去使用一次弹簧就可以了，这样就能找到我们所需要找的。

这里我们再明确几个概念，这个例子中的几种东西，就是我们要存放的数据，弹簧指的是hash算法，因为这些数据的存放是无序的，所以这些概念综合起来看，称这种形式为散列表。

还有一个问题，就是如果在这个散列表中有两个数据通过hash算法落到了同一个区域，那么在这里就称之为冲突，或者叫hash冲突，在散列表中，解决冲突的方式有线性探测法，平方探测法，链式地址法。。。很多种方式，在这里就不讨论每一种解决方式的利弊，我们只是对于Java中的HashMap作为研究。

如果看过HashMap源码的朋友就会知道，在Java中HashMap是基于链式地址法来实现的，当然也有很多朋友可能不太喜欢看源码，好的，那么我们就按照HashMap来动手写一个简单的实现。

我们先定义一个节点类。

public class Entry {
    
    private Integer key;
    
    private String value;
    
    private Entry next;
    
    public Entry(Integer key, String value, Entry next){
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

然后我们在定义一个CopyHashMap类。

public class CopyHashMap {
    
    private final static int DEFAULT_CAPCITY = 11;
    
    private Entry[] arrEntry;
    
    public CopyHashMap(){
        arrEntry = new Entry[DEFAULT_CAPCITY];
    }
    
    public CopyHashMap(int size){
        arrEntry = new Entry[size];
    }
    
    private int hash(int key){
        return key % DEFAULT_CAPCITY;
    }
    
    public String get(int key){
        int h = hash(key);
        Entry entry = arrEntry[h];
        for (Entry e = entry; e != null; e = e.getNext()){
            if (e.getKey().equals(key)){
                return e.getValue();
            }
        }
        return null;
    }
    
    public void put(int key, String value){
        int h = hash(key);
        Entry entry = arrEntry[h];
        for (Entry e = entry; e != null; e = e.getNext()){
            if (e.getKey().equals(key)){
                e.setValue(value);
            }
        }
        arrEntry[h] = new Entry(key, value, arrEntry[h]);
    }
}

这里只是简单的写了一个get和put方法，代码很简单，看一看应该都能明白，可以看到其底层实现还是依赖于一个数组，这里有一个hash的方法，这个就是我们刚开始例子中的弹簧，对于每一个key都要去计算对应的hash值是多少，然后才能确定存放在数组中的哪个位置，所以能够看出，散列表中的hash算法的设计是非常重要的。

这段代码中还有一些东西没有做，比如remove方法，还有rehash方法，如果你有兴趣，那么可以动手实现一下这两个方法，rehash的过程在这里顺便提一下，简单的说就是如果存储列表不够用的情况下，hash表会扩容，然后将里面的数据重新hash一次，当然这个rehash会提前开始进行的，所以这里我们可以观察到一个现象就是如果散列表rehash一次，对程序的性能影响还是比较大的，对了，在JDK8中，HashMap也做了一些改进，链式存储的时候，在其长度达到某一个定值，后面的存储方式会转为红黑树的形式，有兴趣的话可以看一下源码。

HashMap在Java中的使用很频繁，很多人应该都懂其原理，可能也有很多人不太明白，希望这篇文章能让大家初窥HashMap的门道，更深入的研究就只能大家自己探索了。

服务器托管云服务器 java hashmap java_hashmap原理 java_hashmap实现设计浅谈

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76478.html

后台开发常问面试题集锦（问题搬运工，附链接）

摘要：基础问题的的性能及原理之区别详解备忘笔记深入理解流水线抽象关键字修饰符知识点总结必看篇中的关键字解析回调机制解读抽象类与三大特征时间和时间戳的相互转换为什么要使用内部类对象锁和类锁的区别，，优缺点及比较提高篇八详解内部类单例模式和 Java基础问题 String的+的性能及原理 java之yield(),sleep(),wait()区别详解-备忘笔记深入理解Java Stream流水...

spacewander 2019-08-21 17:42 评论0 收藏0
后台开发常问面试题集锦（问题搬运工，附链接）

摘要：基础问题的的性能及原理之区别详解备忘笔记深入理解流水线抽象关键字修饰符知识点总结必看篇中的关键字解析回调机制解读抽象类与三大特征时间和时间戳的相互转换为什么要使用内部类对象锁和类锁的区别，，优缺点及比较提高篇八详解内部类单例模式和 Java基础问题 String的+的性能及原理 java之yield(),sleep(),wait()区别详解-备忘笔记深入理解Java Stream流水...

xfee 2019-08-15 12:33 评论0 收藏0
后台开发常问面试题集锦（问题搬运工，附链接）

摘要：基础问题的的性能及原理之区别详解备忘笔记深入理解流水线抽象关键字修饰符知识点总结必看篇中的关键字解析回调机制解读抽象类与三大特征时间和时间戳的相互转换为什么要使用内部类对象锁和类锁的区别，，优缺点及比较提高篇八详解内部类单例模式和 Java基础问题 String的+的性能及原理 java之yield(),sleep(),wait()区别详解-备忘笔记深入理解Java Stream流水...

makeFoxPlay 2019-07-31 11:00 评论0 收藏0
Java学习路线总结，搬砖工逆袭Java架构师（全网最强）

摘要：哪吒社区技能树打卡打卡贴函数式接口简介领域优质创作者哪吒公众号作者架构师奋斗者扫描主页左侧二维码，加入群聊，一起学习一起进步欢迎点赞收藏留言前情提要无意间听到领导们的谈话，现在公司的现状是码农太多，但能独立带队的人太少，简而言之，不缺干 ? 哪吒社区Java技能树打卡【打卡贴 day2...

Scorpion 2021-11-18 10:02 评论0 收藏0