Java 散列存储详解及简单示例
作者:lqh 发布时间:2022-06-30 23:19:52
Java 散列存储
Java中散列存储的数据结构主要是指HashSet、HashMap、LinkedHashSet、LinkedHashMap以及HashTable等。要理解Java中的散列存储机制,那么我们必须先理解两个方法:equals()和hashCode()。关于equals()方法以及其与“==”关系操作符的区别,我们在另一篇文章中已经说明了。而对于hashCode(),它是在Object类中定义的一个方法:
public native int hashCode();
这是一个返回int值的本地方法,在Object类中没有被实现。这个方法主要被应用于使用散列的数据结构中,配合基于散列的集合一起正常运行,例如,在向一个容器(我们假设是HashMap)中插入一个对象时,怎样判断容器中是否已经存在该对象了呢?由于容器中的元素可能成千上万,使用equals()方法依次进行比较是非常低效的。散列的价值在于速度,它将键保存在某处,以便能够很快找到。存储一组元素最快的数据结构是数组,所以使用它来存储键的信息(注意是键的信息,而非键本身)。但是因为数组不能调整容量,因此就有一个问题:我们希望在Map中保存数量不确定的值,但是如果键的数量被数组的容量限制了,该怎么办呢?
答案就是:数组不保存键本身,而是通过键对象生成一个数字,将其作为数组的下标,这个数字就是散列码(hashcode),由定义在Object中的、且可能由你的类覆盖的hashCode()方法生成。为解决数组容量被固定的问题,不同的键可以产生相同的下标,这种现象被称为冲突。于是,在容器中查询一个值的过程是:先通过hashCode()计算待插入对象的散列码,然后使用散列码查询数组。对于冲突的处理,常常是通过外部链接,即数组并不直接保存值,而是保存值的list,然后对list中的值进行线性查询,这部分查询自然会比较慢。但是,如果散列函数足够好的话,数组的每个位置就只有较少的值。因此,散列机制便可以快速地跳到数组的某个位置,只对很少的元素进行比较。这就是HashMap会如此快的原因,我们可以通过HashMap.put()方法体会到:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
其主要思想便是:在键不为空时,根据键对象获取到散列码hash,然后通过散列码得到数组的下标i。在table[i]所表示的list中进行迭代,通过equals()判断该键是否存在,如果存在,则用新的值更新旧的值,返回旧的值;否则将新的键值对添加到HashMap中。从这里可以看出,hashCode方法的存在是为了减少equals方法的调用次数,从而提高程序效率。
这里我们需要注意到:hashCode()并不需要总是能够返回唯一的标识码,但是equals()方法必须严格地判断两个对象是否相同。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
来源:http://blog.csdn.net/xiangwanpeng/article/details/52842629
猜你喜欢
- 核心代码:Imei = ((TelephonyManager) getSystemService(TELEPHONY_SERVICE)).g
- 1、什么是过滤器?在客户端到服务器的过程中,当发送请求时,如果有不符合的信息将会被filter进行拦截,如果符合则会进行放行,在服务器给客户
- 问题背景公司的项目需要前后端分离,vue+java,这时候就需要支持Cors跨域请求了。最近对zuul进行升级,假如说zuul是1.0的话,
- 1.会话会话: 用户打开了一个浏览器,点击了很多超链接,访问多个web次元,关闭浏览器,这个过程可以称之为会话有状态会话: 带有访问记录的会
- springboot嵌套子类使用在实际项目里,我们会使用到一个User用户含有子类Address、这种嵌套子类在开发中会遇到很多问题,现在主
- Feign导入依赖为unknow的情况网上很多人在使用的feign时在pom.xml中的依赖为:<!-- SpringCloud 整合
- 本文主要讲解如何通过RabbitMQ实现定时任务(延时队列)环境准备需要在MQ中进行安装插件 地址链接插件介绍地址:https://www.
- 目录源码使用源码@Target({ElementType.TYPE, ElementType.METHOD})@Retention(Rete
- 在本篇博文中,我们主要讲解一下 IntelliJ IDEA 安装目录中的一些核心文件的功能及用法:如上图所示,我们定位到了 IntelliJ
- 平时项目中只要涉及表,那么一定能接触到众多各式各样的ID编号,博主整理一些常用的ID格式,整合一个ID生成工具类,供大家参考,如果有什么不足
- 首先打开vs,右击解决方案,点击管理解决方案的Nuget包管理然后我们点击浏览,搜索log4net,进行安装然后我们需要新建一个名为log4
- CSRF介绍CSRF(Cross-site request forgery),中文名称:跨站请求伪造,也被称为:one click atta
- 前言本文主要给大家介绍的是关于obix协议在java中的配置和使用,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧。什么是
- 前言公司的邮件系统用的是 * 的 Lotus notes, 你敢信?最近要实现一个功能,邮件提醒功能,就是通过自动发送提醒邮件 前
- 客户端代码using System;using System.Collections.Generic;using System.Compon
- 在进行详解之前,我想先声明一下,本次我们进行讲解说明的是 Kafka 消息存储的信息文件内容,不是所谓的 Kafka 服务器运行产生的日志文
- API参数:/**fileName: 临时文件的名字, 生成后的文件名字将会是【fileName + 随机数】suffix: 文件后缀,例如
- 目标依赖<!-- poi工具类--> <dependency>
- 配置Servlet的方法有俩种,分别是传统web.xml文档中部署servlet和注解方式部署servlet,下面就先一起来学习 * 解方式部
- 1. 只有public的property能显示出来,可以通过BrowsableAttribute来控制是否显示,通过CategoryAttr