对HashMap的思考及手写实现-低调大师

对HashMap的思考及手写实现

2018-09-06 585

HashMap是Java中常用的集合，而且HashMap的一些思想，对于我们平时解决业务上的一些问题，在思路上有帮助，基于此，本篇博客将分析HashMap底层设计思想，并手写一个迷你版的HashMap！

对HashMap的思考

HashMap底层数据结构

第一，如图所示，HashMap有3个要素：hash函数+数组+单链表

通过写一个迷你版的HashMap来深刻理解

定义接口

接口

定义一个接口，对外暴露快速存取的方法。

注意MyMap接口内部定义了一个内部接口Entry。

接口实现

3df1edd11dbd6abc1120ca7099f98b05b5aa2420

MyHashMap定义

HashMap的要素之一，就是数组，自然在这里，我们要定义数组，数组的初始化大小，还要考虑扩容的阀值。

看MyHashMap的构造

073615f0c1e6eb6db4cbabfa909e726c7918657d

构造方法

构造方法有什么好说的呢？

仔细观察下，你会发现，其实这里使用到了“门面模式”。这里的2个构造方法其实指向的是同一个，但是对外却暴露了2个“门面”！

Entry

cf4a1cbf925b9a3502e7fa392b91ae70b8961f25

Entry

HashMap的要素之一，单链表的体现就在这里！

看put如何实现

put

第一，要考虑是否扩容？

HashMap中的Entry的数量（数组以及单链表中的所有Entry）是否达到阀值？

第二，如果扩容，意味着新生成一个Entry[]，不仅如此还得重新散列。

第三，要根据Key计算出在Entry[]中的位置，定位后，如果Entry[]中的元素为null，那么可以放入其中，如果不为空，那么得遍历单链表，要么更新value，要么形成一个新的Entry“挤压”单链表！

hash函数

MyHashMap提供的hash函数

DK的HashMap提供的hash函数

我这里参考了JDK的HashMap的hash函数的实现，这里也再次说明了：要想散列均匀，就得进行二进制的位运算！

resize和rehash

resize/rehash

这里可以看出，对于HashMap而言，如果频繁进行resize/rehash操作，是会影响性能的。

resize/rehash的过程，就是数组变大，原来数组中的entry元素一个个的put到新数组的过程，需要注意的是一些状态变量的改变。

get实现

get

get很简单，只需要注意在遍历单链表的过程中使用== or equals来判断下即可。

Test测试

利用MyHashMap进行存取

运行结果

972a2bfec24dab953f41f23d8be5a2ce5dd06178

result

OK，一个迷你版的HashMap就写好了，你学到了么？

原文发布时间为：2018-09-6

本文作者：张丰哲

本文来自云栖社区合作伙伴“ java进阶架构师”，了解相关信息可以关注“ java进阶架构师”。

微信关注我们

原文链接：https://yq.aliyun.com/articles/636918

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

AI-多云互联，网络通信的“自动驾驶

数字时代需要可编程的灵活性，敏捷性和互连性全球国际电信会议PTC称数字化转型将开启“‘连接’的新十年”。Equinix在发布的《全球互联指数》报告中指出，城市化、数据主权、网络安全和全球数字服务贸易等技术的使用，推动了全球数字化的发展趋势。正是在这样的背景下，数字媒体、人工智能/机器学习(AI/ML)、大数据和安全分析、增强/虚拟现实和物联网(IoT)等产业日益增长。与传统骨干网络相比，这些技术应用的动态性和交互性特征需要更加的弹性、灵活、低延迟和高带宽的连接来处理数字洪流。事实上，全球互连指数预测，到2020年，数字业务将需要5,000 Tbps以上的互连带宽容量，才能满足企业之间数据交换，这一带宽容量需求已经超过了当前全球IP流量、互联网和MPLS网络的总体增长。这就是为什么业界纷纷转向SDN和NFV技术，从而将其带入数字化时代的未来! 过去十年来，SDN和NFV的供应商和用户一直致力于充分利用这两种不断发展的技术，但仍有很大的增长空间。TBR报告称，近四分之三的领先一级运营商已经或计划采用SDN和NFV。报告预测从2016年到2022年，SDN/NFV总开支将增长94.3%...

2018-09-07

630

背景介绍乐词是新东方倾情打造权威英语单词背记APP，业务涵盖初中、高中、新概念、英语四六级、考研、雅思、托福、GRE、SAT、ACT 、GMAT、托业、商务英语等英语单词库，科学规划词根背记，离线背单词随时学，权威详尽单词解析，全新考试干货课程，群组背记英语单词，完整的视频教学体系为用户提供全方位的单词学习体验。乐词系统涵盖词书、背词、查词、视频课程、活动、用户、在线支付等10多个核心业务模块，用户使用日活10w+，为了给用户提供稳定可靠的服务，对我们系统的可用性提出了更高的要求。Redis作为业界目前流行的Key-Value型NoSQL存储组件，可以帮我们解决面临的技术挑战。因我们属于创业型项目，自建系统以及自行运维意味着前期较大的投入以及过高的运维成本，随着业务规模的扩张，资源水平扩展以及垂直扩展也是未来无法避免的痛点，所以我

2018-09-07

586

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。