数据结构-哈希表(哈希集合)

哈希表(本篇主要讲哈希集合)

部分内容来源于博主@SnailMann

前提

在实际编程中,我们常常面临着两个问题:存储和查询,这两个过程的效率往往制约着整个程序的效率,而我们常见的存储数据的数据结构比如线性表,树,图等,数据在结构中的位置往往是不明确的,当我们在这些数据结构中要查询一个数据,都避免不了去执行查询算法,去遍历数据结构,拿关键字和结构中的数据进行一一比较,从而得到想要的数据,我们就希望能不能不通过比较就能获得我们想要的结果呢?

答案是有的,不通过任何比较,一次存储便能取得所查记录,但这就必须在记录的存储位置和他的关键字之间建立一个确定的对应关系f,使得每个关键字和结构中的唯一的存储位置相对应,这个关系就是我们所说的哈希函数f(x),在这个思想上建立起来的表就成为哈希表。

介绍

哈希表是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表:哈希集合和哈希映射。

哈希集合是集合数据结构的实现之一,用于存储非重复值。
哈希映射是映射 数据结构的实现之一,用于存储(key, value)键值对。
在标准模板库的帮助下,哈希表是易于使用的。大多数常见语言(如Java,C ++ 和 Python)都支持哈希集合和哈希映射。

通过选择合适的哈希函数,哈希表可以在插入和搜索方面实现出色的性能。

原理

哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说,

当我们插入一个新的键时,哈希函数将决定该键应该分配到哪个桶中,并将该键存储在相应的桶中;
当我们想要搜索一个键时,哈希表将使用相同的哈希函数来查找对应的桶,并只在特定的桶中进行搜索。
在这里插入图片描述
在示例中,我们使用 y = x % 5 作为哈希函数。让我们使用这个例子来完成插入和搜索策略:

插入:我们通过哈希函数解析键,将它们映射到相应的桶中。

  • 例如,1987 分配给桶 2,而 24 分配给桶 4。

搜索:我们通过相同的哈希函数解析键,并仅在特定存储桶中搜索。

  • 如果我们搜索 1987,我们将使用相同的哈希函数将1987 映射到 2。因此我们在桶 2 中搜索,我们在那个桶中成功找到了 1987。
    例如,如果我们搜索 23,将映射 23 到 3,并在桶 3 中搜索。我们发现 23 不在桶 3 中,这意味着 23 不在哈希表中。

设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合

具体地说,你的设计应该包含以下的功能

add(value):向哈希集合中插入一个值。
contains(value) :返回哈希集合中是否存在这个值。
remove(value):将给定值从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。

示例:

MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // 返回 true
hashSet.contains(3); // 返回 false (未找到)
hashSet.add(2);
hashSet.contains(2); // 返回 true
hashSet.remove(2);
hashSet.contains(2); // 返回 false (已经被删除)

注意:

