07.哈希查找元素

归并排序

  • 1.基本思想
  • 2.排序过程
  • 3.代码实现
  • 4.如何优化
  • 5.复杂度
  • 6.使用场景

1.基本思想

  • 哈希查找介绍
    • 要了解哈希查找，就要先了解一下哈希表和哈希函数。先看下标准的定义：哈希表，是根据关键值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表（哈希表）。
  • 构造哈希表
    • 要使用哈希查找，就要先有哈希表，所以需要先介绍一下哈希表的构造方法。常见的构造方法有如下几种：
    • 1>直接定址法
      • 哈希地址：f(key) = a*key+b (a,b为常数)。
      • 这种方法的优点是：简单、均匀、不会产生冲突。但是需要事先知道 key 的分布情况，适合查找表较小并且连续的情况。
    • 2>数字分析法
      • 假设关键字是R进制数（如十进制）。并且哈希表中可能出现的关键字都是事先知道的，则可选取关键字的若干数位组成哈希地址。选取的原则是使得到的哈希地址尽量避免冲突，即所选数位上的数字尽可能是随机的。
      • 举个例子：比如11位手机号码“136xxxx5889”，其中前三位是接入号，一般对应不同运营公司的子品牌，中间四位表示归属地，最后四位才是用户号，此时就可以用后4位来作为哈希地址。
    • 3>平方取中法
      • 取key平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，仅取其中的几位为地址不一定合适。而一个数平方后的中间几位数和数的每一位都相关， 由此得到的哈希地址随机性更大。如 key 是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为 f(key) 。
    • 4>折叠法
      • 折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表的表长，取后几位作为 f(key) 。
      • 比如key 是 9876543210，哈希表的表长为3位，我们将 key 分为4组，987 | 654 | 321 | 0 ，然后将它们叠加求和 987+654+321+0=1962，再取后3位即得到哈希位置是：962 。
    • 5>除留余数法
      • 取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。即 f(key) = key % p (p ≤ m)。这种方法是最常用的哈希函数构造方法。
    • 6>随机数法
      • 哈希地址：random(key) ，这里 random 是随机函数，当 key 的长度不等时，采用这种方法比较合适。

2.查找过程

  • 从上面的定义可以看出：哈希查找与线性表查找和树表查找最大的区别在于，不用数值比较。

3.代码实现

  • 依据上文介绍，先构建哈希表。而要构建哈希表，就要先有计算地址的方法，示例代码如下：
    /*用除留余数法计算要插入元素的地址*/
public static int hash(int[] hashTable, int data) {
    return data % hashTable.length;
}
  • 有了计算哈希地址的方法后，剩下的就是将原始的元素插入到哈希表中，也就是先利用key计算一个地址，如果这个地址以及有元素了，就继续向后寻找。此处可以循环计算地址，示例代码如下：
    /*将元素插入到哈希表中*/
public static void insertHashTable(int[] hashTable, int target) {
    int hashAddress = hash(hashTable, target);
    /*如果不为0，则说明发生冲突*/
    while (hashTable[hashAddress] != 0) {
        /*利用开放定址法解决冲突，即向后寻找新地址*/
        hashAddress = (++hashAddress) % hashTable.length;
    }
    /*将元素插入到哈希表中*/
    hashTable[hashAddress] = target;
}
  • 哈希表构建后，就是在哈希表中查找元素了。在查找元素时，容易想到的情况是：在直接计算出的哈希地址及其后续位置查找元素。特殊的是，上一步中，有循环计算地址的操作，所以此处计算到原始地址时，也代表查找失败。示例代码如下：
    public static int searchHashTable(int[] hashTable, int target) {
    int hashAddress = hash(hashTable, target);

    while (hashTable[hashAddress] != target) {
        /*寻找原始地址后面的位置*/
        hashAddress = (++hashAddress) % hashTable.length;
        /*查找到开放单元(未存放元素的位置)或 循环回到原点，表示查找失败*/
        if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, target)) {
            return -1;
        }
    }
    return hashAddress;
}
  • 完整示例代码如下：
    public class Test {
	
    /*待查找序列*/
    static int[] array = {13, 29, 27, 28, 26, 30, 38};
    /* 初始化哈希表长度，此处哈希表容量设置的和array长度一样。
     * 其实正常情况下，哈希表长度应该要长于array长度，因为使用
     * 开放地址法时，可能会多使用一些空位置
     */
    static int hashLength = 7;
    static int[] hashTable = new int[hashLength];

    public static void main(String[] args) {
        /*将元素插入到哈希表中*/
        for (int i = 0; i < array.length; i++) {
        	insertHashTable(hashTable, array[i]);
        }
        System.out.println("哈希表中的数据：");
        printHashTable(hashTable);
        
        int data = 28;
        System.out.println("\n要查找的数据"+data);
        int result = searchHashTable(hashTable, data);
        if (result == -1) {
            System.out.println("对不起，没有找到！");
        } else {
            System.out.println("在哈希表中的位置是：" + result);
        }
        
        int data2 = 38;
        System.out.println("\n要查找的数据"+data2);
        int result2 = searchHashTable(hashTable, data2);
        if (result2 == -1) {
            System.out.println("对不起，没有找到！");
        } else {
            System.out.println("在哈希表中的位置是：" + result2);
        }
        
        int data3 = 48;
        System.out.println("\n要查找的数据"+data3);
        int result3 = searchHashTable(hashTable, data3);
        if (result3 == -1) {
            System.out.println("对不起，没有找到！");
        } else {
            System.out.println("在哈希表中的位置是：" + result3);
        }
    }

    /*将元素插入到哈希表中*/
    public static void insertHashTable(int[] hashTable, int target) {
        int hashAddress = hash(hashTable, target);
        /*如果不为0，则说明发生冲突*/
        while (hashTable[hashAddress] != 0) {
            /*利用开放定址法解决冲突，即向后寻找新地址*/
            hashAddress = (++hashAddress) % hashTable.length;
        }
        /*将元素插入到哈希表中*/
        hashTable[hashAddress] = target;
    }

    public static int searchHashTable(int[] hashTable, int target) {
        int hashAddress = hash(hashTable, target);
        while (hashTable[hashAddress] != target) {
            /*寻找原始地址后面的位置*/
            hashAddress = (++hashAddress) % hashTable.length;
            /*查找到开放单元(未存放元素的位置)或 循环回到原点，表示查找失败*/
            if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, target)) {
                return -1;
            }
        }
        return hashAddress;
    }

    /*用除留余数法计算要插入元素的地址*/
    public static int hash(int[] hashTable, int data) {
        return data % hashTable.length;
    }

    public static void printHashTable(int[] hashTable) {
    	for(int i=0;i<hashTable.length;i++) {
    		System.out.print(hashTable[i]+" ");
    	}
    }
}
  • 得出的结果如下所示
    哈希表中的数据：
27 29 28 30 38 26 13 
要查找的数据28
在哈希表中的位置是：2

要查找的数据38
在哈希表中的位置是：4

要查找的数据48
对不起，没有找到！

4.如何优化

5.复杂度

6.使用场景

贡献者: yangchong211