当前位置：首页 > 编程日记 > 正文

用开放地址法中的线性探查法解决冲突实现哈希表的运算

编程日记 2024-10-07 02:20:00

为了更深的理解哈希算法，自己写了用开放地址法中的线性探查法解决冲突实现哈希表的运算。

/*** Created by lirui on 14-8-13.* 用开放地址法中的线性探查法解决冲突实现哈希表的运算。*/
public class MyHashSearch {public static final int SIZE = 10;public static final int NULLKEY = -1;public static final int DELKEY = -2;public static MyHashTable[] hashTables1 = new MyHashTable[SIZE];// 记录hash表中的数量。public static int count = 0;// 哈希函数  h(key)= key mod ppublic static int hashFunction(int key, int p) {return key % p;}// 解决冲突的函数public static int ConlictFunction(int adress) {return (adress + 1) % SIZE;}/*** @param hashTables* @param p          选择的那个被除数  h(key)= key mod p  h(key)代表地址* @param key        要查的关键字* @return*/public static int searchHT(MyHashTable[] hashTables, int p, int key) {int i = 0, adr;adr = hashFunction(key, p);while (hashTables[adr].key != NULLKEY && hashTables[adr].key != key) {i++;adr = ConlictFunction(adr);}if (hashTables[adr].key == key) {return adr;} else {return -1;}}public static int deleteHT(MyHashTable[] myHashTables, int p, int key) {int adr;adr = searchHT(myHashTables, p, key);if (adr != -1) {myHashTables[adr].key = DELKEY;count--;return 1;} else {return 0;}}// 将key插入到哈希表中public static void insertHT(MyHashTable[] hashTables, int key, int p) {int i, adr;adr = hashFunction(key, p);// 当没有冲突发生的时候if (hashTables[adr].key == NULLKEY || hashTables[adr].key == DELKEY) {hashTables[adr].key = key;hashTables[adr].findcount = 1;} else {// 如果发生了冲突i = 2;adr = ConlictFunction(adr);while (hashTables[adr].key != NULLKEY && hashTables[adr].key != DELKEY) {adr = ConlictFunction(adr);i++;}hashTables[adr].key = key;hashTables[adr].findcount = i;}count++;}/*** @param hashTables* @param x          要存入哈希表中的数组* @param m          哈希表的长度* @param p          哈希参数*/public static void createHT(MyHashTable[] hashTables, int[] x, int m, int p) {int i, length = x.length;for (i = 0; i < m; i++) {hashTables[i].key = NULLKEY;hashTables[i].findcount = 0;}for (i = 0; i < length; i++) {insertHT(hashTables, x[i], p);}}public static void main(String[] args) {MyHashTable[] hashTables1 = MyHashSearch.hashTables1;for (int i = 0; i < MyHashSearch.SIZE; i++) {hashTables1[i] = new MyHashTable();}//int[] x = {2, 49, 303, 100, 30, 1};int[] x = {7, 8, 30, 11, 18, 9 ,14};createHT(hashTables1, x, MyHashSearch.SIZE, 7);for (MyHashTable myHashTable : hashTables1) {System.out.println(myHashTable.key + "  探查次数:" + myHashTable.findcount);}System.out.println(searchHT(hashTables1, 7, 30));System.out.println(count);deleteHT(hashTables1,7,7);System.out.println(count);for (MyHashTable myHashTable : hashTables1) {System.out.println(myHashTable.key + "  探查次数:" + myHashTable.findcount);}}
}class MyHashTable {int key; // 关键字域String info; // 其他数据域int findcount;// 探查次数域MyHashTable() {}MyHashTable(int key, String info, int findcount) {this.key = key;this.info = info;this.findcount = findcount;}
}

https://www.dkcj.cn/info/21935.html

Re: 求助：5道算法题

http://www.newsmth.net/frames.html发信人: cutepig (cutepig), 信区: Algorithm标题: 求助：5道算法题发信站: 水木社区 (Sat Nov 10 18:25:06 2007), 站内1)given a integer, output its previous and next neighbor number which has the same number of bit 1…

编程日记2024/10/07 02:10:00

Linux下des对称性加密

最近对接公安审计一些经历对方的需求： 打成zip包对zip包进行des-cbc对称性加密，使用约定好的 -K和-iv值比如 -K "abcd$#!" -iv "efgh$#!"加密后做base64编码起初是想尝试用 php 去做，经过一阵折腾之后发现，p…

编程日记2024/10/07 02:00:00

在软件中常用的“撤销”操作，其本质是“栈”！

本文介绍了栈的定义与操作并利用顺序表和链表实现了栈这种常用的数据结构。

编程日记2024/10/07 01:50:00

用拉链法实现哈希算法的运算

