数据结构:哈希表

标签: Java  数据结构与算法  数据结构  哈希表  hash  java

 你受的苦,吃的亏,担的责,扛的罪,忍的痛,到最后都会变成光,照亮你的路。

什么是哈希表?

哈希表(Hash table,散列),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做哈希函数,存放记录的数组叫做哈希表。

举个栗子:

一个班有30名学生,他们的学号是1-30的,我们用数组来存储这些学生:

学号 数组下标
1 0
2 1
3 2
30 29

事实上,这个数组就是一个哈希表,班里每个学生的学号都对应了数组中的一个下标。

具体的对应关系为 : 下标 = 学号 - 1

而 f(key) = value,给定一个键值,计算得到一个地址,这样的关系函数就是哈希函数。

在这个具体的例子中, 下标 = 学号 - 1 就是哈希函数,给定一个学号,就能知道这个学生在数组中的存储位置。这样的话,想要查询一个学生的信息只需要O(1)的时间复杂度!

当然这是一种最为简单的哈希表,想要使用哈希表的方法进行查找,就必须解决下面两个问题:

  • Hash函数的构建
  • Hash冲突的解决方式

所谓的Hash冲突是指不同的key通过Hash函数所求的地址值value相同,则这些key就产生了Hash冲突

Hash函数的构建方法

哈希表之所以能达到O(1)的复杂度,本质上是以空间换时间。如果空间足够大,相应的我们就能在O(1)的复杂度下完成各项操作,而如果只有O(1)的空间,那么就需要O(n) (线性表)的时间复杂度。

Hash表就是时间和空间之间的平衡,因此Hash函数的构建是非常重要的。通常应该遵循下列原则:

  • 高效性:hash函数本身运算尽量简单,便与运算
  • 一致性:若a = b ,则 hash(a)= hash(b)
  • 均匀性:通过Hash函数得到的hash函数值必须在Hash地址范围内,且分布均匀,地址冲突尽量小

在上一个学号的例子中,我们直接以 下标 = 学号 - 1 的方式,很快的完成了Hash函数的构建,但事实上不是所有的问题都可以如此简单的构建出来,下面就来讨论更复杂的情况下如何构建Hash函数。

  1. 大整数:除留余数法
    在我国,居民身份证号是由18位数字组成的,比如:110323198512166666。
    哈希表充分体现了空间换时间的思想,如果我们真的有9999999999999999999个空间,那么我们完全可以从下标为0开始存放,当然这是不切实际的,而且如果真的这样做,也是对空间的极大浪费。对于较大的整数,并且这个整数的每几位还存在某些含义时,我们处理方法是模以一个素数。

下面给出了大整数在lwr-upr之间的最佳取模的素数:或者点击这个链接–>最佳取模的素数
在这里插入图片描述
之所以模以一个素数,是因为模以一个素数可以减少hash冲突并且能较为充分地利用到大整数的每部分数据。

比如:
在这里插入图片描述
在模以4时产生了严重的Hash冲突,而模以素数7在这组数据中没有发生Hash冲突。

  1. 特殊类型构建Hash函数
    对于特殊类型的数据,我们依然是将其转化为整数:比如字符串
    在这里插入图片描述

根据实际需求,我们也可以将字符串转化成B进制的整数。那么hash函数就是这样的:
在这里插入图片描述
上面三个hash函数是等价的,只是在第一个hash函数下简化了计算而已。

Hash冲突解决方法

由于具体问题的复杂性,Hash冲突不可避免的存在,因此就需要对Hash冲突进行处理,通常较好的方式是:链地址法。

例如通过Hash函数计算得到 k1的地址为4,k2的地址为1,分别插入后又来了一个k3且地址也是1,此时k1和k3发生了冲突,如何处理呢?
在这里插入图片描述
链地址法就是让发生冲突的元素以链表插在前一个元素后面:
在这里插入图片描述
事实上发生冲突时并不一定要构成一个链表,只要是查找表就行,也就是说我们完全可以链接一个AVL树或者红黑树。

在Java中HashMap就是TreeMap的数组;HashSet是TreeSet的数组。

基于TreeMap实现HashMap

package cn.boom.hash;

import java.util.Arrays;
import java.util.TreeMap;

public class HashTable<K, V> {

    //取模的素数
    private static int[] prime = {53,97,193,389,769,1543,3079,6151,12289,
                                  24593,49157,98317,196613,393241,786433,
                                  1572869,3145739,6291469,12582917,25165843,
                                  50331653,100663319,201326611,402653189,805306457,1610612741};

    private static final int upperTol = 10; //平均hash冲突上界
    private static final int lowerTol = 2; //平均hash冲突下界

    private TreeMap<K,V>[] hashTable;
    private int capacity;
    private int size;
    private int capacityIndex;

    public HashTable(){

        this.size = 0;
        this.capacityIndex = 0;
        this.capacity = prime[capacityIndex];
        this.hashTable = new TreeMap[capacity];

        for (int i = 0; i < capacity; i++) {
            hashTable[i] = new TreeMap<K, V>();
        }
    }

    public int getSize() {
        return size;
    }

    public boolean contains(K key) {
        int address = hash(key);
        return hashTable[address].containsKey(key);
    }

    //hash函数
    private int hash(K key) {
        return key.hashCode() & 0x7fffffff % capacity;//取key hashCode的正值并计算hash值
    }

