散列查找java代码 java散列表的应用

哈希表设计的用Java代码

#include stdio.h

创新互联为企业级客户提高一站式互联网+设计服务，主要包括网站设计制作、做网站、重庆APP开发、微信小程序定制开发、宣传片制作、LOGO设计等，帮助客户快速提升营销能力和企业形象，创新互联各部门都有经验丰富的经验，可以确保每一个作品的质量和创作周期，同时每年都有很多新员工加入，为我们带来大量新的创意。 

#include string.h

#include stdlib.h

//#include

#define HASH_LEN 50 //哈希表的长度

#define M 47

#define NAME_NO 30 //人名的个数

typedef struct NAME

{

char *py; //名字的拼音

int k; //拼音所对应的整数

}NAME;

NAME NameList[HASH_LEN];

typedef struct hterm //哈希表

{

char *py; //名字的拼音

int k; //拼音所对应的整数

int si; //查找长度

}HASH;

HASH HashList[HASH_LEN];

/*-----------------------姓名（结构体数组）初始化---------------------------------*/

void InitNameList()

{

NameList[0].py="chenghongxiu";

NameList[1].py="yuanhao";

NameList[2].py="yangyang";

NameList[3].py="zhanghen";

NameList[4].py="chenghongxiu";

NameList[5].py="xiaokai";

NameList[6].py="liupeng";

NameList[7].py="shenyonghai";

NameList[8].py="chengdaoquan";

NameList[9].py="ludaoqing";

NameList[10].py="gongyunxiang";

NameList[11].py="sunzhenxing";

NameList[12].py="sunrongfei";

NameList[13].py="sunminglong";

NameList[14].py="zhanghao";

NameList[15].py="tianmiao";

NameList[16].py="yaojianzhong";

NameList[17].py="yaojianqing";

NameList[18].py="yaojianhua";

NameList[19].py="yaohaifeng";

NameList[20].py="chengyanhao";

NameList[21].py="yaoqiufeng";

NameList[22].py="qianpengcheng";

NameList[23].py="yaohaifeng";

NameList[24].py="bianyan";

NameList[25].py="linglei";

NameList[26].py="fuzhonghui";

NameList[27].py="huanhaiyan";

NameList[28].py="liudianqin";

NameList[29].py="wangbinnian";

char *f;

int r,s0;

for (int i=0;iNAME_NO;i++)

{

s0=0;

f=NameList[i].py;

for (r=0;*(f+r) != NULL;r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字

s0=*(f+r)+s0;

NameList[i].k=s0;

}

}

/*-----------------------建立哈希表---------------------------------*/

void CreateHashList()

{

for (int i=0; iNAME_NO; i ++)

{

HashList[i].py="";

HashList[i].k=0;

HashList[i].si=0;

}

for (i=0; i NAME_NO ; i++)

{

int sum=0;

int adr=(NameList[i].k) % M; //哈希函数

int d=adr;

if(HashList[adr].si==0) //如果不冲突

{

HashList[adr].k=NameList[i].k;

HashList[adr].py=NameList[i].py;

HashList[adr].si=1;

}

else //冲突

{

do{

d=(d+((NameList[i].k))%10+1)%M; //伪散列

sum=sum+1; //查找次数加1

}while (HashList[d].k!=0);

HashList[d].k=NameList[i].k;

HashList[d].py=NameList[i].py;

HashList[d].si=sum+1;

}

}

}

/*-------------------------------------查找------------------------------------*/

void FindList()

{

printf("\n\n请输入姓名的拼音: "); //输入姓名

char name[20]={0};

scanf("%s",name);

int s0=0;

for (int r=0;r20;r++) //求出姓名的拼音所对应的整数(关键字)

s0+=name[r];

int sum=1;

int adr=s0 % M; //使用哈希函数

int d=adr;

if(HashList[adr].k==s0) //分3种情况进行判断

printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);

else if (HashList[adr].k==0)

printf("无该记录!");

else

{

int g=0;

do

{

d=(d+s0%10+1)%M; //伪散列

sum=sum+1;

if (HashList[d].k==0)

{

printf("无记录! ");

g=1;

}

if (HashList[d].k==s0)

{

printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);

g=1;

}

}while(g==0);

}

}

/*--------------------------------显示哈希表----------------------------*/

void Display()

{

printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式

for(int i=0; i15; i++)

{

printf("%d ",i);

printf("\t%d ",HashList[i].k);

printf("\t\t%d ",HashList[i].si);

printf("\t\t%d ",(HashList[i].k)%M);

printf("\t %s ",HashList[i].py);

printf("\n");

}

printf("按任意键继续显示...\n"); //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）

getchar();

for( i=15; i30; i++)

{

printf("%d ",i);

printf("\t%d ",HashList[i].k);

printf("\t\t%d ",HashList[i].si);

printf("\t\t%d ",(HashList[i].k)%M);

printf("\t %s ",HashList[i].py);

printf("\n");

}

printf("按任意键继续显示...\n");

getchar();

for( i=30; i40; i++)

{

printf("%d ",i);

printf("\t%d ",HashList[i].k);

printf("\t\t%d ",HashList[i].si);

printf("\t\t%d ",(HashList[i].k)%M);

printf("\t %s ",HashList[i].py);

printf("\n");

}

printf("按任意键继续显示...\n");

getchar();

for( i=40; i50; i++)

{

printf("%d ",i);

printf("\t%d ",HashList[i].k);

printf("\t\t%d ",HashList[i].si);

printf("\t\t%d ",(HashList[i].k)%M);

printf("\t %s ",HashList[i].py);

printf("\n");

}

float average=0;

for (i=0;i NAME_NO;i ++)

average+=HashList[i].si;

average/=NAME_NO;

printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);

}

