Java基本查找算法 -- 哈希表的查找

柔情只为你懂 2023-10-06 11:45 37阅读 0赞

## `一、哈希表的查找` ##

> 前面讨论的线性表和树表的查找中，表中的相对位置是随机的，也就是是说，记录在表中的位置跟记录的关键字之间不存在确定关系。因此，在这些表中查找记录时需要进行一系列的关键字比较。这一类查找方法是建立在“比较”的基础上的。  
> 在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和表中一个唯一的存储位置相对应,称这个对应关系f为哈希(散列)函数,根据这个思想建立的表称为哈希表。

> 在哈希表中,若出现key1≠key2,而f(key1)=f(key2),则这种现象称为地址冲突key1和key2对哈希函数f来说是同义词。根据设定的哈希函数f=H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集上，并以关键字在地址集中的“象作为记录中的存储位置，这一映射过程为构造哈希表(散列表)。  
> 　　好的哈希函数应该使一组关键字的哈希地址均匀分布在整个哈希表中，从而减少冲突，常用的构造哈希函数的方法有：
> 
>  *  (1)直接地址法。取关键字或关键字的某个线性函数值为哈希地址,即H(key)=key或H(key)=a\*ket+b,其中,a和b为常数
>  *  (2)数字分析法。假设关键字是r进制数(如十进制数),并且哈希表中可能出现的关键字都是事先知道的，则可选取关键字的若干数位组成哈希地址。选取的原则是使得到的哈希地址尽量避免冲突，即所选数位上的数字尽可能是随机的。
>  *  (3)平方取中法。取关键字平方后的中间几位为哈希地址。这是一种较常用的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，仅取其中的几位为地址不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此得到的哈希地址随机性更大。
>  *  (4)除留余数法。取关键字被某个不大于哈希表长m的数p除后所得的余数为哈希地址。即:H(key)= key mod p(p<=m)。这是一种最简单、最常用的方法,它不仅可以键字直接取模，也可在折叠、平方取中等运算上取模。

> 采用均匀的哈希函数可以减少地址冲突，但是不能避免冲突，因此，必须有良好的法来处理冲突，通常，处理地址冲突的方法有以下两种:
> 
>  *  (1)开放地址法。在开放地址法中，以发生冲突的哈希地址为自变量，通过某周哈希冲突函数得到一个新的空闲的哈希地址。这种得到新地址的方法有很多种，主要有线性探查法和平方探查法。线性探查法是从发生冲突的地址开始，依次探查该地址的下一地址，直到找到一个空闲单元为止。而平方探查法则是在发生冲突的地址上加减某个因子的平方作为新的地址。
>  *  (2)拉链法。拉链法是把所有的同义词用单链表链接起来的方法。在这种方哈希表中每个单元中存放的不再是记录本身，而是相应同义词单链表的头指针。

> 例1：有如下数字构成的序列：A = \{ 7，4，1，14，100，30，5，9，20，134 \} 请构造一张哈希表。  
> 　　  
> 对数字序列:A = \{ 7,4,1,14，100，30，5，9，20，134 \}中的10个元素,就可以采用除留余数法来构造哈希表,哈希函数为H(key)=key%p(p<=m),其中p用13,m用15,而对与哈希冲突的解决，可以采用开放地址中的线性探查法，具体构造哈希表的过程如下：

> 首先在哈希表可用空间里取用15个连续空间来存放对应元素,对于A中第一个元素用哈希函数求其对应的空间位置为:7%13=7，所以把第一个元素7放入位置为7的空间里。  
> ![在这里插入图片描述][20200712232702545.png]  
> 对于A中第二个元素4,用哈希函数求其对应的空间位置为:4%13=4,所以把第个元素4放入位置为4的空间里。  
> ![在这里插入图片描述][20200712232638703.png]  
> 对于A中第三个元素1，用哈希函数求其对应的空间位置为：1%13=1，所以把第三个元素1放入位置为1的空间里。  
> ![在这里插入图片描述][20200712232605862.png]  
> 对于A中第四个元素14,用哈徐函数求其对应的空间地址为：14%13=1，但由于位置1的空间里有元素了，就采用开发地址中的线性探查法解决地址冲突，依此往后探索地址，得到位置2的空间可用，所以把第4个元素14放入位置2的空间里。  
> ![在这里插入图片描述][20200712232510378.png]  
> 按如此寻址规律循环下去，把剩下的元素全部放入哈希表中，得到哈希表如下：  
> ![在这里插入图片描述][20200712232419906.png]

