数据结构 - 哈希表解析实现

标签: 数据结构和算法  数据结构  java  hash

哈希表

Hash表也称散列表,也可以直接译作哈希表,Hash表是一种根据关键字值(key - value)映射到表中的一个位置而直接进行访问的数据结构,这个映射函数叫散列函数(哈希函数)

在这里插入图片描述

(链地址法哈希表)

哈希表基于数组实现,通过把关键字映射到数组的某个下标(哈希函数)来加快查找速度,查找某个关键字对于哈希表来说,只是O(1)的时间级


什么是散列函数

散列函数:将关键字装换为数组的特定下标,这种转换的函数就是哈希函数

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

就如同构建一个字典,先将所有的单词全部存入内存,散列函数就如同目录,是单词与对应地址的映射

一个高效的散列函数可以帮我们快速定位对应的地址,如何设置高效的散列函数?

需要考虑:

  • 计算哈希函数所需时间
  • 关键字的长度、种类
  • 哈希表的大小
  • 关键字的分布情况
  • 记录的查找频率

常见的散列函数有六种:

  1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址,也就是f(key) = a * key + b,最基本的散列函数
  2. 数据分析法:分析一组数据,找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址(如网址都是后几位不同,就利用后几位映射地址)
  3. 平方取中法:当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址
  4. 折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址
  5. 随机数法:选择一随机函数,取关键字的随机值作为散列地址
  6. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址

当关键字是非基本数据类型时需要考虑多方面,这里就不深追,以下的例子以关键字为整形,通过取余法为散列函数简单处理


冲突

取余法:关键字除一个设置的不大于散列表表长的数m,key % m得到余数,余数为0~9,即将关键字映射到了0-9的数组上

把巨大的数字范围压缩到较小的数字范围,那么肯定会有几个不同的单词哈希化到同一个数组下标,即产生了冲突

例如设置m=10,数组为0~9,1和11都会映射到数组下标为1的位置,这就产生了冲突

常用两种方法:

  • 开放地址法:当冲突产生时,再给关键字找一个地址,有三种方法:线性探测、二次探测以及再哈希法
  • 链地址法:扩展数组的单元,即数组每个数据项设置为链表或者子数组

开放地址法

开发地址法:当冲突发生时,为关键字再找一个合适的位置

线性探测

当散列函数得到的位置被占,数组下标依次递增,直到找到空白的位置

例如:存入1和11,1的位置被占了,在下标2的位置存放11

以下通过Java实现一个开放地址法的哈希表

将要存放的数据,关键字为int型


class DataItem {
    private int iData;

    public DataItem(int iData) {
        this.iData = iData;
    }

    public int getKey() {
        return iData;
    }
}

哈希表,设置了以下重要方法:

  • 取余:除数组大小
  • 插入数据项
  • 更新数组:新建数据为原数组大小的两倍
  • 删除数据项
  • 根据关键字查找数据项
public class MyHashTable {
    //DataItem类,表示每个数据项信息
    private DataItem[] hashArray;
    //数组的初始大小
    private int arraySize;
    //数组实际存储了多少项数据
    private int itemNum;
    //用于删除数据项
    private DataItem nonItem;

    public MyHashTable(int arraySize) {
        this.arraySize = arraySize;
        hashArray = new DataItem[arraySize];
        //删除的数据项下标初始化为-1
        nonItem = new DataItem(-1);
    }

    //判断数组是否存储满了
    public boolean isFull() {
        return (itemNum == arraySize);
    }

    //判断数组是否为空
    public boolean isEmpty() {
        return (itemNum == 0);
    }


    //打印数组内容
    public void display() {
        System.out.println("Table:");
        for (int j = 0;j < arraySize;j++) {
            if (hashArray[j] != null) {
                System.out.println("== 第 "+j+" 项为:"+hashArray[j].getKey() + " ==");
            } else {
                System.out.println("== 第 "+j+" 项为空 ==");
            }
        }
    }

