手写HashMap

article/2025/6/22 4:59:56

项目仓库：https://gitee.com/bossDuy/hand-tear-collection-series
基于一个b站up的课程：https://www.bilibili.com/video/BV1SWZrYDEag?spm_id_from=333.788.videopod.sections&vd_source=4cda4baec795c32b16ddd661bb9ce865

手写简单的HashMap

这里实现的是jdk1.7的，没有实现红黑树

简单的实现

并没对桶数组进行扩容

package com.yb0os1;import org.w3c.dom.Node;public class MyHashMap<K, V> {//默认的初始容量private static final int DEFAULT_INITIAL_CAPACITY = 16;//默认的负载因子private static final float DEFAULT_LOAD_FACTOR = 0.75f;//当前HashMap的大小private int size;//存储Node的数组private Node<K, V>[] table;//负载因子private float loadFactor;public MyHashMap() {this.size = 0;this.table = new Node[DEFAULT_INITIAL_CAPACITY];this.loadFactor = DEFAULT_LOAD_FACTOR;}public V put(K key, V value) {//put的时候，首先获取key的hashcode计算对应的indexOfint index = indexOf(key);Node<K, V> head = table[index];//判断数组当前index是否为空if (head == null) {//为空table[index] = new Node<>(key, value);size++;return null;}//当前数组下标位置不为空while (true) {//当前位置key和传入的key相同，替换valueif (head.key.equals(key)) {V oldValue = head.value;head.value = value;return oldValue;}//当前位置key和传入的key不相同，先判断是否到链表尾部if (head.next == null) {head.next = new Node<>(key, value);size++;return null;}//继续遍历下一个节点head = head.next;}}public V get(K key) {//get的时候，首先获取key的hashcode计算对应的indexOfint index = indexOf(key);Node<K, V> head = table[index];//判断数组当前index是否为空while (head != null){if(head.key.equals(key)){return head.value;}head = head.next;}return null;}public V remove(K key) {//remove的时候，首先获取key的hashcode计算对应的indexOfint index = indexOf(key);Node<K,V> head = table[index];//要判断是否为头节点//是头节点if(head!=null&&head.key.equals(key)){table[index] = head.next;--size;return head.value;}//不为头节点Node<K,V> pre = head;Node<K,V> cur = head.next;while(cur!=null){if(cur.key.equals(key)){pre.next=cur.next;--size;return cur.value;}pre = cur;cur  = cur.next;}return null;}public int size(){return size;}private int indexOf(Object key) {return key.hashCode() & (table.length - 1);}//hashmap里面的节点 entryprivate class Node<K, V> {public Node() {}public Node(K key, V value) {this.key = key;this.value = value;}public K key;public V value;public Node<K,V> next;}
}

我们进行测试

   @org.junit.Testpublic void test() {MyHashMap<String,String> myHashMap = new MyHashMap();int count = 100000;for (int i = 0; i < count; i++) {myHashMap.put(String.valueOf(i),  String.valueOf(i));}System.out.println(myHashMap.size());for (int i = 0; i < count; i++) {assertEquals(String.valueOf(i),myHashMap.get(String.valueOf(i)));}}

在这里插入图片描述

桶数组扩容版本

增加了桶数组扩容

