Java数据结构之实现哈希表的分离链接法
作者:TanGBx 发布时间:2023-09-06 04:50:17
哈希表的分离链接法
原理
Hash Table可以看作是一种特殊的数组。他的原理基本上跟数组相同,给他一个数据,经过自己设置的哈希函数变换得到一个位置,并在这个位置当中放置该数据。哦对了,他还有个名字叫散列
0 | 1 |
数据1 | 数据2 |
就像这个数组,0号位置放着数据1,1号位置放数据2
而我们的哈希表则是通过一个函数f(x) 把数据1变成0,把数据2变成1,然后在得到位置插入数据1和数据2。
非常重要的是哈希表的长度为素数最好!!
而且当插入数据大于一半的时候我们要进行扩充!!!
冲突问题产生
现在这个表就是2个数据,所以不会产生什么冲突,但是若一个数据他通过f(x)计算得到的位置也是0呢?是不是就跟数据1产生了冲突,因为数据1已经占据了这个位置,你无法进行插入操作。对不对。
所以我们该如何解决这个问题呢,诶,我们肯定是想两个都可以插入是不是,就像一个炸串一样把他串起来。如图
a b c就像一个炸串,而如何实现这个炸串就有多种方式。这里我们用线性表来实现
线性表实现
我们可以用java自带的List ArrayList等表,这边也给出单链表的实现方式。
public class MyArray<AnyType> {
我们首先得创建一个内部类用来存放数据,以及保存下个节点
class ArrayNode<AnyType>{
public AnyType data;
public ArrayNode<AnyType> next;
public ArrayNode(AnyType data){this(data,null);}
private ArrayNode(AnyType data,ArrayNode<AnyType> next){
this.data=data;
this.next=next;
}
}//save type node;
设置我们这个线性表所需要的对象,例如size和一个头节点,以及我们要进行初始化,判断这个表是否为空等。
private int theSize;//array list size
private ArrayNode<AnyType> head; //head node every data behind it
//init MyArray
public MyArray(){doClear();}
public void clear(){doClear();}
private void doClear(){
theSize=0;
head=new ArrayNode<>(null);
}
//get size and is empty
public int size(){return theSize;}
public boolean isEmpty(){return theSize==0;}
接下来我们需要实现他的基本操作,是否包含,插入,获得以及删除。
//contain
public boolean contains(AnyType x){
ArrayNode<AnyType> newNode=head;//get a new node=head
while (newNode.next!=null) {
newNode=newNode.next;
if (newNode.data == x)
return true;
}
return false;
}
//get the data in idx from array
public AnyType get(int idx){return get(idx,head).data;}
private ArrayNode<AnyType> get(int idx,ArrayNode<AnyType> node){
if(idx<0||idx>size())
throw new IndexOutOfBoundsException();//out of length
ArrayNode<AnyType> newNode=node;
//find start head.next
for (int i = 0; i < idx; i++)
newNode=newNode.next;
return newNode;
}
//set data into array
public void set(AnyType x){set(x,head);}
private void set(AnyType x,ArrayNode<AnyType> node){
ArrayNode<AnyType> newNode=node;
while (newNode.next!=null)
newNode=newNode.next;
theSize++;
newNode.next=new ArrayNode<>(x);
}
//remove
public void remove(AnyType x){remove(x,head);}
private void remove(AnyType x,ArrayNode<AnyType> node){
if(!contains(x))
return;
while (node.next!=null){
node=node.next;
if (node.next.data==x)
break;
}
ArrayNode<AnyType> oldNode=node.next;
node.next=null;
node.next=oldNode.next;
}
}
哈希表实现
public class MyHashTable<AnyType>{
//define the things that we need to use
private static final int DEFAULT_SIZE = 10;
private MyArray<AnyType>[] arrays;
private int currentSize;
因为我实现的是学号的存储
也就是带0开头的数据 所以我用字符串
这里这个myHash就是我实现的简单哈希函数,即获得的数据字符串化,得到最后两个字符
private int myHash(AnyType x){
String s=x.toString();
return Integer.parseInt(s.substring(s.length()-2,s.length()));
}
初始化哈希表,设置的默认大小为10,然后进行素数判断,如果它不是素数,那么就找到他的下一个素数作为表的大小。
//init we should ensure that the table size is prime
public MyHashTable(){
ensureTable(nextPrime(DEFAULT_SIZE));
makeEmpty();
}
private void ensureTable(int x){
arrays=new MyArray[x];
for (int i = 0; i < arrays.length; i++)
arrays[i]=new MyArray<>();
}
//make the array empty
public void makeEmpty(){
currentSize=0;
for(MyArray<AnyType> myArray:arrays)
myArray.clear();
}
//size and empty
public int size(){return currentSize;}
public boolean isEmpty(){return currentSize==0;}
基本方法的实现,插入,获得,删除,包含
//contain x
public boolean contains(AnyType x){
int position=myHash(x);
return arrays[position].contains(x);
}
//insert x
public void insert(AnyType x){
int position=myHash(x);
if(arrays[position].contains(x))
return;
else if(arrays[position].size()==0)
if(++currentSize>arrays.length)
makeBigger();
arrays[position].set(x);
}
//get idx data
public MyArray<AnyType> get(int idx){ return arrays[idx];}
在这里,如果插入的时候啦,实际的currentSize大于二分之一表的大小了
则进行扩充表
一般扩充表的话,我们是直接两倍两倍扩充的。
//makeBigger
public void makeBigger() {
MyArray[] oldArray = arrays;
arrays = new MyArray[2 * arrays.length];
for (int i = 0; i < oldArray.length; i++)
arrays[i] = oldArray[i];
}
下一个素数查找,如果他是偶数,则给他加1这样可以大大减少开销。
然后进行下一个素数判断,奇数当中找素数。
//nextPrime
private int nextPrime(int i){
if(i%2==0)
i++;
for (; !isPrime(i); i+=2);//ensure i is jishu
return i;
}
是否为素数判断,如果为2则范围true
如果是1或者为偶数则返回false
都不满足则从三开始,他的平方小于输入的数,用奇数进行操作,因为用偶数的话,前面那个2就直接判断了,所以我们用奇数,大大减少开销。
我们也可以设置他的判断条件是小于输入的二分之一,但是我们用平方进行判断大大减少了开销,而且对于奇数来说是十分有效果的。
//is Prime
private boolean isPrime(int i){
if(i==2||i==3)
return true;
if(i==1||i%2==0)
return false;
for (int j = 3; j*j<=i ; j+=2)
if (i%j==0)
return false;
return true;
}
}
测试
public class test {
public static void main(String[] args) {
MyHashTable<String> a=new MyHashTable<>();
a.insert("001");
a.insert("01");
for(int i=1;i<a.get(1).size()+1;i++){
System.out.println(a.get(1).get(i));
}
}
}
结果
来源:https://blog.csdn.net/TanGBx/article/details/117906761
猜你喜欢
- spring security用了也有一段时间了,弄过异步和多数据源登录,也看过一点源码,最近弄rest,然后顺便搭oauth2,前端用js
- 在windows环境下,我们通常在IDE如VS的工程中开发C++项目,对于生成和使用静态库(*.lib)与动态库(*.dll)可能都已经比较
- C#过滤DataTable中的空数据和重复数据string sql = "select name,age from user&qu
- 一.导入Netty依赖<dependency> <groupId>io.netty</group
- SSO :同一个帐号在同一个公司不同系统上登陆 使用SpringSecurity实现类似于SSO登陆系统是十分简单的 下面我就搭
- 运行下面这段代码,观察其结果:package com.test;public class HelloB extends HelloA {pu
- fifter、servlet、interceptorfifter用来处理请求头、请求参数、编码的一些设置,然后转交给servlet,处理业务
- 输入方法第一种输入方法:scannerimport java.util.Scanner; // 导入java.util.Scannerpub
- 下面我们就字符串连接方面分析。1.String打开String的源码,如图所示会发现存储字符串的字符数值是final常量。再看String的
- 本文实例为大家分享了java模拟斗地主发牌的具体代码,供大家参考,具体内容如下1.案例介绍规则:组装54张扑克牌54张牌顺序打乱三个玩家参与
- 一、添加数据1、在主表中添加从表数据在景点的住宿集合(Lodgings)中增加一个度假区(Resort)var dest = (from d
- 命令行编译java文件import java.util.*;public class shuchu{ public
- 读写锁:分为读锁和写锁,多个读锁不互斥,读锁与写锁互斥,这是由jvm自己控制的,你只要上好相应的锁即可。如果你的代码只读数据,可以很多人同时
- Object是所有类的父类,也就是说java中所有的类都是直接或者间接继承自Object类。比如你随便创建一个classA,虽然没有明说,但
- AbstractDetectingUrlHandlerMapping是通过扫描方式注册Handler,收到请求时由Abstrac
- idea这个工具真的很好 很强大。而且非常的好用。用过idea的人,估计都不想用eclipse了。idea这个工具虽然好用,但是对硬件还是有
- 很久以来都想研究一下利用java操作Excel的方法,今天没事,就稍微了解了一下,特总结一下。利用java操作Excel,有个开源的东东-j
- 1. 运行环境 Enviroment当 MyBatis 与不同的应用结合时,需要不同的事务管理机制。与 Spring 结合时,由 Sprin
- class文件中的常量池之前我们在讲class文件的结构时,提到了每个class文件都有一个常量池,常量池中存了些什么东西呢?字符串常量,类
- 本文实例讲述了Java编程调用微信分享功能。分享给大家供大家参考,具体如下:这篇文章介绍如何使用java开发微信分享功能,因为工作,已经开发