> 为了便于查验构造哈希表结果的正确性，构造哈希表的代码里面添加了显示哈希表内容的函数和构造哈希表驱动程序，具体代码如下：

public class HashTable {
        
        public int[] key;
        public int nullKey = -1;
        public int count = 0;
        
        public HashTable() {
        
            this.key  = new int[50];
        }
        
        public void insertHT(HashTable ha, int key, int p, int m) {
        
            int i, adr;
            adr = key % p;
            if (ha.key[adr] == nullKey){
        
                ha.key[adr] = key;
                ha.count = 1;
            } else {
        
                i = 1;
                do {
        
                    adr = (adr + 1) % m;
                } while (ha.key[adr] != nullKey);
                ha.key[adr] = key;
                ha.count = i;
            }
        }
        
        public void  createHT(HashTable ha, int [] a, int n, int m, int p) {
        
            int i;
            for (i = 0; i < m; i++){
        
                ha.key[i] = nullKey;
                ha.count = 0;
            }
            for (i = 0; i < n; i++) {
        
                insertHT(ha, a[i], p, m);
            }
        }
        
        public void dispHT(HashTable ha, int m){
        
            int i;
            for (i = 0; i < m; i++) {
        
                System.out.println(i + " ");
            }
            System.out.println();
            for (i = 0; i < m; i++) {
        
                if (ha.key[i] != nullKey) {
        
                    if (ha.key[i] < 10) {
        
                        System.out.println(ha.key[i] + " ");
                    } else if (ha.key[i] >= 100) {
        
                        System.out.println(ha.key[i] + " ");
                    } else {
        
                        System.out.println(ha.key[i] + " ");
                    }
                } else {
        
                    System.out.println(" ");
                }
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
        
            int[] a= {
        7, 4, 1, 14, 100, 30, 5, 9, 20, 134};
            HashTable ht = new HashTable();
            ht.createHT(ht, a, a.length, 15, 13);
            ht.dispHT(ht, 15);
        }
    }

> 例2：在例:1所构造的哈希表中，查找100是否存在，并输出结果。  
> 　　在哈希表中对X值(如100)进行查找,则按照哈希函数获取待查元素的地址,若对应地址空间的值不等于待查元素的值，则线性搜索下一地址，比较对应地址空间的值，直到找到为止;若搜索到哈希表尾都未找到,则查找失败,具体Java代码如下:

public int searchHT(HashTable ha, int p, int m, int a){
        
        int adr;
        adr = a % p;
        while (ha.key[adr]!=nullKey && ha.key[adr]!=a) {
        
            adr=(adr+1)%m;
        }
        if (ha.key[adr]==a) {
        
            return adr;
        } else {
        
            return -1;
        }
    }

public static void main(String[] args) {
        
        int[] a= {
        7, 4, 1, 14, 100, 30, 5, 9, 20, 134};
        HashTable ht = new HashTable();
        ht.createHT(ht, a, a.length, 15, 13);
        ht.dispHT(ht, 15);
        
        int x = ht.searchHT(ht, 13, 15, 100);
        if (x==-1) {
        
            System.out.println("查找失败，不存在该元素");
        } else {
        
            
        }
        System.out.println("查找成功，该元素的地址为：" + x);
    }

> 算法分析:哈希表查找法查找成功时的平均查找长度是指查到表中已有的表象的平均获查次数，它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查装长度是指在表中查找不到待查的表项，但找到插入位置的平均探查次数，它是表中所有可能散列到的位置上要插入新元素时未找到空位置的探查次数的平均值。

[20200712232702545.png]: https://img-blog.csdnimg.cn/20200712232702545.png
[20200712232638703.png]: https://img-blog.csdnimg.cn/20200712232638703.png
[20200712232605862.png]: https://img-blog.csdnimg.cn/20200712232605862.png
[20200712232510378.png]: https://img-blog.csdnimg.cn/20200712232510378.png
[20200712232419906.png]: https://img-blog.csdnimg.cn/20200712232419906.png