所有的值都在 [1, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希集合库。

class MyHashSet {
public:
    /** Initialize your data structure here. */
    vector<bool> hash;
    MyHashSet() {
        hash = vector<bool>(1000001, false);
    }
    
    void add(int key) {
        hash[key] = true;
    }
    
    void remove(int key) {
        if(hash[key])
        {
            hash[key] = false;
        }
        return;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        if(hash[key])
        {
            return true;
        }
        return false;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射

具体地说,你的设计应该包含以下的功能

put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更新这个值。
get(key):返回给定的键所对应的值,如果映射中不包含这个键,返回-1。
remove(key):如果映射中存在这个键,删除这个数值对。

示例:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // 返回 1
hashMap.get(3); // 返回 -1 (未找到)
hashMap.put(2, 1); // 更新已有的值
hashMap.get(2); // 返回 1
hashMap.remove(2); // 删除键为2的数据
hashMap.get(2); // 返回 -1 (未找到)

注意:

所有的值都在 [1, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。

class MyHashMap {
public:
    /** Initialize your data structure here. */
    vector<int> hash;
    MyHashMap() {
        hash = vector<int>(1000001,-1);
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        hash[key] = value;
    } 
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        if(hash[key] == -1)
        {
            return -1;
        }else{
            return hash[key];
        }
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        if(hash[key] == -1)
        {
            return;
        }else
        {
            hash[key] = -1;
        }
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

这两道题主要用于理解哈希集合和哈希映射的概念

哈希集合在c++ stl中的应用

#include <unordered_set>                // 当时用set时引用的模板库

int main() {
    // 创建一个哈希集合
    unordered_set<int> hashset;   
    // 插入新的关键字
    hashset.insert(3);
    hashset.insert(2);
    hashset.insert(1);
    // 删除关键字
    hashset.erase(2);
    // 判断关键字是否在哈希集合中,如果在方法返回负数
    if (hashset.count(2) <= 0) {
        cout << "关键字2不在哈希集合中" << endl;
    }
    // 得到哈希集合的大小
    cout << "The size of hash set is: " << hashset.size() << endl; 
    // 遍历哈希集合,注意要以指针的形式
    for (auto it = hashset.begin(); it != hashset.end(); ++it) {
        cout << (*it) << " ";
    }
    cout << "are in the hash set." << endl;
    // 清除哈希集合
    hashset.clear();
    // 判断哈希结合是否为空
    if (hashset.empty()) {
        cout << "hash set is empty now!" << endl;
    }
}

经典例题1

  • 存在重复元素
  • 给定一个整数数组,判断是否存在重复元素。
  • 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。
  • 示例 :

输入: [1,2,3,1]
输出: true
示例 2:

输入: [1,2,3,4]
输出: false
示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

分析;这道题我们使用标准库中的查重模板,顺序将数组中的元素压入哈希集合中,在利用count()方法判断后序函数是否在哈希集合中即可

// leecode 存在重复元素
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hashset;
        for(int i = 0; i < nums.size(); i++)
        {
            if(hashset.count(nums[i]) > 0)
            {
                return true;
            }
            else{
                hashset.insert(nums[i]);
                
            }
        }
        return false;
    }
};

经典例题2

  • 只出现一次的数字

  • 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

  • 说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

分析:因为在数组中,元素出现的次数不是一次就是两次,我们这里利用哈希集合顺序将元素压入哈希集合中,利用count()方法判断后序元素是否在哈希集合中,如果在,便删除哈希集合中的元素,如果不在,将后序元素压入哈希集合中,到最后,哈希集合中只会存在一个元素,将此元素输出即可。

// leetcode 只出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set <int> hashset;
        for(int i = 0; i < nums.size(); i++)
        {
            if(hashset.count(nums[i]) > 0)
            {
                hashset.erase(nums[i]);
            }else{
                hashset.insert(nums[i]);
            }
        }
        return *hashset.begin();
      
    }
};

经典例题3

  • 两个数组的交集
  • 给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序

分析:创建两个哈希集合,压入nums1和nums2的所有元素,因为哈希集合中不允许存在相同的元素,所以在全部压入的时候会自动甩出相同的元素,最后再一次判断重复元素即可

// leetcode 两个数组的交集
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        vector<int> ret{};
        unordered_set<int> nums1_set{nums1.cbegin(), nums1.cend()}; 
        unordered_set<int> nums2_set{nums2.cbegin(), nums2.cend()};
        for (auto &num : nums2_set) {
            if (nums1_set.count(num) > 0) 
            {
                ret.push_back(num);
            }
        }

        return ret;
    }
};

经典例题4

  • 快乐数问题(然而被这个问题搞得一点都不快乐)

  • 编写一个算法来判断一个数是不是“快乐数”。

  • 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。

示例:

输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路:利用哈希集合,将每次计算的和,例如82,68等等压入哈希集合中,如果某一次的计算出的总和出现在了哈希集合中,则证明这个数不是快乐数,这是跳出无限循环的关键,如果计算出的和等于1,则返回true

// leetcode 快乐数(今天你快乐了嘛)
class Solution {
public:
    unordered_set<int> hashset;
    int m;
    bool isHappy(int n) {
        while(n != 1)
        {
            if(hashset.count(n) > 0)
            {
                return false;
            }else
            {
                int sum = 0;
                hashset.insert(n);
                while( n != 0)
                {
                    sum += (n % 10) * (n % 10);
                    n = n / 10;
                }
                n = sum;
            }
        }
        return true;
    }
};
版权声明:本文为aiyaxinlala原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/aiyaxinlala/article/details/90142420

智能推荐

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

猜你喜欢

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...

小demo:slideDown()实现二级菜单栏下拉效果

效果如下,鼠标经过显示隐藏的二级菜单栏 但是这样的时候会存在一个问题,就是鼠标快速不停移入移出会导致二级菜单栏闪屏现象,一般需要使用stop()来清除事件  ...

基于docker环境的mysql主从复制

1、安装docker 可以参考之前的博客,之前写过了~ 2、拉取mysql镜像 3、创建mysql01和mysql02实例 主: 从: 4、进入容器修改配置 1)修改主数据库配置 进入主数据库容器 切换到 etc/mysql/目录下 查看可以看到my.cnf文件,使用vim编辑器打开,但是需要提前安装 安装vim命令: 安装成功后,修改my.cnf文件 新增配置后的my.cnf: binlog 日...

机器学习算法之决策树

原文:http://www.jianshu.com/p/6eecdeee5012 决策树是一种简单高效并且具有强解释性的模型,广泛应用于数据分析领域。其本质是一颗由多个判断节点组成的树,如: 决策树 在使用模型进行预测时,根据输入参数依次在各个判断节点进行判断游走,最后到叶子节点即为预测结果。 如何构造决策树 决策树算法的核心是通过对数据的学习,选定判断节点,构造一颗合适的决策树。 假设我们从用户...