    //通过哈希函数转换得到数组下标
    public int hashFunction(int key) {
        return key % arraySize;
    }

    //插入数据项
    public void insert(DataItem item) {

        if (isFull()) {
            //哈希表已满,扩展哈希表
            System.out.println("哈希表已满,重新哈希化...");
            extendHashTable();
        }
        int key = item.getKey();
        int hashVal = hashFunction(key);
        while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
            //线性探测,直接下标+1
            ++hashVal;
            //防止越界
            hashVal %= arraySize;
        }
        hashArray[hashVal] = item;
        itemNum++;
    }

    /**
     * 数组不能扩展,只能新建数组存放,数组大小改变,需要重新映射所有数据
     * 这个过程叫做重新哈希化。这是一个耗时的过程
     * */
    public void extendHashTable() {
        int num = arraySize;
        //重新计数,因为下面要把原来的数据转移到新的扩张的数组中
        itemNum = 0;
        //数组大小翻倍(可以自己设置)
        arraySize *= 2;
        DataItem[] oldHashArray = hashArray;
        hashArray = new DataItem[arraySize];
        for (int i = 0; i < num; i++) {
            insert(oldHashArray[i]);
        }
    }

    //删除数据项
    public DataItem delete(int key) {
        if (isEmpty()) {
            System.out.println("Hash Table is Empty!");
            return null;
        }
        int hashVal = hashFunction(key);
        while (hashArray[hashVal] != null) {
            if (hashArray[hashVal].getKey() == key) {
                DataItem temp = hashArray[hashVal];
                //nonItem表示空Item,其key为-1
                hashArray[hashVal] = nonItem;
                itemNum--;
                return temp;
            }
            ++hashVal;
            hashVal %= arraySize;
        }
        return null;
    }

    //查找数据项
    public DataItem find(int key) {
        int hashVal = hashFunction(key);
        while (hashArray[hashVal] != null) {
            if (hashArray[hashVal].getKey() == key) {
                return hashArray[hashVal];
            }
            ++hashVal;
            hashVal %= arraySize;
        }
        return null;
    }
}

设置一个测试类:

