详解如何使用java实现Open Addressing

你好！ 我们这里总共向您提供三种open addression的方法，分别为linear probing、quadratic probing和double hashing。

Linear Probing

Linear probing是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对，并且能通过给出的键来查找表中对应的值。Linear probing这种策略是在1954年由Gene Amdahl, Elaine M. McGraw,和 Arthur Samuel 所发明，并且最早于1963年由Donald Knuth对其进行分析。

  • 假设A是哈希表的一个容量N为15的数组；
  • 将Keys（5、9、12、24、31、40、47、53、62、71）使用linear probing按照顺序依次插入到数组中。
public static void main(String[] args) {
 int N = 15;
 int[] A = new int [N];
 int[] Keys = {5, 9, 12, 24, 31, 40, 47, 53, 62, 71};

 for (int i = 0; i < Keys.length; i++) {
  int j = 0;
  int Position = Keys[i] % N;
  while (A[Position] != 0) {
  j = j + 1;
  Position = Keys[i] % N + j;
  }
  A[Position] = Keys[i];
 }
 for (int i = 0; i < A.length; i++) {
  System.out.println(A[i]);
 }
 }

Quadratic Probing

Quadratic probing是计算机程序解决散列表冲突时所采取的另一种策略，用于解决散列表中的冲突。Quadratic probing通过获取原始哈希索引并将任意二次多项式的连续值相加，直到找到一个空槽来进行操作。

  • 假设A是哈希表的一个容量N为15的数组；
  • 将Keys（5、9、12、24、31、40、47、53、62、71）使用quadratic probing按照顺序依次插入到数组中。
public static void main(String[] args) {
 int N = 15;
 int[] A = new int [N];
 int[] Keys = {5, 9, 12, 24, 31, 40, 47, 53, 62, 71};

 for (int i = 0; i < Keys.length; i++) {
  int j = 0;
  int Position = Keys[i] % N;
  while (A[Position] != 0) {
  j = j + 1;
  Position = (Keys[i] % N + j*j) % N;
  }
  A[Position] = Keys[i];
 }
 for (int i = 0; i < A.length; i++) {
  System.out.println(A[i]);
 }
 }

Double Hashing

Double hashing是计算机程序解决散列表冲突时所采取的另一种策略，与散列表中的开放寻址结合使用，通过使用密钥的辅助哈希作为冲突发生时的偏移来解决哈希冲突。具有open addressing的double hashing是表上的经典数据结构。

  • 假设A是哈希表的一个容量N为15的数组；
  • 将Keys（5、9、12、24、31、40、47、53、62、71）使用double hashing（我们假设h'(k)为13 - (k mod 13)）按照顺序依次插入到数组中。
public static void main(String[] args) {
 int N = 15;
 int[] A = new int [N];
 int[] Keys = {5, 9, 12, 24, 31, 40, 47, 53, 62, 71};

 for (int i = 0; i < Keys.length; i++) {
  int j = 0;
  int Position = (Keys[i] % N + (13 - (Keys[i] % 13)) * j) % N;
  while (A[Position] != 0) {
  j = j + 1;
  Position = (Keys[i] % N + (13 - (Keys[i] % 13)) * j) % N;
  }
  A[Position] = Keys[i];
 }
 for (int i = 0; i < A.length; i++) {
  System.out.println(A[i]);
 }
 }

