哈希表分为两大类,一是开放地址法,二是链地址法。
1)、开放地址法中,通过在哈希表中再找一个空位解决冲突问题。
2)、链地址法中,某个数据项的关键字值还是像通常一样映射到哈希表的单元,而数据项本身插入到这个单元的链表中,其他同样映射到该位置的数据项只需要加入到链表中。
链地址法Java简缩代码:
/**
* 节点类
*/
class Link{
private int data;
public Link next;
public Link(int data){
this.data = data;
this.next = null;
}
public int getKey(){
return this.data;
}
public void display(){
System.out.println(this.data);
}
}
/**
* 优先级链表
*/
class SortedList{
private Link first;
public SortedList(){
this.first = null;
}
public void insert(Link theLink){
int key = theLink.getKey();
Link current = this.first;
Link previous = null;
while (current != null && key > current.getKey()){
previous = current;
current = current.next;
}
if (previous != null){
previous.next = theLink;
}else{
this.first = theLink;
}
theLink.next = current;
}
public Link find(int key){
Link current = this.first;
while (current != null && key != current.getKey()){
current = current.next;
}
return current;
}
public void display(){
Link current = this.first;
while (current != null){
current.display();
current = current.next;
}
}
}
/**
* 链地址哈希表
*/
class HashTableLink{
private SortedList[] hashArray;
private int arraySize;
public HashTableLink(int size){
this.arraySize = size;
this.hashArray = new SortedList[this.arraySize];
for (int i = 0; i < this.arraySize; i++){
this.hashArray[i] = new SortedList();
}
}
public int keyFunc(int key){
return key % this.arraySize;
}
public void insert(Link theLink){
int key = keyFunc(theLink.getKey());
this.hashArray[key].insert(theLink);
}
public Link find(int key){
key = keyFunc(key);
return this.hashArray[key].find(key);
}
public void display(){
for (int i = 0; i < this.arraySize; i++){
System.out.println("i: " + i);
this.hashArray[i].display();
}
}
}
public class HashTableTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
HashTableLink htl = new HashTableLink(3);
for (int i = 1; i < 12; i ++){
Link link = new Link(i);
htl.insert(link);
}
htl.display();
}
}
分享到:
相关推荐
哈希表 用链地址法解决冲突:(哈希函数是按名字第一个大写字母分的) 输入内容:学生的姓名跟成绩 操作:插入、修改、查找、删除学生;以及输出哈希表
哈希表--链表 哈希表--链表 哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表
printf("请选择hash表的操作\n1.查询\t2.插入\t3.删除\t4.输出\n"); scanf("%d",&Case); switch(Case) { case 1: { printf("请输入要查询的元素:"); scanf("%d",&value); printf(search_hash(A,value,n)?...
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
哈希表 哈希表_使用Java开发的哈希表_HashTable
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2...
哈希表 哈希表_使用C语言实现哈希表数据结构_HashTable
浙大超牛老师数据结构课件,非常经典!~详细介绍了哈希表的定义,性质,基本哈希函数和哈希冲突的解决办法!
哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 测试数据 取读者周围较熟悉的30个人名。 选作内容 (1) 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数,比较...
第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19 第1章 哈希和哈希表-2020.08.19
. c实现的哈希表。哈希函数采用除留余数法,处理哈希冲突采用链地址法。包含设计文档!在dev c++上验证过。. vs2010 中有代码.有修改过一些BUG.
数据结构算法\哈希表开放地址法解决冲突
《数据结构》(C语言版本)的实验之一,哈希表设计。网上找的资源,共享。
哈希表 哈希表_使用C++实现的哈希表_HashTable
哈希表的设计与实现——链地址法 问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立...
数据结构中的哈希表查找,代码有注释,理解算法后理解代码非常容易看懂
Java版本算法练习+笔记总结 按照数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构进行系统的练习 每道题都有标号和题目链接.zip
严蔚敏 数据结构 ppt 哈希表 数 图 严蔚敏 数据结构 ppt 哈希表 数 图 严蔚敏 数据结构 ppt 哈希表 数 图
大数据结构课程设计--哈希表实验报告材料