    private void resize(int newCapacity){

        TreeMap<K, V>[] newHashTable = new TreeMap[newCapacity];
        for(int i = 0 ; i < newCapacity ; i ++)
            newHashTable[i] = new TreeMap<K,V>();

        int oldCapacity = this.capacity;
        this.capacity = newCapacity;

        for(int i = 0 ; i < oldCapacity ; i ++)
            for(K key: hashTable[i].keySet())
                newHashTable[hash(key)].put(key, hashTable[i].get(key));

        this.hashTable = newHashTable;
    }


    public void add(K key, V value) {

        int address = hash(key);

        if (hashTable[address].containsKey(key)) {
            hashTable[address].put(key, value);
        } else {
            hashTable[address].put(key, value);
            this.size++;

            if (this.size  >= this.capacity * upperTol && capacity+1 < prime.length) {
                resize(prime[(capacityIndex++)]);
            }

        }
    }

    public V remove(K key) {

        int address = hash(key);

        if (!hashTable[address].containsKey(key)) {
            throw new IllegalArgumentException(key + " doesn't exist ! ");
        }

        V ret = hashTable[address].remove(key);
        size--;

        if (this.size < this.capacity * lowerTol && capacityIndex - 1 >= 0) {
            resize(prime[(capacityIndex--)]);
        }

        return ret;
    }

    @Override
    public String toString() {
        return "HashTable{" +
                "hashTable=" + Arrays.toString(hashTable) +
                ", capacity=" + capacity +
                ", size=" + size +
                ", capacityIndex=" + capacityIndex +
                '}';
    }
}

版权声明:本文为qq_42080839原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42080839/article/details/104395001

智能推荐

android问题记录

Error: Cannot fit requested classes in a single dex file (# methods: 80441 > 65536) 解决办法: gradle文件的defaultConfig默认配置里面增加...

ROS机器人Diego 1# 利用人工智能 风格迁移技术拍摄不同画风的视频

风格迁移,就是将一种图片的风格迁移到其他图片上,改变其他图片的风格,很好玩的一个人工自能模型,github上已经有很多实现的方法,本文参考https://github.com/hzy46/fast-neural-style-tensorflow 的算法,利用Diego1#的平台实现实时视频的风格转换,先上两张图看效果: 是不是很酷呢,其实实现方法和上篇博文中的原理是一样的,只是把人工智能的算法包装...

数据分析学习总结笔记17:文本分析入门案例实战

文章目录 1 数据准备 2 分词 3 统计词频 4 词云 5 提取特征 6 用sklearn进行训练 1 数据准备 数据样例如下, 数据总量为7.7万+: 本节通过一个实战的例子来展示文本分析的最简单流程。首先设定因变量为原始数据中的"评分"。自变量是"评价内容",这里根据评价内容提取TF-IDF特征。之后,通过评价内容的特征建模预测下整体评分。 以上只是最...

LeetCode 150. 逆波兰表达式求值

题目描述 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。 换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1: 输入:[“2”, “1”, “+”, “3&r...

猜你喜欢

并查集原理及应用

并查集 树形的数据结构,每个集合有其代表节点,代表节点相同的元素属于同一集合。 find:通过查找节点的代表节点,判断节点所属集合。 union:合并两集合,小集合合并到大集合,使用大集合的代表节点。 在find的递归过程中,让路过节点的父节点直接赋值为代表节点,节省下次查找时间,如图所示。 计算岛的个数 遍历二维数组,遇到1时就将所相连的1都改为2,看看遇到多少次1,就是岛的数量。改数时使用回溯...

linux nutch1.0安装配置

1,下载nutch1.0 下载地址:http://archive.apache.org/dist/nutch/,下载这个文件nutch-1.0.tar.gz   2,上传到服务器 上传位置:/home/www/,解压nutch-1.0.tar.gz #tar -xvf nutch-1.0.tar.gz 重命名 #mv nutch-1.0 nutch   3,修改配置文...

如何搭建自己的博客?附加美化

如何搭建自己的blog?附加美化 前言: 之前在腾讯云以学生优惠租了一年的服务器,还买了一年的域名,忽然觉得不能闲置着域名,所以搭建了个博客,过程也遇到了很多的问题,望在此阐述,予以他人帮助,祝好~ 准备工作:使用Xshell连接上Linux服务器,我的是centos系统,方便进行操作。使用Xftp连接上Linux服务器,方便传输文件。 安装apache服务器:yum install httpd ...

rabbitmq五种模式详解(含实现代码)

1.简单模式 当生产端发送消息到交换机,交换机根据消息属性发送到队列,消费者监听绑定队列实现消息的接收和消费逻辑编写.简单模式下,强调的一个队列queue只被一个消费者监听消费. 1.1 结构   生产者:生成消息,发送到交换机 交换机:根据消息属性,将消息发送给队列 消费者:监听这个队列,发现消息后,获取消息执行消费逻辑 1.2应用场景 常见的应用场景就是一发,一接的结构 例如: 手机...

AndroidStudio 常用配置

1. 设置主题&左侧导航栏字体 AndroidStudio->Preferences(下同) 2. 设置字体大小 3. 取消竖线 间距设置大些 4. 控制台字体大小 5. 修改LogCat颜色 LogCat 色值 Verbose BBBBBB Debug 48BB31 Info 0070BB Warn BBBB23 Error FF0006 Assert 8F0005 5. 修改变量...