到此这篇关于详解如何使用java实现Open Addressing的文章就介绍到这了,更多相关java实现Open Addressing内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java中的IP地址和InetAddress类使用详解

    Java语言的优势之一是Java程序能访问网络资源.Java提供一系列的类支持Java程序访问网络资源. TCP/IP协议和IP地址 为了进行网络通信,通信双方必须遵守通信协议.目前最广泛使用的是TCP/IP协议,它是Internet中各方所遵循的公共协议.TCP(Transport Control Protocol)是一种传输控制协议,IP(Internet Protocol)是一种网际协议,TCP/IP代表这两个协议的. TCP/IP分为四个层次: 网络接口层:负责接收和发送物理帧: 网络层

  • Java编程中利用InetAddress类确定特殊IP地址的方法

    InetAddress类 InetAddress类用来封装我们前面讨论的数字式的IP地址和该地址的域名. 你通过一个IP主机名与这个类发生作用,IP主机名比它的IP地址用起来更简便更容易理解. InetAddress类内部隐藏了地址数字. InetAddress类中的工厂方法 InetAddress类没有明显的构造函数.为生成一个InetAddress对象,必须运用一个可用的工厂方法. 工厂方法(factory method)仅是一个类中静态方法返回一个该类实例的约定. 对于InetAddres

  • Java输出通过InetAddress获得的IP地址数组详细解析

    使用 InetAddress 获取 IP 地址会得到一个 byte 数组如果你直接输出这个数组,你会发现 IP 地址中的某些位变成了负数比如 61.135.169.105 会输出成 61.-121.-87.105仔细看一看,会发现 135 + 121 = 256,169 + 87 = 256 -_-! 怎么个情况! 我首先想到的是 byte 类型向 int 类型转换过程中出现了问题,后来发现,实际不然 因为 Java 中没有 unsigned 类型,所以byte.short.int.long 都

  • 详解如何使用java实现Open Addressing

    你好! 我们这里总共向您提供三种open addression的方法,分别为linear probing.quadratic probing和double hashing. Linear Probing Linear probing是计算机程序解决散列表冲突时所采取的一种策略.散列表这种数据结构用于保存键值对,并且能通过给出的键来查找表中对应的值.Linear probing这种策略是在1954年由Gene Amdahl, Elaine M. McGraw,和 Arthur Samuel 所发明

  • Java构造方法实例详解(动力节点java学院整理)

    Java构造方法实例详解(动力节点java学院整理)

    构造函数是一种特殊的函数.其主要功能是用来在创建对象时初始化对象, 即为v对象成员变量赋初始值,总与new运算符一起使用在创建对象的语句中.构造函数与类名相同,可重载多个不同的构造函数.在JAVA语言中,构造函数与C++语言中的构造函数相同,JAVA语言中普遍称之为构造方法. 使用构造器时需要记住: 1.构造器必须与类同名(如果一个源文件中有多个类,那么构造器必须与公共类同名) 2.每个类可以有一个以上的构造器 3.构造器可以有0个.1个或1个以上的参数 4.构造器没有返回值 5.构造器总是伴随

  • Java类的继承实例详解(动力节点Java学院整理)

    Java类的继承实例详解(动力节点Java学院整理)

    一.你了解类吗? 在Java中,类文件是以.java为后缀的代码文件,在每个类文件中最多只允许出现一个public类,当有public类的时候,类文件的名称必须和public类的名称相同,若不存在public,则类文件的名称可以为任意的名称(当然以数字开头的名称是不允许的). 在类内部,对于成员变量,如果在定义的时候没有进行显示的赋值初始化,则Java会保证类的每个成员变量都得到恰当的初始化: 1)对于  char.short.byte.int.long.float.double等基本数据类型的

  • 详解springSecurity之java配置篇

    一 前言 本篇是springSecurity知识的入门第二篇,主要内容是如何使用java配置的方式进行配置springSeciruty,然后通过一个简单的示例自定义登陆页面,覆盖原有springSecurity默认的登陆页面:学习这篇的基础是 知识追寻者之前发布 过 的<springSecurity入门篇> 二 java配置 2.1配置账号密码 如下所示, 使用 @EnableWebSecurity 在配置类上开启security配置功能: 在配置类中定义bean 名为 UserDetails

  • 详解如何将JAVA程序制作成可以直接执行的exe文件

    突然心血来潮,想自己做个小程序玩玩,但是怎么把他做成一个exe文件,让大家能够更好的理解和使用呢,百度了一下,说是需要exe4j来生成,但是看了很多关于exe4j将java程序生成exe文件的教程,觉着都不是自己想要的结果,还是自己综合一下,写篇文章记录一下. 下载和安装的步骤我就略过了,直接说重点. 一 : 将写好的java程序打成jar包,如下图: 1: . 2: 3: 4: 5:此处填写MANIFEST.MF文件路径,MANIFEST.MF手动创建后放在下项目路径下即可 MANIFEST.

  • 详解如何把Java中if-else代码重构成高质量代码

    为什么我们写的代码都是if-else? 程序员想必都经历过这样的场景:刚开始自己写的代码很简洁,逻辑清晰,函数精简,没有一个if-else, 可随着代码逻辑不断完善和业务的瞬息万变:比如需要对入参进行类型和值进行判断:这里要判断下对象是否为null:不同类型执行不同的流程. 落地到具体实现只能不停地加if-else来处理,渐渐地,代码变得越来越庞大,函数越来越长,文件行数也迅速突破上千行,维护难度也越来越大,到后期基本达到一种难以维护的状态. 虽然我们都很不情愿写出满屏if-else的代码,可逻

  • 详解怎么用Java的super关键字

    详解怎么用Java的super关键字

    Java的super关键字 当子类重写父类的方法后,子类对象将无法直接访问父类被重写的方法.为了解决这个问题,在Java中专门提供了一个super关键字来访问父类的成员,例如访问父类的成员变量.成员方法和构造方法.下面分两种情况来学习一下super关键字的具体用法. (1)使用super关键字调用父类的成员变量和成员方法,具体格式如下: super.成员变量 super.成员方法([参数1,参数2...]) 接下来通过一个案例来学习如何使用super关键字调用父类的成员变量和成员方法,如文件1所

  • 详解如何在Java中调用Python程序

    Java中调用Python程序 1.新建一个Maven工程,导入如下依赖 <dependency> <groupId>org.python</groupId> <artifactId>jython-standalone</artifactId> <version>2.7.0</version> </dependency> 2.在java中直接执行python代码片段 import org.python.util

  • 详解如何在Java中实现堆排序算法

    目录 算法描述 实现代码 测试代码 算法描述 堆排序算法的描述如下: 将待排序的数组调整为最大堆,此时未排序的长度 N 为数组的长度,调整的过程就是倒序将数组的前 N/2 个元素下沉的过程,每次下沉都会将较大的元素带到上面,最终将数组变为最大堆: 弹出最大堆的堆顶元素并将其移动到数组的最后面,将原本最后面的元素放到堆顶,然后将未排序的长度 N - 1,调整数组的前 N 个元素为最大堆: 重复步骤 2 直到未排序的长度为 0. 实现代码 package com.zhiyiyo.collection

  • 详解如何在Java中加密和解密zip文件

    目录 依赖 压缩一个文件 压缩多个文件 压缩一个目录 创建一个分割的压缩文件 提取所有文件 提取单个文件 总结 依赖 让我们先把 zip4j 依赖关系添加到我们的 pom.xml 文件中. <dependency>     <groupId>net.lingala.zip4j</groupId>     <artifactId>zip4j</artifactId>     <version>2.9.0</version>

随机推荐