package com.yb0os1;import org.w3c.dom.Node;public class MyHashMap<K, V> {//默认的初始容量private static final int DEFAULT_INITIAL_CAPACITY = 16;//默认的负载因子private static final float DEFAULT_LOAD_FACTOR = 0.75f;//当前HashMap的大小private int size;//存储Node的数组private Node<K, V>[] table;//负载因子private float loadFactor;public MyHashMap() {this.size = 0;this.table = new Node[DEFAULT_INITIAL_CAPACITY];this.loadFactor = DEFAULT_LOAD_FACTOR;}public V put(K key, V value) {//put的时候，首先获取key的hashcode计算对应的indexOfint index = indexOf(key);Node<K, V> head = table[index];//判断数组当前index是否为空if (head == null) {//为空table[index] = new Node<>(key, value);size++;resizeIfNecessary();return null;}//当前数组下标位置不为空while (true) {//当前位置key和传入的key相同，替换valueif (head.key.equals(key)) {V oldValue = head.value;head.value = value;return oldValue;}//当前位置key和传入的key不相同，先判断是否到链表尾部if (head.next == null) {head.next = new Node<>(key, value);size++;resizeIfNecessary();return null;}//继续遍历下一个节点head = head.next;}}public V get(K key) {//get的时候，首先获取key的hashcode计算对应的indexOfint index = indexOf(key);Node<K, V> head = table[index];//判断数组当前index是否为空while (head != null){if(head.key.equals(key)){return head.value;}head = head.next;}return null;}public V remove(K key) {//remove的时候，首先获取key的hashcode计算对应的indexOfint index = indexOf(key);Node<K,V> head = table[index];//要判断是否为头节点//是头节点if(head!=null&&head.key.equals(key)){table[index] = head.next;--size;return head.value;}//不为头节点Node<K,V> pre = head;Node<K,V> cur = head.next;while(cur!=null){if(cur.key.equals(key)){pre.next=cur.next;--size;return cur.value;}pre = cur;cur  = cur.next;}return null;}public int size(){return size;}private int indexOf(Object key) {return key.hashCode() & (table.length - 1);}private void resizeIfNecessary() {//不需要扩容的情况if(size<table.length*loadFactor)return;//需要扩容的情况 新建一个新的桶数组Node<K,V>[] newTable = new Node[table.length*2];//遍历老的桶数组，将原先的元素再哈希放到新的桶数组for(Node<K,V> head:table){if ( head==null)continue;Node<K,V>current = head;while(current!=null){//获取当前元素在新的桶数组中的indexint newIndex = current.key.hashCode() & (newTable.length-1);if( newTable[newIndex]==null){newTable[newIndex] = current;Node< K,V>next = current.next;current.next = null;current = next;}else{//头插法Node< K,V>next =current.next;current.next = newTable[newIndex];newTable[newIndex] = current;current = next;}}}this.table = newTable;System.out.println( "扩容了"+ table.length);}//hashmap里面的节点 entryprivate class Node<K, V> {public Node() {}public Node(K key, V value) {this.key = key;this.value = value;}public K key;public V value;public Node<K,V> next;}
}

test的用时变为：35ms

在这里插入图片描述

但是导致桶数组很大，而且如果hash冲突很严重的话查找还是O(n)，所以在jdk1.8引进了红黑树

注意点

多线程下hashmap存在死循环、数据丢失的问题。

1、jdk1.7扩容时采用的是头插法，1.8之后改为了尾插法

  1. 头插法的效率相比尾插法高，因为头插法只需要将新插入的节点的next指向原想的头节点，尾插法需要遍历到链表最尾端。
  2. 头插法在多线程情况下存在死循环的问题：比如两个线程，线程1修改头节点之后，线程2拿到current的节点还是已经修改之后的，那么就会导致current.next = current的操作，导致了死循环；尾插法不存在这个问题。
  3. JDK官方可能考虑在多线程环境下保证HashMap的可用性而不保证正确性，但是多线程下使用hashmap本就是一个错误的行为，因为错误的行为换成了一个效率比较低的操作我感觉有点本末倒置了

2、关于数据丢失的问题

  1. 两个线程1，2同时put操作，并且发生了哈希冲突（index相同）
  2. 当判断完冲突，并且计算到应该插入到哪一个位置的时候，线程1挂起
  3. 线程2执行插入操作，由于之前线程1已经计算到应该插入的位置，此时直接插入就导致线程2插入的数据被覆盖了

http://www.hkcw.cn/article/ukRRtRFSjE.shtml

相关文章

MySQL强化关键_018_MySQL 优化手段及性能分析工具

MySQL强化关键_018_MySQL 优化手段及性能分析工具

目 录 一、优化手段 二、SQL 性能分析工具 1.查看数据库整体情况 &#xff08;1&#xff09;语法格式 &#xff08;2&#xff09;说明 2.慢查询日志 &#xff08;1&#xff09;说明 &#xff08;2&#xff09;开启慢查询日志功能 &#xff08;3&#xff09;实例 3.s…
阅读更多...
VMware-workstation安装教程--超详细（附带安装包）附带安装CentOS系统教程

VMware-workstation安装教程--超详细（附带安装包）附带安装CentOS系统教程

