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


猜你喜欢
- 先扯再说最近一直在研究某个国产开源的MySQL数据库中间件,拉下其最新版的代码到eclipse后,启动起来,然后做各种测试和代码追踪;用完想
- 本文实例为大家分享了AndAndroid实现网页图片浏览的具体代码,供大家参考,具体内容如下基本功能:输入图片的url然后点击按钮加载出来图
- webclient在调用DownloadData或者DownloadString的时候请求回来的数据出现乱码问题,解决办法如下:1、设置we
- 本篇主要总结下Spring容器在初始化实例前后,提供的一些回调方法和可扩展点。利用这些方法和扩展点,可以实现在Spring初始化实例前后做一
- 解决Spring in action @valid验证不生效按照书上的示例代码来实现但是,添加了验证但是没有生效。Spring提供了校验Ap
- Room其实就是一个orm,抽象了SQLite的使用,但是它作为Android的亲儿子orm,并且原生支持LiveData和Rxjava嵌套
- mybatis项目CRUD步骤1.pom.xml引入相应的依赖<?xml version="1.0" encodi
- 为了学习数据库,重装了系统,之前前一直在用eclipse,现在准备换成myeclipse,这之前当然需要重新设置环境变量,顺手写下有关jdk
- 前段时间做了一个练手的小项目,名叫Book_Bar,用来卖书的,采用的是三层架构,也就是Models,IDAL,DAL,BLL 和 Web
- package com.videobackend.controller;import java.io.File;import java.io
- 一直对invoke和begininvoke的使用和概念比较混乱,这两天看了些资料,对这两个的用法和原理有了些新的认识和理解。 首先
- 一、了解Spring自动装配的方式采用传统的XML方式配置Bean组件的关键代码如下所示<bean id="userMapp
- 一、JNDI是什么?JNDI--Java 命名和目录接口(Java Naming and Directory Interface),是一组在
- 本文实例为大家分享了Unity苹果手机Taptic震动的具体代码,供大家参考,具体内容如下文件:ios震动.zip将上方文件解压之后将Mul
- @JSONField看源码它可以作用于字段和方法上。引用网上说的,一、作用Field@JSONField作用在Field时,其name不仅定
- 1、引例class Complex{private: double Real,Image;public: &nbs
- 申请百度地图密钥以及查看百度API网址:http://lbsyun.baidu.com/apiconsole/key#/home网址:htt
- AssertJ是我目前见过的最强大的断言api,没有之一。官网传送门为什么使用assertJ?1、流式断言,代码即用例,直观易懂。举个例子:
- 一、饿汉式(静态常量)public class Face { private stat
- 什么是 Retrofit ?Retrofit是Square开发的一个Android和Java的REST客户端库。这个库非常简单并且具有很多特