package lirui.find;import java.util.LinkedList;/*** Created by lirui on 14-8-13.* 用拉链法实现哈希算法的运算*/ public class MyHashSearch2 {public static final int SIZE 10;public static MyHashElement[] hashtable new MyHashElement[SIZE];// 记录hash表中的数…

编程日记2024/10/07 01:40:00

C#图片处理常见方法性能比较

在.NET编程中，由于GDI的出现，使得对于图像的处理功能大大增强。在文通过一个简单黑白处理实例介绍在.NET中常见的图片处理方法和原理并比较各种方法的性能。黑白处理原理：彩色图像处理成黑白效果通常有3种算法； (1).最大值法: 使…

编程日记2024/10/07 01:30:00

软件中常用的“发送邮件”、“打印文档”，其本质是“队列”！

本图文详细介绍了顺序队列、循环队列、链队列的实现过程。

编程日记2024/10/07 01:20:00

二分查找的循环实现和递归实现

自己实现了二分查找的循环实现和递归实现说明：二分查找适用于顺序存储结构，不适于链式存储结构，是一个高效的查找方法。虽然折半查找效率高，但是要排序，排序本身是一种很费时的运算。要求传入的表是有序的。二分查找的…

编程日记2024/10/07 01:10:00

CentOS6.8 编译安装LNMP

思路：根据Linux系统以及公司网站系统的信息，选择合适的安装包进行安装一、查看系统信息 # uname -a # 查看内核/操作系统/CPU信息 # head -n 1 /etc/issue # 查看操作系统版本 # grep MemTotal /proc/meminfo # 查看内…

编程日记2024/10/07 01:00:00

js入门·循环与判断/利用函数的简单实例/使用对象/列举对象属性的名称

1,列举对象属性的名称<script language"javascript">varobjnewObject();obj.a"您好，我是田洪川";obj.b"你是田洪川咋的，不得了啊？";obj.c"西西，哈哈，我是属性 c ";//上…

编程日记2024/10/07 00:50:00

Matlab与数据结构 -- 对向量的排序

本图文介绍了Matlab怎样实现对向量的排序。

编程日记2024/10/07 00:40:00

HashMap和HashSet原理及底层实现

HashMap底层用哈希算法实现，下面看一下哈希算表的整体概括： 当map.put(“key”,”values”);的时候，底层是这样的： static final Entry<?,?>[] EMPTY_TABLE {}; transient Entry<K,V>[] table (Entry<K,V&g…

编程日记2024/10/07 00:30:00

Study on Android【三】--Intent消息传递

在前面写Android的ContentProvider时候，可以看到那是基于观察者模式的一个消息传递方法。每一个Cursor、ContentResolver做为一个小的注册中心，相关观察者可以在这个中心注册，更新消息由注册中心分发给各个观察者。而在MFC或Winform中&#x…

编程日记2024/10/07 00:20:00

Matlab与数据结构 -- 对矩阵的排序

本图文介绍了Matlab怎样实现对矩阵的排序。

编程日记2024/10/07 00:10:00

Java_中快速获取系统时间

直接调用System的currentTimeMillis()即可！ long start System.currentTimeMillis(); System.out.println("Start time : "start);

编程日记2024/10/07 00:00:00

servlet必知细节（一）

servlet必知细节（一） 今天复习了一下servlet，有过一些编程经验后，与最初学习servlet相比，对servlet理解的角度不同了，最初只是学习了如何写一个servlet，api怎么用，现在从更深处了解了…

编程日记2024/10/06 23:50:00

办公室“暧昧”的几种结局。

暧昧结局一：以消散结尾外贸公司职员小雨 p: [( I J( n, i/ L( L 那是我刚来这家公司的时候，参加面试时我就关注到其中一个面试我的男人长得不错，言谈举止也都很儒雅，所以第一面就留下了深刻印象。等到我被录取正式上班后…

编程日记2024/10/06 23:40:00

Matlab与机器学习-- 数据的归一化

本文介绍了Matlab对数据归一化的处理函数mapminmax。

编程日记2024/10/06 23:30:00

ASP.NET中的母版页

ASP.NET中的母版页添加一个"母版页",使用<asp:ContentPlaceHolder>挖坑,新建的母版页已经自动设置了两个ContentPlaceHolder创建使用母版页的具体页面,WebSite是新建"Web窗体"的时候勾选"选择模板页",WebApplication是新建"Web内容窗…

编程日记2024/10/06 23:20:00

servlet必知细节(二)--servlet执行过程

servlet必知细节(二)--servlet执行过程我们知道，servlet没有main函数，那么，servlet是怎么调用的呢？实际上，servlet 是由tomcat调用的，tomcat调用servlet程序执行。由调用栈可以看到，当一个请求…

编程日记2024/10/06 23:10:00

workerman源码分析之启动过程

2019独角兽企业重金招聘Python工程师标准>>> http://www.cnblogs.com/CpNice/p/4714182.html 转载于:https://my.oschina.net/yonghan/blog/898076

编程日记2024/10/06 23:00:00

MD5加密方法

/**//// <summary>/// 16位MD5加密方法/// </summary>/// <param name"str">原文</param>/// <returns>密文</returns>publicstaticstringgetMd5(stringstr){ MD5CryptoServiceProvider md5 new MD5CryptoServiceProvider()…

编程日记2024/10/06 22:50:00

如何教计算机认识手写数字（上）

本图文介绍了一种简单的教会计算机识别手写数字的方法。

编程日记2024/10/06 22:40:00

servlet必知细节（三）-- DefaultServlet

servlet必知细节（三）-- DefaultServlet 缺省servlet：org.apache.catalina.servlets.DefaultServlet，作用是处理其他servlet处理不到的请求我们知道，在我们工程的web.xml中，会配置servlet映射&#xff0c…

编程日记2024/10/06 22:30:00

第五篇：Visual Studio 2008 Web开发使用的新特性

第五篇：Visual Studio 2008 Web开发使用的新特性本篇翻译自MSDN。 .NET Framwork 3.5与Visual Studio 2008 包含很多新特性。AJAX的Web开发人员支持与综合查询语言（LINQ）是其中最重要的更新。此外还包含一些新的服务器端控件以及客户端对象库…

编程日记2024/10/06 22:20:00