NotionNext
NotionNext
编程爱好者
/互联网从业者
/知识分享博主
认知决定态度,态度决定选择,选择决定人生

HashMap

NotionNext - 2023-4-23 - Technical / Java / 后端
发布于:2023-4-23|最后更新: 2023-8-29|
type
status
date
slug
summary
tags
category
icon
password

什么是HashMap?

  • HashMap是Java中常用的一种键值对存储结构,它实现了Map接口。HashMap中的数据是以键值对形式存储的,其中键是唯一的,且不能为空,值可以是null。
  • Hash table based implementation of the Map interface
  • 基于哈希表的 Map 接口实现

什么是哈希表?

  • 设计精妙,用途广泛的数据结构之一
  • 拥有键值对元素的无序集合
  • 键的值是唯一的,键对应的值可以通过键来获取,更新或移除
  • 无论这个哈希表有多大,这些操作(Insert/Search/Delete)基本上通过常量时间O(1)的键比较就可完成

为什么要设计哈希表?

  • 连续型数据结构
    • 数组:查询快
  • 离散型
    • 链表:插入删除快
  • 哈希表:为了兼顾两者的优点,设计了哈希表
  • 具体来说,哈希表有以下几个主要优点:
  1. 快速查找:哈希表中数据的存储方式允许我们快速并且随机地访问其元素,因此我们可以迅速地查找到需要的数据。
  1. 快速插入和删除:哈希表中的数据是通过哈希函数映射到数组中的位置,因此我们可以在常数时间内快速地插入和删除数据。
  1. 高效的空间利用率:哈希表可以动态地扩展和缩小其存储空间,从而达到高效利用空间的目的。

构造一个HashMap

  • 如何构造一个HashMap
    • size/isEmpty方法
      • 重点:put/putAll/putIfAbsent
      • get/getOrDefault
      • containskey/containsValue
      • remove
      • replace
      • keySet()/values()/entrySet()
       
      • 遍历Hashmap
        • 通过 entrySet 遍历entry
        • 通过 keySet 遍历key, 再通过get(key)遍历value
        • 利用迭代器遍历 set的迭代器 (一般工作中较少用到)
          • 利用迭代器遍历 entrySet
          • 利用迭代器遍历 keySet
        • lambda 表达式遍历
        •  
       
      动手实现一个HashMapJava中的排序