算法09 五大查找之:哈希查找

前面的几篇文章分别总结了:顺序查找二分查找索引查找二叉排序树。这一篇文章要总结的是五大查找的最后一个:哈希查找(也称为散列查找)。提起哈希,我的第一印象就是java中的Hashtable类,它是由 key/value 的键值对组成的集合,它就是应用了哈希技术。

那什么是哈希查找呢?在弄清楚什么是哈希查找之前,我们要弄清楚哈希技术,哈希技术是在记录的存储位置和记录的 key 之间建立一个确定的映射 f(),使得每个 key 对应一个存储位置 f(key)。若查找集合中存在这个记录,则必定在 f(key) 的位置上。哈希技术既是一种存储方法,也是一种查找方法。

六种哈希函数 f(key) 的构造方法:

1、直接定址法

哈希地址:f(key) = a*key+b  (a,b为常数)

这种方法的优点是:简单,均匀,不会产生冲突。但是需要事先知道 key 的分布情况,适合查找表较小并且连续的情况。

2、数字分析法

比如我们的11位手机号码“136xxxx5889”,其中前三位是接入号,一般对应不同运营公司的子品牌,如130是联通如意通,136是移动神州行等等。中间四位表示归属地。最后四位才是用户号。

若我们现在要存储某家公司员工登记表,如果用手机号码作为 key,那么极有可能前7位都是相同的,所以我们选择最后四位作为 f(key) 就是不错的选择。

3、平方取中法

故名思义,比如 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位即得到 f(key) = 962 。

5、除留余数法

哈希地址:f(key) = key mod p (p<=m) m为哈希表表长。

这种方法是最常用的哈希函数构造方法。下面的代码中也使用了这种方法。

6、随机数法

哈希地址:f(key) = random(key)  

这里 random 是随机函数,当 key 的长度不等时,采用这种方法比较合适。

哈希函数冲突的两种解决方法:

我们设计得再好的哈希函数也不可能完全避免冲突,当我们使用哈希函数后发现有 key1 != key2,但却有 f(key1) = f(key2) ,即发生冲突。

1、开放定址法:

开放定址法就是一旦发生了冲突,就去寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总是能找到,然后将记录插入。这种方法是最常用的解决冲突的方法。下面的代码中也使用了这种方法。

2、链地址法:

链地址法不做详细展开。

代码:

HashSearch.java

import java.io.IOException;
import java.util.Scanner;

public class HashSearch {
    // 初始化哈希表
    static int hashLength = 7;
    static int[] hashTable = new int[hashLength];

    // 原始数据
    static int[] list = new int[]{13, 29, 27, 28, 26, 30, 38};

    public static void main(String[] args) throws IOException {
        System.out.println("*******哈希查找*******");

        // 创建哈希表
        for (int i = 0; i < list.length; i++) {
            insert(hashTable, list[i]);
        }
        System.out.println("展示哈希表中的数据:" + display(hashTable));

        while (true) {
            // 哈希表查找
            System.out.print("请输入要查找的数据:");
            int data = new Scanner(System.in).nextInt();
            int result = search(hashTable, data);
            if (result == -1) {
                System.out.println("对不起,没有找到!");
            } else {
                System.out.println("数据的位置是:" + result);
            }
        }
    }

    /**
     * 方法:哈希表插入
     */
    public static void insert(int[] hashTable, int data) {
        // 哈希函数,除留余数法
        int hashAddress = hash(hashTable, data);

        // 如果不为0,则说明发生冲突
        while (hashTable[hashAddress] != 0) {
            // 利用 开放定址法 解决冲突
            hashAddress = (++hashAddress) % hashTable.length;
        }

        // 将待插入值存入字典中
        hashTable[hashAddress] = data;
    }

    /**
     * 方法:哈希表查找
     */
    public static int search(int[] hashTable, int data) {
        // 哈希函数,除留余数法
        int hashAddress = hash(hashTable, data);

        while (hashTable[hashAddress] != data) {
            // 利用 开放定址法 解决冲突
            hashAddress = (++hashAddress) % hashTable.length;
            // 查找到开放单元 或者 循环回到原点,表示查找失败
            if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, data)) {
                return -1;
            }
        }
        // 查找成功,返回下标
        return hashAddress;
    }

    /**
     * 方法:构建哈希函数(除留余数法)
     *
     * @param hashTable
     * @param data
     * @return
     */
    public static int hash(int[] hashTable, int data) {
        return data % hashTable.length;
    }

    /**
     * 方法:展示哈希表
     */
    public static String display(int[] hashTable) {
        StringBuffer stringBuffer = new StringBuffer();
        for (int i : hashTable) {
            stringBuffer = stringBuffer.append(i + " ");
        }
        return String.valueOf(stringBuffer);
    }
}

运行结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我杨某人的青春满是悔恨

Swift API 设计指南(下)

一般来说,默认参数比方法族(method families)更可取,因为它减轻了 API 使用者的认知负担。

8220
来自专栏函数式编程语言及工具

泛函编程(0)-什么是泛函编程

 什么是泛函编程(Functional Programming)?泛函编程就是用函数编写程序。这个回答太抽象,等于没说。 再说清楚一点:泛函编程就想砌积木一样把...

21880
来自专栏海天一树

NOIP 2018普及组初赛C/C++答案详解

1 D 打印机是把电脑里的资料打印到纸上,所以是输出设备。 扫描仪、键盘和鼠标都是往电脑里输入东西,是输入设备。

24330
来自专栏take time, save time

你所能用到的数据结构(八)

十一、不能被应用的理论不是好研究 前面介绍了堆栈的一些小小的理论模型,那么这样一个东西有什么作用呢?实际中不可能有那么一辆停在站台前方堵死的火车的,即使有,也...

28340
来自专栏我杨某人的青春满是悔恨

《编程的智慧(初稿)》读后感

王垠更新了文章,加入了Optional跟Union比较的内容,所以我也来更新一下。垠神认为Optional并没有什么卵用,Java8的Optional我不是很了...

12120
来自专栏我的小碗汤

一文带你读懂:最小栈问题

设一个变量int min = -1; 当一个元素进入栈时,把最小值的下标记录成0,后面进来的数和stack[min]做比较,如果大于等于当前的最小值,那就不做变...

11830
来自专栏人工智能LeadAI

记一道未能答出的算法面试题

昨天晚上,参加了一场面试,有道算法题当时没答出来,痛心疾首!刚刚起床给娃娃换尿布的空当,突然间就想清楚了实现的办法,当时没答出来就是卡在构建多叉树这一点!本文会...

39570
来自专栏BaronTalk

Java8新特性第3章(Stream API)

Stream作为Java8的新特性之一,他与Java IO包中的InputStream和OutputStream完全不是一个概念。Java8中的Stream是对...

362100
来自专栏iKcamp

翻译连载 |《你不知道的JS》姊妹篇 |《JavaScript 轻量级函数式编程》- 第 8 章:列表操作

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 8 章:列表操作 你是否还沉...

47970
来自专栏web编程技术分享

JavaScript: 零基础轻松学闭包(2)

28690

扫码关注云+社区

领取腾讯云代金券