Java 散列存储详解及简单示例

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()方法必须严格地判断两个对象是否相同。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • java实现文件保存到本地的方法

    本篇介绍了java实现文件保存到本地的方法,具体代码如下: private void savePic(InputStream inputStream, String fileName) { OutputStream os = null; try { String path = "D:\\testFile\\"; // 2.保存到临时文件 // 1K的数据缓冲 byte[] bs = new byte[1024]; // 读取到的数据长度 int len; // 输出的文件流保存到本地文

  • Java将文件分割为多个子文件再将子文件合并成原始文件的示例

    Java将文件分割为多个子文件再将子文件合并成原始文件的示例,废话不多说,代码如下: import java.io.File; import java.io.InputStream; import java.io.FileInputStream; import java.io.OutputStream; import java.io.FileOutputStream; import java.util.Properties; import java.util.Iterator; import j

  • 详解Java中“==”与equals()的区别

    Java中"=="与equals()的区别 对于关系操作符"==",<Java编程思想>中是这样描述的:"关系操作符生成的是一个boolean结果,它们计算的是操作数的值之间的关系".这里的操作数的"值"值得我们注意.对于8种基本数据类型(boolean,byte,char,short,int,float,double,long),它们的变量直接存储的就是"值".所以,我们用"==&q

  • java HashMap内部实现原理详解

    java HashMap内部实现原理详解

    详解HashMap内部实现原理 内部数据结构 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; 从上面的数据结构定义可以看出,HashMap存元素的是一组键值对的链表,以什么形式存储呢 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABL

  • Java中包装类介绍与其注意事项

    Java中包装类介绍与其注意事项

    前言 大家都知道在Java中,除了8种基本数据类型外,其他的都是引用类型.使用引用类型是为了更好地贯彻面向对象的思想,那为什么还要保留8种基本数据类型呢? 这其实更多地是照顾程序员的习惯.为了既照顾程序员的习惯,同时又能全面贯彻面向对象编程的思想,Java中引入了包装类机制. 所谓的包装类就是为8种基本数据类型分别定义了相应的引用类型,其对应关系如下: 显然,除了int及char外,其余的包装类都是将对应的基本数据类型的首字母大写即可. 那为什么要引入包装类呢?前面已经说过,是为了全面贯彻面向对

  • java计算给定字符串中出现次数最多的字母和该字母出现次数的方法

    本文实例讲述了java计算给定字符串中出现次数最多的字母和该字母出现次数的方法.分享给大家供大家参考,具体如下: import Java.util.Collections; import java.util.Map; import java.util.TreeMap; public class TestStringSplict { public static void main(String[] args){ String str = "aaaaaaacccccccccccccccccccccc

  • Java中基于maven实现zxing二维码功能

    maven所需jar <dependency> <groupId>com.google.zxing</groupId> <artifactId>core</artifactId> <version>3.0.0</version> </dependency> <dependency> <groupId>com.google.zxing</groupId> <artifac

  • Java之Spring AOP 实现用户权限验证

    Java之Spring AOP 实现用户权限验证

    每个项目都会有权限管理系统 无论你是一个简单的企业站,还是一个复杂到爆的平台级项目,都会涉及到用户登录.权限管理这些必不可少的业务逻辑.有人说,企业站需要什么权限管理阿?那行吧,你那可能叫静态页面,就算这样,但你肯定也会有后台管理及登录功能. 每个项目中都会有这些几乎一样的业务逻辑,我们能不能把他们做成通用的系统呢? AOP 实现用户权限验证 AOP 在实际项目中运用的场景主要有权限管理(Authority Management).事务管理(Transaction Management).安全管

  • java 中modCount 详解及源码分析

    modCount到底是干什么的呢 在ArrayList,LinkedList,HashMap等等的内部实现增,删,改中我们总能看到modCount的身影,modCount字面意思就是修改次数,但为什么要记录modCount的修改次数呢? 大家发现一个公共特点没有,所有使用modCount属性的全是线程不安全的,这是为什么呢?说明这个玩意肯定和线程安全有关系喽,那有什么关系呢 阅读源码,发现这玩意只有在本数据结构对应迭代器中才使用,以HashMap为例: private abstract clas

  • java Socket UDP实例详解

    UDP编程示例 服务器端: package socket; import java.io.IOException; import java.net.DatagramPacket; import java.net.DatagramSocket; import java.net.SocketException; public class UDPServer { public static void main(String[] args) throws IOException { byte[] buf

  • java实现字符串和日期类型相互转换的方法

    本文实例讲述了java实现字符串和日期类型相互转换的方法.分享给大家供大家参考,具体如下: Date inDate = new Date(); //获取当前日期 //建立一个一定格式的 SimpleDateFormat SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss"); String date = f.format(inDate); //将Date转化为字符串 System.out.println(date

随机推荐