本来已经躺在床上准备呼呼大睡了,突然想到hash表的博客还没发表,于是大半夜爬了起来发了这篇文章,希望没有扰人清梦就好了。本来一直以为是早就发了的,然后今天晚上躺在床上才忽然意识到还没有发,最近过的有点浑浑噩噩的,悲剧啊。
这个代码是自己模拟哈希表实现的一个简单的学生统计系统,具体是实现的散列表中的开散列,即用数组保存一组数据,这一组数据中通过链表连结彼此,于是达到增加,查找,替换,删除的功能。
hash的预映射算法比较简单,即将学生学号的各个位相加,得到的个位数数值即为散列值,因为个位数所以数组大小为10.
private int handdata(Student stu) {
int num = stu.numb;
while (num > 9) {//循环运算直到num变为个位数
num = num / 10000 + num % 10000 / 1000 + num % 1000 / 100 + num
% 100 / 10 + num % 10;//将各个位的值相加的运算
}
return num;
}
接下来要设计学生的类,这也是hash表中数组中保存的对象的类。
public class Student {
public String name="11";
public int numb=11111;
public int gride=11;
public Student before=null;
public Student next=null;
/**
* 重新构造方法以传入数值
* @param name
* @param numb
* @param gride
*/
public Student(String name,int numb,int gride){
this.name=name;
this.gride=gride;
this.numb=numb;
}
//这个构造方法用来实现默认的对象
public Student(){
}
//改变对象下一个和上一下结点的方法
public void changenext(Student s){
next=s;
}
public void changebefore(Student s){
before=s;
}
}
创建hash表和向其中加入元素的方法
这里要注意的是在加入新对象时记得去掉默认的对象
/**
* 创建hash表的方法
* @param stu
*/
public void createHash(Student stu) {
for (int i = 0; i < 10; i++) {
Student st = new Student();
hash[i] = st;
}//首先默认对数组每个下标值对应的加入一个对象
int hashcode = handdata(stu);//获得散列值
hash[hashcode] = stu;//加入对象
}
/**
* 向hash表内加入元素的方法
* @param stu
*/
public void addHash(Student stu) {
int hashcode = handdata(stu);
if (hash[hashcode] == null) {
hash[hashcode] = stu;
} else {//如果此散列值对应的不为空,那么去掉默认的对象(如果有),加入新对象
Student stut = hash[hashcode];
if (stut.name.equals("11")) {
hash[hashcode] = stu;
} else {
while (stut.next != null) {
stut = stut.next;
}
stut.next = stu;
}
}
}
查找表中已存在的元素很简单,即将它的学号处理得到散列值然后遍历hash表即可(这里给予的值可以是学生类的对象,也可以是学生的学号,大体上没什么区别)
public Student seekHash(Student stu) {
int hashcode = handdata(stu);
Student stu2 = hash[hashcode];
while (stu2.numb != stu.numb) {//反复查找直到找到对应的对象
stu2 = stu2.next;
}
System.out.println("姓名:" + stu2.name + "\t学号:" + stu2.numb + "\t分数:"
+ stu2.gride);
System.out.println("查找完成。");
return stu2;
}
替换表中元素和删除表中元素其实差不多,都是找到这个对象然后改变它父结点和子结点中指针的指向来达到目的的,其中要注意的就是找到的这个结点可能没有父结点或子结点,这时需要分开讨论(由于删除牵涉到2个需要讨论的结点之间的操作,所以比替换略复杂)
/**
* 替换hash表元素的方法
*
* @param stu1
* @param stu2
*/
public void changeHash(Student stu1, Student stu2) {
int hashcode = handdata(stu1);
Student stu = seekHash(stu1);
if (stu.before != null) {//分before和next讨论
Student stu3 = stu.before;
stu3.next = stu2;
stu2.before = stu3;
} else {
hash[hashcode] = stu2;
}
if (stu.next != null) {
Student stu4 = stu.next;
stu4.before = stu2;
stu2.next = stu4;
}
}
/**
* 删除hash表元素的方法
*
* @param stu
*/
public void deleteHash(Student stu) {
int hashcode = handdata(stu);
Student stu0 = seekHash(stu);
if (stu0.before != null && stu0.next != null) {//各种讨论
Student stu1 = stu0.before;
Student stu2 = stu0.next;
stu1.next = stu2;
stu2.before = stu1;
} else if(stu0.before == null && stu0.next == null){
hash[hashcode] = new Student();
}else if(stu0.before == null && stu0.next != null){
Student stu3=stu0.next;
stu3.before=null;
}else if(stu0.before != null && stu0.next == null){
Student stu4=stu0.before;
stu4.next=null;
}
}
以上就是我的简单的开散列,下面附上实例结果,分别为创建添加,替换,删除后的遍历结果(查找已在替换和删除中体现)
引用
数组第0个中的元素:
姓名:lihao1 学号:0 分数:87
数组第1个中的元素:
姓名:lihao2 学号:1 分数:86
姓名:lihao3 学号:1 分数:85
数组第2个中的元素:
姓名:lihao4 学号:2 分数:84
数组第3个中的元素:
姓名:11 学号:11111 分数:11
数组第4个中的元素:
姓名:11 学号:11111 分数:11
数组第5个中的元素:
姓名:11 学号:11111 分数:11
数组第6个中的元素:
姓名:11 学号:11111 分数:11
数组第7个中的元素:
姓名:11 学号:11111 分数:11
数组第8个中的元素:
姓名:11 学号:11111 分数:11
数组第9个中的元素:
姓名:11 学号:11111 分数:11
一次遍历完成。
姓名:lihao4 学号:2 分数:84
一次查找完成。
数组第0个中的元素:
姓名:lihao1 学号:0 分数:87
数组第1个中的元素:
姓名:lihao2 学号:1 分数:86
姓名:lihao3 学号:1 分数:85
数组第2个中的元素:
姓名:lihao5 学号:2 分数:88
数组第3个中的元素:
姓名:11 学号:11111 分数:11
数组第4个中的元素:
姓名:11 学号:11111 分数:11
数组第5个中的元素:
姓名:11 学号:11111 分数:11
数组第6个中的元素:
姓名:11 学号:11111 分数:11
数组第7个中的元素:
姓名:11 学号:11111 分数:11
数组第8个中的元素:
姓名:11 学号:11111 分数:11
数组第9个中的元素:
姓名:11 学号:11111 分数:11
一次遍历完成。
姓名:lihao5 学号:2 分数:88
一次查找完成。
数组第0个中的元素:
姓名:lihao1 学号:0 分数:87
数组第1个中的元素:
姓名:lihao2 学号:1 分数:86
姓名:lihao3 学号:1 分数:85
数组第2个中的元素:
姓名:11 学号:11111 分数:11
数组第3个中的元素:
姓名:11 学号:11111 分数:11
数组第4个中的元素:
姓名:11 学号:11111 分数:11
数组第5个中的元素:
姓名:11 学号:11111 分数:11
数组第6个中的元素:
姓名:11 学号:11111 分数:11
数组第7个中的元素:
姓名:11 学号:11111 分数:11
数组第8个中的元素:
姓名:11 学号:11111 分数:11
数组第9个中的元素:
姓名:11 学号:11111 分数:11
一次遍历完成。
分享到:
相关推荐
C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。
stm32f407平台上实现的hash算法
c语言hash表源码 来自于开源软件项目
从linux内核提取出来的,双向链表和hash表实现。在普通的用户态C程序中,均可使用
自己实现的hash表,自己的hash函数,优化了的内存管理
Hash表应用 (必做) (查找) [问题描述] 设计散列表实现身份证查找系统,对身份证号进行Hash。 [基本要求] (1) 设每个记录有下列数据项:身份证号码(虚构,位数和编码规则与真实一致即可)、姓名、地址; ...
C++写的hash表模板类,效率还是很不错的。另付有测试代码和可运行文件
Hash分区是Oracle实现表分区的三种基本分区方式之一。对于那些无法有效划分分区范围的大表,或者出于某些特殊考虑的设计,需要使用Hash分区,下面介绍使用方法
打造最快的Hash表.doc 据说来自暴雪 nop nop nop nop
hash表操作函数 HASH_ADD_INT HASH_ADD_STR
封装hashtable的两级hash表,两个键值索引和访问。适合存放稀疏数据,如稀疏矩阵,稀疏表等结构,由于提供key-value的索引遍历,数据稀疏的情况下,相比于传统矩阵遍历的速度更快。
该文档消息描述了hash表的创建、数据插入、数据删除、数据查找以及hash表销毁等操作
简单的hash学习程序。 关于Hash的详细介绍请见我的文章http://blog.csdn.net/yankai0219/article/details/8185796
sfxhash 链式hash表 sfxhash 链式hash表 sfxhash 链式hash表 sfxhash 链式hash表 sfxhash 链式hash表
基于HASH表和SYN计算的TCP包重组方法.rar
base64加解密, hash表, fnmatch的windows下的实现简单实现版本。是从mosquitto的auth_plug中copy和https://blog.csdn.net/tttmt/article/details/24824291?utm_source=blogxgwz8 看到的 c语言代码。在qt上测试了
hash表的源代码#include <stdio.h> /*标准输入输出函数库*/ #include<stdlib.h> /*标准函数库*/ #include<string.h> #define HASH_LEN 50 /*哈希表的长度 */ #define M 47 #define NAME_N 30 /*人名拼音的最大个...
Hash表采用了数组加链表的结构,即一个数组元组中不再是存储单个元素,而是存储一个链表,就好比包租婆收租的时候,一个握把上面挂了一连串的钥匙一样。Hash表的引出是为了减少查询数据库操作所带来的时间问题,将...
数据更新于:2020年11月06日 ,包含4个json(省级、地级、县级、乡级),3个整理后的txt,1个java文件 带注释,具体可看文章:https://mp.csdn.net/editor/html/115234415