VMware-workstation安装教程--超详细&#xff08;附带安装包&#xff09;附带安装CentOS系统教程 一、下载软件VMwware二、下载需要的镜像三、在VMware上安装系统 一、下载软件VMwware 二、下载需要的镜像 三、在VMware上安装系统 VMware 被 Broadcom&#xff08;博通&#x…
阅读更多...
Flutter - 原生交互 - 相机Camera - 01

Flutter - 原生交互 - 相机Camera - 01

环境 Flutter 3.29 macOS Sequoia 15.4.1 Xcode 16.3 集成 Flutter提供了camera插件来拍照和录视频&#xff0c;它提供了一系列可用的相机&#xff0c;并使用特定的相机展示相机预览、拍照、录视频。 添加依赖 camera: 提供使用设备相机模块的工具path_provider: 寻找存储图…
阅读更多...
HackMyVM-Art

HackMyVM-Art

信息搜集 主机发现 ┌──(kali㉿kali)-[~] └─$ nmap -sn 192.168.43.0/24 Starting Nmap 7.95 ( https://nmap.org ) at 2025-05-31 03:00 EDT Nmap scan report for 192.168.43.1 Host is up (0.0047s latency). MAC Address: C6:45:66:05:91:88 (Unknown) Nmap scan rep…
阅读更多...
第304个Vulnhub靶场演练攻略:digital world.local：FALL

第304个Vulnhub靶场演练攻略:digital world.local：FALL

digital world.local&#xff1a;FALL Vulnhub 演练 FALL (digitalworld.local: FALL) 是 Donavan 为 Vulnhub 打造的一款中型机器。这款实验室非常适合经验丰富的 CTF 玩家&#xff0c;他们希望在这类环境中检验自己的技能。那么&#xff0c;让我们开始吧&#xff0c;看看如何…
阅读更多...
使用 HTML + JavaScript 在高德地图上实现物流轨迹跟踪系统

使用 HTML + JavaScript 在高德地图上实现物流轨迹跟踪系统

在电商行业蓬勃发展的今天&#xff0c;物流信息查询已成为人们日常生活中的重要需求。本文将详细介绍如何基于高德地图 API 利用 HTML JavaScript 实现物流轨迹跟踪系统的开发。 效果演示 项目概述 本项目主要包含以下核心功能&#xff1a; 地图初始化与展示运单号查询功能…
阅读更多...
HTML Day04

HTML Day04

Day04 0.引言1. HTML字符实体2. HTML表单2.1 表单标签2.2 表单示例 3. HTML框架4. HTML颜色4.1 16进制表示法4.2 rgba表示法4.3 名称表达法 5. HTML脚本 0.引言 刚刚回顾了前面几篇博客&#xff0c;感觉写的内容倒是很详细&#xff0c;每个知识点都做了说明。但是感觉在知识组织…
阅读更多...
命令行式本地与服务器互传文件

命令行式本地与服务器互传文件

文章目录 1. 背景2. 传输方式2.1 SCP 协议传输2.2 SFTP 协议传输 命令行式本地与服务器互传文件 1. 背景 多设备协同工作中&#xff0c;因操作系统的不同&#xff0c;我们经常需要将另外一个系统中的文件传输到本地PC进行浏览、编译。多设备文件互传&#xff0c;在嵌入式开发中…
阅读更多...
进程间通信III·System V 系列(linux)

进程间通信III·System V 系列(linux)

目录 为什么有system V 共享内存 原理 操作 shmget 创建共享内存 shmctl 控制共享内存 shmat 挂接共享内存到进程的虚拟地址空间中 shmdt 将共享内存去关联 特点 模拟练习 Makefile client.cpp server.cpp main.hpp 小知识 为什么有system V linux是一种类unix系…
阅读更多...
Kafka 如何保证顺序消费

Kafka 如何保证顺序消费

在消息队列的应用场景中&#xff0c;保证消息的顺序消费对于一些业务至关重要&#xff0c;例如金融交易中的订单处理、电商系统的库存变更等。Kafka 作为高性能的分布式消息队列系统&#xff0c;通过巧妙的设计和配置&#xff0c;能够实现消息的顺序消费。接下来&#xff0c;我…
阅读更多...
数据结构：栈（Stack）和堆（Heap）

数据结构：栈（Stack）和堆（Heap）

目录 内存&#xff08;Memory&#xff09;基础 程序是如何利用主存的&#xff1f; &#x1f3af; 静态内存分配 vs 动态内存分配 栈&#xff08;stack&#xff09; 程序执行过程与栈帧变化 堆&#xff08;Heap&#xff09; 程序运行时的主存布局 内存&#xff08;Memo…
阅读更多...
数字权限管理（DRM）：保护数字内容安全的小卫士

数字权限管理（DRM）：保护数字内容安全的小卫士

《数字权限管理&#xff08;DRM&#xff09;&#xff1a;保护数字内容安全的小卫士》 在当今数字化飞速发展的时代&#xff0c;我们每天都在和各种各样的数字内容打交道&#xff0c;像电子书、音乐、电影、软件等等。然而&#xff0c;这些数字内容的版权保护和访问控制也成为了…
阅读更多...
进程同步：生产者-消费者 题目

进程同步：生产者-消费者 题目

正确答案&#xff1a; 问题类型&#xff1a; 经典生产者 - 消费者问题 同时涉及同步和互斥。 同步&#xff1a;生产者与消费者通过信号量协调生产 / 消费节奏&#xff08;如缓冲区满时生产者等待&#xff0c;空时消费者等待&#xff09;。互斥&#xff1a;对共享缓冲区的访问需…
阅读更多...
【第三十八周】BLIP-2：一种高效的视觉语言预训练框架

【第三十八周】BLIP-2：一种高效的视觉语言预训练框架

BLIP-2 摘要Abstract文章信息引言方法模型结构Stage1:表征学习Stage2:生成学习模型预训练 实验结果总结 摘要 本篇博客介绍了BLIP-2 &#xff0c;这是一种面向通用多模态任务的高效视觉语言预训练框架&#xff0c;其核心思想是在冻结大语言模型的前提下&#xff0c;通过引入一…
阅读更多...
算法打卡12天

算法打卡12天

19.链表相交 &#xff08;力扣面试题 02.07. 链表相交&#xff09; 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交**&#xff1a;** 题目数据…
阅读更多...
Redis最佳实践——安全与稳定性保障之连接池管理详解

Redis最佳实践——安全与稳定性保障之连接池管理详解

Redis 在电商应用的连接池管理全面详解 一、连接池核心原理与架构 1. 连接池工作模型 #mermaid-svg-G7I3ukCljlJZAXaA {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-G7I3ukCljlJZAXaA .error-icon{fill:#552222;}…
阅读更多...
无人机+AI视频联网：精准狙击，让‘罪恶之花’无处藏身

无人机+AI视频联网：精准狙击，让‘罪恶之花’无处藏身

引言&#xff1a;禁毒攻坚战&#xff0c;科技是关键 今天是2025年5&#xff0c;正值罂粟等毒株生长关键期。传统人工巡查耗时长、盲区多&#xff0c;而无人机巡检视频AI分析的智慧禁毒方案&#xff0c;正以“高空鹰眼地面AI”的立体化监控网络&#xff0c;实现毒株种植的早发现…
阅读更多...
以太网原理与开发802.3

以太网原理与开发802.3

W5500以太网搭建 官方移植库W5500 下载地址：GitCode - 全球开发者的开源社区,开源代码托管平台目录结构Ethernet以太网移植文件文件wizchip_conf 配置 芯片型号 工作模式 wizchip_conf.c配置 临界区片选SPI收发字节配置 自定义注册SPI // 自定义注册SPI相关回调函数 void use…
阅读更多...
day5 cpp:，对象的组织(const对象)，

day5 cpp:，对象的组织(const对象)，

1.对象的组织(类比内置类型) const对象 const对象只能调用const成员函数和数据成员&#xff0c;除了四大金刚 若成员函数没有加const(void print() const{}),即便里面没有_ix100修改值&#xff0c;也不能pt2.print()访问&#xff0c;因为是const Point pt2(3,5)--->对象不…
阅读更多...
C语言进阶--动态内存管理

C语言进阶--动态内存管理

学习数据结构重要的三个部分&#xff1a;指针、结构体、动态内存管理&#xff08;malloc、calloc、realloc、free&#xff09;。 1.为什么存在动态内存分配&#xff1f; 1.空间开辟大小是固定的&#xff1b; 2.数组在声明时&#xff0c;必须指定数组的长度&#xff0c;它所需…
阅读更多...
推荐文章

Copyright @ 2022~2023