HashSet和HashMap的底层实现——哈希表、散列表_lpp1234567的博客-程序员宝宝_hashset底层是数组还是哈希表

技术标签: JAVA基础  

java.lang 
类 Object

java.lang.Object

int hashCode() 
          返回该对象的哈希码值。

boolean equals(Object obj)
          指示某个其他对象是否与此对象“相等”。


一、概述

java最基本的两种数据结构:数组和链表的区别:

数组易于快速读取(通过for循环),不便存储(数组长度有限制);链表易于存储,不易于快速读取。

哈希表的出现是为了解决链表访问不快速的弱点,哈希表也称散列表。

HashSet是通过HasMap来实现的,HashMap的输入参数有Key、Value两个组成,在实现HashSet的时候,保持HashMap的Value为常量,相当于在HashMap中只对Key对象进行处理。

HashMap的底层是一个数组结构,数组中的每一项对应了一个链表,这种结构称“链表散列”的数据结构,即数组和链表的结合体;也叫散列表、哈希表。


HahMap存储对象的过程如下:

1、对HahMap的Key调用hashCode()方法,返回int值,即对应的hashCode;

2、把此hashCode作为哈希表的索引,查找哈希表的相应位置,若当前位置内容为NULL,则把hashMap的Key、Value包装成Entry数组,放入当前位置;

3、若当前位置内容不为空,则继续查找当前索引处存放的链表,利用equals方法,找到Key相同的Entry数组,则用当前Value去替换旧的Value;

4、若未找到与当前Key值相同的对象,则把当前位置的链表后移(Entry数组持有一个指向下一个元素的引用),把新的Entry数组放到链表表头;


HashMap的内存实现结构如下:


注意:在哈希表的数组结构中Entry对象已经超出0.75的容量,因此需要重新申请内存了。


二、使用示例

利用HashMap往散列表中存放<Key, Value>,并根据存入的Key,返回Value值。


①Key为基本数据类型

import java.util.*;
class  MapDemo
{
public static void main(String[] args) 
{
Map map = new HashMap();
map.put("a",new Integer(1));
map.put("b",new Integer(2));
map.put("c",new Integer(3));

Set set= map.keySet();

for(Iterator iter = set.iterator();iter.hasNext();)
{
String key = (String)iter.next();
Integer value = (Integer)map.get(key);


System.out.print(key+", "+value);
System.out.println();
}
System.out.println(map.get("a"));

System.out.println(map.get("b"));

System.out.println(map.get("c"));
}
}

结果:

b, 2

c, 3

a, 1

1

2

3

②Key为对象引用类型

import java.util.* ;
class Person
{
private String name ;
private int age ;
Person(String name,int age)
{
this.name = name ;
this.age = age ;
}
public String toString()
{
return "姓名:"+this.name+",年龄:"+this.age ;
}
}

