哈希查找
- 博客分类:
- Classical Finding
大家可否知道,其实查找中有一种O(1)的查找,即所谓的秒杀。
第三:哈希查找:
对的,他就是哈希查找,说到哈希,大家肯定要提到哈希函数,呵呵,这东西已经在我们脑子里面形成固有思维了。大家一定要知道“哈希“中的对应关系。
比如说: ”5“是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个”2",那么此时的”5“和“2”就建立一种对应关系,这种关系就是所谓的“哈希关系”,在实际应用中也就形成了”2“是key,”5“是value。
那么有的朋友就会问如何做哈希,首先做哈希必须要遵守两点原则:
①: key尽可能的分散,也就是我丢一个“6”和“5”给你,你都返回一个“2”,那么这样的哈希函数不尽完美。
②: 哈希函数尽可能的简单,也就是说丢一个“6”给你,你哈希函数要搞1小时才能给我,这样也是不好的。
其实常用的做哈希的手法有“五种”:
第一种:”直接定址法“。
很容易理解,key=Value+C; 这个“C"是常量。Value+C其实就是一个简单的哈希函数。
第二种:“除法取余法”。
很容易理解, key=value%C;解释同上。
第三种:“数字分析法”。
这种蛮有意思,比如有一组value1=112233,value2=112633,value3=119033,
针对这样的数我们分析数中间两个数比较波动,其他数不变。那么我们取key的值就可以是
key1=22,key2=26,key3=90。
第四种:“平方取中法”。此处忽略,见名识意。
第五种:“折叠法”。
这种蛮有意思,比如value=135790,要求key是2位数的散列值。那么我们将value变为13+57+90=160,
然后去掉高位“1”,此时key=60,哈哈,这就是他们的哈希关系,这样做的目的就是key与每一位value都相关,来做到“散列地址”尽可能分散的
目地。
正所谓常在河边走,哪有不湿鞋。哈希也一样,你哈希函数设计的再好,搞不好哪一次就撞楼了,那么抛给我们的问题就是如果来解决“散列地址“的冲突。
其实解决冲突常用的手法也就2种:
第一种: “开放地址法“。
所谓”开放地址“,其实就是数组中未使用的地址。也就是说,在发生冲突的地方,后到的那个元素(可采用两种方式
:①线性探测,②函数探测)向数组后寻找"开放地址“然后把自己插进入。
第二种:”链接法“。
这个大家暂时不懂也没关系,我就先介绍一下原理,就是在每个元素上放一个”指针域“,在发生冲突的地方,后到的那个元素将自己的数据域抛给冲突中的元素,此时冲突的地方就形成了一个链表。
上面啰嗦了那么多,也就是想让大家在”设计哈希“和”解决冲突“这两个方面提一点参考和手段。
那么下面就上代码了,
设计函数采用:”除法取余法“。
冲突方面采用:”开放地址线性探测法"。
- import java.util.List;
- import java.util.Arrays;
- import java.util.Scanner;
- public class HashProgram
- {
- //“除法取余法”
- static int hashLength = 13 ;
- //原数据
- static Integer a[]={ 13 , 29 , 27 , 28 , 26 , 30 , 38 };
- static List<Integer> list=Arrays.asList(a);
- //c#中可以这样啊!jdk1.7也不能啊
- // static List<int> list = new List<int>() { 13, 29, 27, 28, 26, 30, 38 };
- //哈希表长度
- static int [] hash = new int [hashLength];
- public static void main(String[] args)
- {
- Scanner sca=new Scanner(System.in);
- //创建hash
- for ( int i = 0 ; i < list.size(); i++)
- {
- InsertHash(hash, hashLength, list.get(i));
- }
- System.out.println("Hash表中的数据:" );
- for ( int i:hash)
- System.out.print(i+"," );
- while ( true )
- {
- System.out.printf("\n请输入要查找数字:" );
- int result = sca.nextInt();
- int index = SearchHash(hash, hashLength, result);
- if (index != - 1 )
- System.out.println("数字" + result + "在索引的位置是:" + index);
- else
- System.out.println("呜呜," + result + " 在hash中没有找到!" );
- }
- }
- // Hash表检索数据
- static int SearchHash( int [] hash, int hashLength, int key)
- {
- //哈希函数
- int hashAddress = key % hashLength;
- //指定hashAdrress对应值存在但不是关键值,则用开放寻址法解决
- while (hash[hashAddress] != 0 && hash[hashAddress] != key)
- {
- hashAddress = (++hashAddress) % hashLength;
- }
- //查找到了开放单元,表示查找失败
- if (hash[hashAddress] == 0 )
- return - 1 ;
- return hashAddress;
- }
- //数据插入Hash表
- static void InsertHash( int [] hash, int hashLength, int data)
- {
- //哈希函数
- int hashAddress = data % 13 ;
- //如果key存在,则说明已经被别人占用,此时必须解决冲突
- while (hash[hashAddress] != 0 )
- {
- //用开放寻址法找到
- hashAddress = (++hashAddress) % hashLength;
- }
- //将data存入字典中
- hash[hashAddress] = data;
- }
- }
运行:
D:\java>java HashProgram
Hash表中的数据:
13,27,28,29,26,30,0,0,0,0,0,0,38
请输入要查找数字:38
数字38在索引的位置是:12
请输入要查找数字:33
呜呜,33 在hash中没有找到!
请输入要查找数字:27
数字27在索引的位置是:1
请输入要查找数字:
第四:索引查找
简称分级查找.例如汉字查找.对象是计算机为索引查找而建立的主表和各级索引表,主表只有一个,索引表的级数和数量不受限制,根据具体的需要确定.索引存储结构是数据组织的一项很重要的存储技术,在数据库领域中有广泛的应用.
基本思想:首先把一个集合或线性表(主表)按照一定的函数关系或条件划分成若干个逻辑上的子表,为每个子表分别建立一个索引项,由所有这些索引项构成主表的一个索引表,然后,可采用顺序或是链接的方式来存储索引表和每个子表.
索引表包含三个域:
(1)索引值域,用来存储对应子表的索引值,相当于记录的关键字,在索引表中由此索引值来唯一标识一个索引项.
(2)表的开始位置域,用来存储对应子表的第一个元素的存储位置,从此位置出发可以依次访问到子表中的所有元素.
(3)子表的长度域:用来存储对应子表的元素个数.
索引查找算法:是在索引表和主表上进行的查找.过程是:首先根据给定的索引值K1,在索引表上查找出索引值等于K1的索引项,以确定对应子表
在主表的开始位置和长度.然后再根据给定的关键字K2,在对应的子表中查找出关键字等于K2的元素.对索引表或子表的查找时,若表是顺序存储的有序表,则
可进行顺序查找,也可以进行二分查找.否则只能进行顺序查找.
- import java.util.Arrays;
- public class IndexSearch {
- // 主表
- static int [] students = { 101 , 102 , 103 , 104 , 105 , 0 , 0 , 0 , 0 , 0 , 201 , 202 ,
- 203 , 204 , 0 , 0 , 0 , 0 , 0 , 0 , 301 , 302 , 303 , 0 , 0 , 0 , 0 , 0 , 0 , 0 };
- // 索引表
- static IndexItem[] indexItem = { new IndexItem( 1 , 0 , 5 ),
- new IndexItem( 2 , 10 , 4 ), new IndexItem( 3 , 20 , 3 ), };
- // 查找数据
- public static int indexSearch( int key) {
- IndexItem item = null ;
- // 建立索引规则
- int index = key / 100 ;
- // 首先去索引找
- for ( int i = 0 ; i < indexItem.length; i++) {
- if (indexItem[i].index == index) {
- item = indexItem[i];
- break ;
- }
- }
- // 如果item为null,则说明在索引中查找失败
- if (item == null )
- return - 1 ;
- for ( int i = item.start; i < item.start + item.length; i++) {
- if (students[i] == key) {
- return i;
- }
- }
- return - 1 ;
- }
- // / 插入数据
- public static int insert( int key) {
- IndexItem item = null ;
- // 建立索引规则
- int index = key / 100 ;
- int i = 0 ;
- for (i = 0 ; i < indexItem.length; i++) {
- // 获取到了索引
- if (indexItem[i].index == index) {
- item = indexItem[i];
- break ;
- }
- }
- if (item == null )
- return - 1 ;
- // 更新主表
- students[item.start + item.length] = key;
- // 更新索引表
- indexItem[i].length++;
- return 1 ;
- }
- public static void main(String[] args) {
- int value = 205 ;
- // 将205插入集合中,过索引
- int index = insert(value);
- insert(308 );
- // 如果插入成功,获取205元素所在的位置
- if (index == 1 ) {
- System.out.println("\n插入后数据:" + Arrays.toString(students));
- System.out.println("\n数据元素:205在数组中的位置为 " + indexSearch( 205 ) + "位" );
- }
- }
- }
- // 索引项实体
- class IndexItem {
- // 对应主表的值
- public int index;
- // 主表记录区间段的开始位置
- public int start;
- // 主表记录区间段的长度
- public int length;
- public IndexItem() {
- }
- public IndexItem( int index, int start, int length) {
- this .index = index;
- this .start = start;
- this .length = length;
- }
- }
运行:
D:\java>java IndexSearch
插入后数据:[101, 102, 103, 104, 105, 0, 0, 0, 0, 0, 201, 202, 203, 204, 205, 0, 0, 0, 0, 0, 301, 302, 303, 308, 0, 0, 0, 0, 0, 0]
数据元素:205在数组中的位置为 14位
相关推荐
//哈希查找法 #include #include #include<iomanip.h> #define datawidth 5 //设置数据显示宽度 #define arraymaxnum 21 //约定数组大小,0号单元默认不用,故用户数据可以接受20个 #define defaultnum 10 //约定...
哈希查找数据结构实验报告.pdf
c/c++语言程序-哈希查找
易语言万倍哈希查找源码,万倍哈希查找,操作函数,加入,取回,删除,成员数,内部哈希,线程等待,取时间戳_易,创建进入许可证_,进入许可区_,退出许可区_,删除进入许可证_,启动线程_,销毁线程_,寻找字节集_,内存_申请,内存_...
哈希表(散列表)和哈希查找方法,解决冲突方法教程
数据结构,哈希查找,C语言开发,界面友好。。
C 言语 哈希查找算法 数据结构教才答案
哈希查找 C++源代码 数据结构。 数据结构课作业。
建立哈希表查找c++中32个关键字,其中哈希表长为M=101 32个关键字为auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof ...
哈希查找算法的源代码c语言[文].pdf
输入:待哈希数据序列 功能要求:输出哈希方法和解决冲突的方法(文字输出),输出哈希表
#include #include typedef struct node { int data; struct node *next; }node; init_hash(node **A,int n) { int i; for(i=0;i;i++) { A[i]=(node *)malloc(sizeof(node));...printf("请选择hash表的操作\n1....}
哈希查找,是查找的方法中重要的一种查找方法
数据结构查找方法 哈希查找 折半查找 顺序查找
根据一个班级成员的汉语拼音构造建立哈希表,利用哈希函数进行查找
万倍哈希查找.rar 万倍哈希查找.rar 万倍哈希查找.rar 万倍哈希查找.rar 万倍哈希查找.rar 万倍哈希查找.rar
2) 掌握哈希查找的基本方法及适用场合,并能在解决实际问题时灵活应用; 3) 巩固在散列查找时解决冲突的方法及特点。 2. 实验内容 1) 哈希表查找的实现(用线性探测法解决冲突); 2) 能对哈希表进行插入和查找。 3...
数据结构查找方法 哈希查找
数据结构-查找算法 二分查找 二叉顺序数 哈希查找
可以实现最小完美哈希查找,及查找时间复杂度为O(1),且load size 为1