/*--------------------------------主函数----------------------------*/

void main()

{

/* ::SetConsoleTitle("哈希表操作"); //Windows API函数,设置控制台窗口的标题

HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄

::SetConsoleTextAttribute(hCon, 10|0); //设置文本颜色

*/

printf("\n------------------------哈希表的建立和查找----------------------");

InitNameList();

CreateHashList ();

while(1)

{

printf("\n\n");

printf(" 1. 显示哈希表\n");

printf(" 2. 查找\n");

printf(" 3. 退出\n");

err:

char ch1=getchar();

if (ch1='1')

Display();

else if (ch1='2')

FindList();

else if (ch1='3')

return;

else

{

printf("\n请输入正确的选择!");

goto err;

}

}

}

java中的散列码

首先，你要弄明白原因，你要明白两点：

1、你得有一定的汇编功底，了解堆和栈关系。

2、你得明白，java对像类和封装类在内存是怎么存储的。

1首先解答为什么(a == b)－"不相等"

对像类和封装类，在内存中这样存储的：

a.当new一个对像类时，就会在堆中开辟一块空间，然后，会把这个空间的地指向你new 的这个句柄，这个句柄就会放在栈中，（栈）就像个列表，CPU会向栈发送指令进行操作。（栈像一本书的目录，堆像书中的详细章节）栈中存放的对像的具体物理地址。

== ：比的是栈中的东西，a栈的内容是c8（散列码是不分正负的，内存表是1－－－11001000）

b栈的容易是c8（就是数字200的16进制，内存表是0－－－11001000）

因为（1－－－11001000）！＝（0－－－11001000）所以在堆中要分两段存储，比如堆地址为

00001000存放（1－－－11001000）为a，

堆地址为

00002000存放（0－－－11001000）为b,==比较的是00001000和00002000，所以不想等。

(String是比较特殊的对像，不是基本类型)

如果：String c = "abc";

String d = "abc";

它没有new 在定义d = "abc";的时候，因为堆中已经有"abc"了就直接把它的地址负给了d，所以

c和d的栈中存储的都是"abc"在堆中二进制地址码。所以不管是c==d还是c.equals(d)都是相等的。

equals:比较的是栈地址指向的堆中的内容是否想等。针对所有对像都有效。

比较的是（1－－－11001000）和（0－－－11001000）所表示的内容c8，所以想等。

这是有点不太好说清楚，不知道你明白了没有。

java中如何获取一个字符串的散列值?

String str = "java";

System.out.println(str.hashCode());

输出 3254818

JAVA中的散列表

散列表

（

Hash

table

，也叫

哈希表

），是根据关键码值(Key

value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做(

散列表).

hash

table

的概念！！

若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash

function)，按这个思想建立的表为

散列表

。

对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform

Hash

function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位

直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)

=

a·key

+

b，其中a和b为常数（这种散列函数叫做自身函数）

数字分析法

平方取中法

折叠法

随机数法

除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即

H(key)

=

key

MOD

p,

p=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

关于解决冲突的方法

大概有4

种，

你GOOGLE

一下，

上面有写的

，

在看下

JAVA

API

吧都有。。

Java相关：什么是散列码？

散列码就是通过一种不可逆的散列(Hash)算法，对一个数据进行计算，获得一个“唯一”的值。这个值可以对这个数据进行标识，在查找数据的时候，可以通过这个值来快速定位数据，从而有效减少开销。

由于散列长度是有限和固定的，因此在数据极多的情况下散列值会出现重复，用术语讲就是“碰撞”。这个时候就需要其它方法来消除这种碰撞，比如再散列、拉链算法等。

举个例子，设计一个散列算法，这个算法是把比划数相加。

“知道”的散列值就是20，

“你好”的散列值就是13。（我数对没有？ :））

java 什么是散列码

我的理解是：“散列码”就是用来把一堆对象散到各自的队列里去的一种标识码。

举个形象一点的例子，一年有 365 天，从 1 编号到 365，下面我定义一种编码方法，每个人按照他生日那天的编号作为他的标识码，这样，一群人每个人就会有一个标识码。

这个标识码有什么用呢？好，下面我说，请所有单号的人站到一起，所有双号的人站在一起。此后，当我要找一个人的时候，如果知道他的编号是单号，那我只需要到前面一堆人里去找，查找效率提高了一倍。

如果我说，请编号能被 16 整除的人站到一起，被 16 除余 1 的人站到一起，被 16 除余 2 的人站到一起…… 此后，当我要找一个人的时候，查找效率就会提高到 16 倍。

这就是散列码。所以，一个好的散列码算法，配合一个适当的存储机制，就能够实现高效的存储管理。

那么，不好的散列码算法会有多糟糕呢？比如，hashCode() 返回一个常量，那么，无论什么存储机制都会退化，所有的人都站在一堆里，查找效率无法提高。不过，也就只是影响效率，不会影响“正确性”，因为散列码的本性决定了，所有的算法都不应该假设两个不同的对象必须有不同的散列码。