public class HashCodeDemo
{
public static void main(String args[])
{

HashMap hm = new HashMap() ;
hm.put(new Person("张三",20),"张三") ;
System.out.println(hm.get(new Person("张三",20))) ;

}

结果:null

原因:两次new Person("张三",20)实例化的引用不同,因此在查找哈希表的时候,index也不同。

修改成如下:

public class HashCodeDemo
{
public static void main(String args[])
{
HashMap hm = new HashMap() ;
Person p1 = new Person("张三",20);
hm.put(p1,"张三") ;
System.out.println(hm.get(p1)) ;
}
}

结果:张三

或者进行强制修改hashCode()方法和equals()方法,另hashCode()返回固定的值(即,每次对Key进行哈希编码的值都是一样的),另equals()方法返回true(即在哈希表中找到了与当前Key对应的Value)。

为什么重写了hashCode()方法后,必须要重写equals()方法呢?

原因是,哈希码相同仅代表Key相同,不代表Entry数组里面的Value值相同。

class Person
{
private String name ;
private int age ;
Person(String name,int age)
{
this.name = name ;
this.age = age ;
}
public String toString()
{
return "姓名:"+this.name+",年龄:"+this.age ;
}


public boolean equals(Object obj)
{
return true ;
}
public int hashCode()
{
return 20 ;//返回任意一个int值都可以
}
}

public class HashCodeDemo
{
public static void main(String args[])
{

HashMap hm = new HashMap() ;
hm.put(new Person("张三",20),"张三") ;
System.out.println(hm.get(new Person("张三",20))) ;

}

结果:张三

分析:上例中利用重写hashCode()方法,返回相同的哈希码,这时如果把System.out.println(hm.get(new Person("张三",20))) ;修改成System.out.println(hm.get(new Person("李四",20))) ;后返回的哈希码也是相同的。在当前哈希码对应index上查找Entry数组组成的链表,因为equals()方法返回的是true,所以结果就找到了hm.put(new Person("张三",20),"张三") ;中的Value值——张三。

若再放入一个Entry数组  hm.put(new Person("张三",20),"王五") ;结果会变成怎么样呢?

public class HashCodeDemo
{
public static void main(String args[])
{
HashMap hm = new HashMap() ;

hm.put(new Person("张三",20),"张三") ;
hm.put(new Person("张三",20),"王五") ;

System.out.println(hm.get(new Person("张三",20))) ;

}

结果:王五

为什么不是  张三?

在数据库结构中,程序默认的对最近一次放入的数据具有较高的优先级,因为hm.put(new Person("张三",20),"王五") ;是后放入的,所以返回 王五。

若调换一下顺序:

public class HashCodeDemo
{
public static void main(String args[])
{
HashMap hm = new HashMap() ;

hm.put(new Person("张三",20),"王五") ;

hm.put(new Person("张三",20),"张三") ;

System.out.println(hm.get(new Person("张三",20))) ;

}

结果:张三

在复写equals()方法时,返回设定为false:

public boolean equals(Object obj)
{
return false ;
}

结果:null

原因:虽然hashCode()返回值相同,即找到了数组index,但在当前索引的链表中,没有找到Key相同的Entry包,所以最后返回null。


总结:在查找哈希表中的对象时,首先根据Key确定哈希码,以哈希码作为数组的索引查找对应位置的链表,从链表头开始查找有相同的Key值的Entry包,找到后返回映射对象。链表上多个Entry包的哈希码可以相同,但Value值肯定不相同。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lpp1234567/article/details/20640759

智能推荐

nanopi 2 fire s5p4418 初次体验 (2)烧写uboot到sd卡,通过tftp启动内核,nfs挂载根文件系统_Ethan_LiuQuan的博客-程序员宝宝

nanopi 2 fire s5p4418 初次体验 (2)烧写uboot到sd卡,通过tftp启动内核,nfs挂载根文件系统

Win11玩游戏突然没有声音怎么恢复?_小白一键重装系统的博客-程序员宝宝

近期有部分Win11用户反映,在玩游戏时电脑突然没有声音了,这样十分影响游戏体验,那么有没有什么方法可以恢复呢?如果你也有同样的困扰,不妨来看看下面这篇小编带来的详细的解决教程吧,希望对你有所帮助哦。更多系统教程尽在小白系统网​  方法一:  1、首先,按【 Win + i 】组合键,打开Windows 设置,然后点击【声音(音量级别、输出、输入、声音设备)】;  2、高级下,找到并点击【更多声音设置】;  3、声音窗口,双击正在使用的声音设备【扬声器】;  4、扬声器 属性窗口,【高级】选项卡下,取消勾选

java hashmap总结_Fourier_1024的博客-程序员宝宝

0. 前言总结hashmap用法。1. 使用场景涉及到对同一数据数组(一维或者多维)进行反复查找的。2. 常用语法

struts2----IOC容器的实现机制(上篇)_iteye_8039的博客-程序员宝宝

说起 IOC 容器,依赖注入等名词,大家的第一印象往往是spring,因为spring刚出道的时候招牌就是 IOC和AOP等核心功能,而且我们在应用程序中使用spring最多的功能之一也是其 IOC 容器提供的。而 struts2做为一个 web层的MVC实现框架,其核心功能主要是帮助我们处理 http请求,但是 struts2本身也包含了一个 IOC 容器,用来支撑struts2的运行环境,...

Leetcode【分治 链表】| 23. 合并K个排序链表_Cherils的博客-程序员宝宝

Leetcode | 23. 合并K个排序链表题目解题顺序依次合并合并2链表递归实现合并2链表迭代实现两两成对合并(分治)题目合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入:  [   1-&gt;4-&gt;5,   1-&gt;3-&gt;4,   2-&gt;6  ] 输出: 1-&gt;1-&gt;2-&gt;3-&gt;4-...

C语言的fopen()函数_Galaxy_Robot的博客-程序员宝宝_c语言fopen

C语言的fopen()函数fopen()的声明在头文件:#include &lt;stdio.h&gt;fopen()是一个常用的函数,用来以指定的方式打开文件,其原型为:​ FILE * fopen(const char * path, const char * mode);【参数】path为包含了路径的文件名,mode为文件打开方式(模式)。表1 fopen()的模式字符串打开方式说明“r”以读模式打开文件“w”以写模式打开,把现有文件的长度截为0,

随便推点

ubuntu 学习_再等一次的博客-程序员宝宝_ubuntu 学习

/etc/default/locale 语言设置LANG=”en_US.UTF-8″LANGUAGE=”en_US:en”ubuntu下 vi输入方向键会变成ABCD,这是ubuntu预装的是vim tiny版本,安装vim full版本即可解决先卸载vim-tiny:sudo apt-get remove vim-common

java获取企业微信打卡数据_咯_的博客-程序员宝宝

目录先获取AppToken:有了Token再加上企业id就可获取到企业微信的组织架构:进行考勤数据读取:近期一个项目中需要获取企业微信的打卡记录并同步到本地来进行考勤相关业务的处理,其中涉及了如何获取企业微信的部门组织,如何通过组织架构获取每个部门的人员Userid,然后再获取考勤数据等等。其中必要的条件有 企业ID,通讯录 AppSecre 值,打卡 AppSecre 值。企业ID位置在企业微信管理后台,上方最右侧我的企业&gt;&gt;&gt;企业信息&gt;&gt;最下方就能查找.

实现网络空间的“挂图作战”:网络空间地理学+可视化技术_知道创宇KCSC的博客-程序员宝宝

郭启全1,2 高春东1 郝蒙蒙1* 江 东11 中国科学院地理科学与资源研究所2 中华人民共和国公安部 网络安全保卫局在传统的地理空间,地图作为描绘地理现象的重...

linux连接池等待时间,LINUX系统下解决time_wait 连接数过多问题_日立中央空调的博客-程序员宝宝

经常检查apache的连接数,会发现很多无用的time_wait连接。有人说这是正常的,是因为一个请求中途中断造成的;还有人说微软的IE连接时产生的Time_wait会比用Firefox连接时多。个人认为有一定的Time_wait是正常的,如果超过了连接数的比例就不是很正常,所以还是找来方法解决一下。先检查一下time wait的值:[[email protected] ~]#sysctl -a | grep t...

Git Submodule 管理项目子模块_huangjiazhi_的博客-程序员宝宝_git submodule怎么在dockerfile

1、添加一个子模块git submodule add 子模块地址 自定义到当前工程的路径git commitgit push2、克隆/更新带子模块的工程2.1、方法一:git clone 工程地址, 进入工程后git submodule init (init 操作只需要在刚clone下来时执行一下就行了,以后就不需要执行了)git submodule updat...

cartographer代码学习-回调函数与传感器数据走向_一叶执念的博客-程序员宝宝

1、里程计数据走向:里程计的回调函数为:/** * @brief 处理里程计数据,里程计的数据走向有2个 * 第1个是传入PoseExtrapolator,用于位姿预测 * 第2个是传入SensorBridge,使用其传感器处理函数进行里程计数据处理 * * @param[in] trajectory_id 轨迹id * @param[in] sensor_id 里程计的topic名字 * @param[in] msg 里程计的ros格式的数据 */void Node::Handle

推荐文章

热门文章

相关标签