class Test{
    public static void main(String[] args) {
        MyHashTable myHashTable = new MyHashTable(10);

        Scanner scanner = new Scanner(System.in);
        while (true){
            System.out.println("add:添加数据 display:显示数据 find:查找 exit:退出");
            String key = scanner.next();

            switch (key){
                case "add":
                    System.out.println("输入iData:");
                    int iData = scanner.nextInt();
                    DataItem dataItem = new DataItem(iData);
                    myHashTable.insert(dataItem);
                    break;
                case "display":
                    myHashTable.display();
                    break;
                case "find":
                    System.out.println("请输入要查找的数据项的iData:");
                    iData = scanner.nextInt();
                    myHashTable.find(iData);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

添加3个数据:

在这里插入图片描述

打印,可以发现通过取余分别将数据放置在相应的位置:

在这里插入图片描述

再添加一个数据11,与1冲突,按照线性探测,放到下一个位置:

在这里插入图片描述

当数据满时,需要重新哈希化:

在这里插入图片描述

数组大小*2:
在这里插入图片描述

装填因子

可以从上面的案例中看出,当数组中数据数量到一定大小后,每次插入数据需要多次计算插入位置,这是比较耗时的

我们需要尽量减少再次计算,就需要引入一个填装因子

装填因子:已添加到哈希表内的数据项与表长的比例
例如哈希表大小1000,添加了500个数据项,装填因子为0.5

装填因子表示哈希表中元素填满的程度,当数据项到达一定程度,数据需要重新计算位置即冲突的几率很大

二次探测

二次探测是为了防止数据聚集,本质也是线性探测,区别在与设置较远的探测步长

从散列函数计算的原始下标为x,线性探测是x+1,x+2,x+3…,而二次探测为x+1,x+4,x+9,x+16…
在这里插入图片描述

相对与线性探测有了一定的改进

再散列法

前面线性探测、二次探测实际上都是固定的步长,我们可以设置一种依赖关键字的探测序列

再散列法:把关键字用不同的散列函数再做一遍散列化,用这个结果作为步长,进行探测

第二个散列函数需要:

  • 和第一个散列函数不同
  • 不能输出0,不然每次探测会原地踏步,陷入死循环

专家们已经发现下面形式的哈希函数工作的非常好:stepSize = constant - key % constant; 其中constant是质数,且小于数组容量,表的容量要是一个质数

例如:对上面的例子进行修改

创建第二个散列函数:步长 = 7 - key % 7

	//第二个散列函数:计算步长
	public int hashFunction2(int key){
        return 7 - key % 7;
    }
    
    //插入数据项
    public void insert2(DataItem item) {

        if (isFull()) {
            //哈希表已满,扩展哈希表
            System.out.println("哈希表已满,重新哈希化...");
            extendHashTable();
        }
        int key = item.getKey();
        int hashVal = hashFunction(key);
        //第二散列函数计算步长
        int stepSize = hashFunction2(key);
        while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
            //再散列法
            hashVal += stepSize;
            //防止越界
            hashVal %= arraySize;
        }
        hashArray[hashVal] = item;
        itemNum++;
    }

修改一下测试类,添加1和11,添加11时,步长为7-11%7=3,即在下标为4的位置加入数据

在这里插入图片描述

再散列法因为由关键字决定步长,可以较有效的减少聚集


链地址法

把数组的数据项设置为链表或者数组

常用的数组+链表

在这里插入图片描述

Java实现哈希表:数组+链表

这里再稍微该动:存放的数据为员工对象,属性为id,name

//表示一个员工
class Emp{
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

这里的哈希表=数组+链表,即需要分开为两个类:员工链表、哈希表

员工链表:

  • 添加员工:直接在链表尾加上新增员工
  • 遍历:遍历链表打印
  • 根据id查找员工
package com.company.hashTable;

import java.util.Scanner;

/**
 * @author zfk
 * 哈希表
 */

//员工链表
class EmpLinkedList{
    //头指针为第一个Emp
    private Emp head;

    //添加员工,直接加在最后
    public void add(Emp emp){
        //如果是添加第一个员工
        if (head == null){
            head = emp;
            return;
        }
        //如果不是第一个
        Emp cur = head;

        while (true){
            //到了链表最后
            if (cur.next == null) {
                break;
            }
            cur = cur.next;
        }
        //退出时cur为链表最后一个元素
        cur.next = emp;
    }

    //遍历链表
    public void list(int no){

        if (head == null){
            System.out.println("=== 第 "+no+" 条链表为空 ===");
            return;
        }
        System.out.println("=====第 "+no+" 条链表=======");
        Emp cur = head;
        while (true){
            System.out.print("=> id = "+cur.id+" name = "+cur.name);
            //已经是最后的节点
            if (cur.next == null){
                break;
            }
            //后移
            cur = cur.next;
        }
        System.out.println();
        System.out.println("============");
    }

    //根据id查找员工
    public Emp findEmpById(int id){
        //判断链表是否为空
        if (head == null){
            System.out.println("=== 当前链表为空 ===");
            return null;
        }
        Emp cur = head;

        while (true){
            //找到了cur
            if (cur.id == id){
                break;
            }
            //遍历完当前链表没有找到,退出
            if (cur.next == null){
                cur = null;
                break;
            }
            //后移
            cur = cur.next;
        }

        return cur;
    }
}

//哈希表
class HashTable{
    private EmpLinkedList[] linkedListArray;
    //表示链表数
    private int size;

    public HashTable(int size) {
        this.size = size;
        this.linkedListArray = new EmpLinkedList[size];
        //分别初始化链表
        for (int i = 0;i < size;i++){
            linkedListArray[i] = new EmpLinkedList();
        }
    }
    //添加
    public void add(Emp emp){
        //根据员工的id得到该员工应当添加到哪个链表
        int listNum = hashFun(emp.id);
        //将emp添加到对应的链表
        linkedListArray[listNum].add(emp);
    }

    //散列函数,使用取模法
    public int hashFun(int id){
        return id % size;
    }
    //遍历所有的链表
    public void list(){
        for (int i = 0;i < size;i++){
            linkedListArray[i].list(i);
        }
    }

    //根据输入的id查找员工
    public void findEmpById(int id){
        //使用散列函数确定应该从哪条链表查找
        int listNum = hashFun(id);
        Emp empById = linkedListArray[listNum].findEmpById(id);

        if (empById != null){
            System.out.println("在第 "+listNum+" 条链表查找到");
        }
        else {
            System.out.println("=== 在哈希表中没有找到 ===");
        }
    }
}

测试类:设置哈希表数组大小7

public class HashTableDemo {
    public static void main(String[] args) {
        //创建一个哈希表
        HashTable hashTable = new HashTable(7);
        Scanner scanner = new Scanner(System.in);
        while (true){
            System.out.println("add:添加成员 list:显示成员 find:查找 exit:退出");
            String key = scanner.next();

            switch (key){
                case "add":
                    System.out.println("输入id:");
                    int id = scanner.nextInt();
                    System.out.println("输入name:");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTable.add(emp);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id:");
                    id = scanner.nextInt();
                    hashTable.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                 default:
                     break;
            }
        }
    }

}

添加1,8数据项,这个时候我们就不需要考虑冲突的问题了

在这里插入图片描述


总结

hash表是一种根据关键字值(key-value)映射到表中的位置而直接访问的数据结构,构建hash表关键在于创建高效的hash函数

需要考虑:

  • 计算哈希函数所需时间
  • 关键字的长度、种类
  • 哈希表的大小
  • 关键字的分布情况
  • 记录的查找频率

常见的hash函数有6种:

  • 直接寻址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 随机数法
  • 取余法

hash函数可以压缩数据,将大范围数据映射到小范围,但不可避免会出现冲突:不同数据计算出同一下标
当数据出现冲突,会大量消耗时间去计算新的地址,引进了装填因子的概念,装填因子=数组中数据项 / 数组容量,装填因子表示哈希表中元素填满的程度,当装填因子越大,越可能发生冲突

为了解决冲突,有两种方法:

  • 开放地址法:当地址已被占有,根据一定规则找到新的位置放置
  • 链地址法:将数组的项设置为链表或子数组
版权声明:本文为key_768原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/key_768/article/details/106786645

智能推荐

使用欧几里得算法解决问题——求字符串的最大公因子(力扣第1071题)(JavaScript解法)

1、欧几里得算法的思想 基于辗转相除法的原理,具体做法:用较大数除以较小数,再用出现的余数(第一个余数)去除除数,,再用出现的余数(第二个余数)去除第一个余数,如此仿佛,直到最后一个余数为0 2、算法流程 3、JavaScript实现欧几里得算法 4、使用欧几里得算法解决问题 力扣1071字符串的最大公因子 题目描述: 对于字符串 S 和 T,只有在 S = T + … + T(T ...

spring与redis整合和序列化问题

spring与redis整合 首先用docker下载redis 下载:docker pull redis 运行:docker run -d -p 6379:6379 --name myredis docker.io/redis 连接redis Desktop Manager 然后开始在springboot上开始配置 application.yml: 自动配置好StringRedisTemplate...

CentOS 7配置南大docker镜像

文章目录 CentOS 7配置南大docker镜像 0.帮助页面 1.系统要求 2.卸载旧版本(没有旧版本可跳过) 3.安装方式 4.准备工作 5.可选操作 Stable Test Nightly 6.安装docker引擎 7. (可选)修改配置文件防止与xshell连接冲突 8.启动docker CentOS 7配置南大docker镜像 0.帮助页面 南大docker源:https://mirr...

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

猜你喜欢

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...