精华内容
下载资源
问答
  • 哈希表的用法
    千次阅读
    2022-07-29 10:30:03

    哈希表

    哈希表是一种很常见的数据结构,我现在平时刷算法题一般使用C++刷(不要问我为什么,懂的都懂)。C++关于哈希表有很多数据结构,平时使用的比较多的有unordered_set 跟 unordered_map。其中unordered_map 存储的是键值对。
    其实我们在某些情况下可以使用数组构建哈希表(具体是哪些情况的呢,自行搜索)。但是数组的大小是受限制的,而且如果元素很少却哈希值很大的话会造成内存空间的浪费(至于为什么会这样请自行搜索)。

    为什么要用哈希表

    如果现在做哈希表的题目,是因为按专题刷的哈希表的题目,所以会直接用哈希表。但是遇到一道新的题目,没有标签,怎么想到使用哈希表呢?
    咱们要清楚一点的就是,一般哈希表都是用来快速判断一个元素是否出现在集合里。

    遍历

    for (auto i = hash.begin(); i != hash.end(); i++)

    如果是unordered_map,遍历的时候,可以访键值i ->first或者是i->second;

    查找

    查找某个元素是否在哈希表中,可以使用hash.find(x) != hash.end(),或者hash.count(x) > 0
    注意:hash.count(x) 的数值只有 0 和 1。所以不能通过hash.count(x)来表示x在hash 中出现的次数。

    插入

    在unordered_set 中插入元素,可以用hash.insert(key)
    在unordered_map中插入元素,可以使用hash[key = value

    删除

    在unordered_set 跟unordered_map 中删除元素,都用hash.erase(key)
    注意,在unordered_map 中,即使hash[key] == 0,如果之前已经将key存入到hash中,然后通过hash[key] -- 使得hash[key] == 0,hash 中还会存在key ,也就是说此时hash.count(key) == 1
    在个别场景下,可能需要一次性删除 unordered_map 容器中存储的所有键值对,可以使用clear()方法,其语法格式如下:

    void clear()
    {
    hash.clear();
    }

    我觉的刷题会这些基本的操作足够了,想深层次的了解哈希表的话自行查阅资料吧。

    更多相关内容
  • booleancontains(Objectvalue)——-确定哈希表内是否包含了给定的对象,若有返回true,否则false。

    目录

    参考“时间、流水”博主的文章,稍微多加了一点东西。原文链接:https://blog.csdn.net/qq_52445563/article/details/125835619
    侵权删

    1.1 初始化

    HashMap<object1, object2> hashmap = new HashMap<object1, object2>();

    1.2 添加新键值对

    hashmap.put(object1, object2);

    1.3 在原有的基础上增加

    hashmap.put(object1, hashmap.getOrDefault((object1, 0) + 1));

    1.4 访问元素的value

    object2 obj2 = hashmap.get(object1);

    1.5 判断存在

    boolean contains(Object value) ——-确定哈希表内是否包含了给定的对象,若有返回true,否则false
    Boolean bool = hashmap.containsKey( Object key );
    Boolean bool = hashmap.containsValue( Object value );

    1.6 删除元素

    hashmap.remove(object1);

    1.7 清空元素

    hashmap.clear();

    1.8 计算大小

    int size = hashmap.size();

    1.9 遍历

    for(object1 obj1 : hashmap.keySet()){
    System.out.println(obj1 + hashmap.get(obj1));
    }
    for(object2 obj2 : hashmap.values()){
    System.out.println(obj2);
    }

    1.10 判断为空

    Boolean bool = hashmap.isEmpty();

    展开全文
  • 哈希表使用

    2021-07-27 21:54:11
    哈希表一般用于存储键值对即key-val 一般是由数组和链表构成 常用操作 //查找是否存在键值 unordered_map<int,int> hash; hash.find(key)==hash.end(); hash.count(key)==1; 例题 290. Word Pattern ...

    哈希表一般用于存储键值对即key-val

    一般是由数组和链表构成

    常用操作

    //查找是否存在键值
    unordered_map<int,int> hash;
    hash.find(key)==hash.end();//find返回的是迭代器
    hash.count(key)>=1;//说明存在

    例题

    290. Word Pattern

    由于C++中的哈希表不能查找某一值的存在,只能查找某一键是否存在,所以C++需要两个哈希表来相互存储。

    class Solution {
    public:
        //将字符串传入到数组中
        vector<string> split(string &s) {
    	    string temp;
    	    vector<string> v;
    	    for (int i = 0; i < s.size(); i++) {
    		    if (s[i] != ' ')temp += s[i];
    		    else {
    			v.push_back(temp);
    			temp = "";
    		    }
    	    }
    	    v.push_back(temp);
    	    return v;
        }
    
        bool wordPattern(string pattern, string s) {
            //两个哈希表双向存储
            //事实上如果C++STL中如果有类似于java的containsKey函数,只需要一个哈希表就足够
            unordered_map<string,char> hash1;
            unordered_map<char,string> hash2;
            vector<string> v = split(s);
    
            if(v.size()!=pattern.size()) return false;  
    
            for(int i=0;i<pattern.size();i++){
                 //如果存在并且相互对应
                if(hash1.count(v[i]) && hash2[pattern[i]] != v[i]) return false;
    
                if(hash2.count(pattern[i]) && hash1[v[i]] != pattern[i]) return false;
                
                //双向映射
                hash1[v[i]] = pattern[i];
    
                hash2[pattern[i]] = v[i];
                
            }
            return true;
        }
    };

     C++中没有split函数对字符串进行划片,手写辅助函数split()。

    451. 根据字符出现频率排序

    这个需要根据字符数目排序,但是哈希表不能满足排序的需求

     

    哈希表中存储的数据经常需要排序,一个常见的操作就是把哈希表中的数据用vector进行存放,vector可以很容易的根据一定的规则进行排序。

    在定义排序规则的时候,传入的应该是vector内部的子类型数据,对于vector<pair<char,int>>,在排序的时候传入的参数是pair<char,int>类型的数据。

    class Solution {
    public:
        static bool cmp(pair<char,int> &a,pair<char,int> &b){
            return a.second>b.second;
        }
    
        
        string frequencySort(string s) {
            string res;
            unordered_map<char,int>hash;
            vector<pair<char,int>> v;
            for(auto c:s) hash[c]++;
    
            for(auto item:hash) v.push_back(pair(item.first,item.second));
    
            sort(v.begin(),v.end(),cmp);
    
            for(int i=0;i<v.size();i++){
                while(v[i].second--)res+=v[i].first;
            }
    
            return res;
    
        }
    };

    未完待续!

    展开全文
  • 哈希表使用总结

    2022-03-03 17:13:31
    最近完成哈希表的算法题练习,对哈希表使用场景有了进一步的深入。 哈希表简介 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。 也就是说,它通过把关键码值映射到表中...

    刷题日记

    最近完成哈希表的算法题练习,对哈希表的使用场景有了进一步的深入。

    哈希表简介

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。
    	也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
    	这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,
    	则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
    
    • 以上来自百度百科的介绍,
    • 简单来说,哈希表和散列表是一个东西,都是根据关键码的值直接进行访问的数据结构。
    • 举个栗子,数组其实就是一个哈希表,通过数组角标(关键码的值)直接进行访问的数据结构

    常见哈希表

    • 常见的哈希表,这里就说一下我到现在用的比较多的3种哈希表,
    • 分别是:数组、set集合、map集合
      小声bb,因为我是资深的java的萌新,其他语言有没有set和map就不清楚了,不过语言之间是相通的啦,应是有类似的数据结构的啦~
    • 数组相信大家都很熟,这里就简单介绍一下set和map的特性,
    • set:集合内元素:不可以重复,无序
    • map:map是双列集合,存储的是键值对,保证键的唯一性

    使用场景

    0. 大体上

    • 哈希表的使用场景,从定义上来看(百度百科上说的可能比较清楚),是一种花费空间来换取时间的数据结构,所以当我们需要快速判断一个元素是否出现在集合内的时候就可以考虑使用哈希表来帮助我们

    常用哈希表种类的选择

    • 根据俺这几天的学习经验,以上三种哈希表使用的场景还是大有不同滴~。
      在这里插入图片描述

    1. 数组

    • 数组作为哈希表来使用的话,有两个地方需要注意,一个是哈希函数,一个是空间
    • 所以,这个哈希函数是个啥嘞?
      在这里插入图片描述

    1.1 哈希函数

    哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。
    	一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,
    	因此,在结构中查找记录时需进行一系列和关键字的比较。
    这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。
    	理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,
    	使每个关键字和结构中一个唯一的存储位置相对应。
    
    • 以上是百度百科的定义
    • 简单来说,哈希函数就是一个映射关系,就比如你要把你同班同学的名字映射到哈希表上的索引,然后就可以通过查询索引下标来找到你班上的某某某,如下图:
      在这里插入图片描述
    • 通过哈希函数将要存放的数据与哈希表的索引下标形成关联。

    • 咳咳,回到数组上来
    • 既然选择数组作为哈希表,那么首先要解决的就是映射问题
    • 在力扣的242.有效的字母异位词中就可以使用数组作为哈希表,映射关系也是巧妙的利用题中的提示:两字符串中仅包含小写字母,通过char与int数据类型之间的关系,利用ASCII码,
    • 将 (字符 - ‘a’) 作为哈希函数,实现char到哈希表索引的转换,这也是经常使用的映射手段之一,
    • 基本上碰到字母就有点暗示使用数组的味道在里面了。

    1.2 空间

    • 再来就是空间的考量了,
    • 数组的大小是受限的,
    • 也就是说,1. 如果我们在无法确定需要存放数据的数量的时候;2. 很难将目标映射满数组的时候,或者说如果数组空间够大,但哈希值比较少、特别分散、跨度非常大(会造成空间的浪费),是不适合使用数组作为哈希表的。

    2. set和map

    • 需要使用set(集合)和map(映射)的时候主要是考虑到这两种东东的特性,再来就是处理速度
    • 一般来说能用数组的就用数组,不能用才会考虑这以上两位
    • 因为后面两者占用空间,在同等情况下要比数组打,而且速度不如数组,
    • set把数值映射到key上都要做hash计算的,map也需要做相应的hash函数运算,在数据量比较大的情况下,会有很大的时间差异的!!

    2.1 set

    • set主打的就是元素的唯一性,当有需要限定查找集合中的元素不能重复的时候,我们就应该考虑使用set集合了,
    • set在各大语言中也有一些细分,像java就有HashSet和TreeSet,代表着无排序需求的和有排序需求的,其他语言也有诸如此类的东西存在,这里就不做过多介绍

    2.2 map

    • map使用的场景,无非是前面两个兄弟用不了,这里就一口气把他们的缺点bb一下
    • 数组大小受限制,如果元素很少,而哈希值又比较大会造成内存空间的浪费
    • set集合里面能放的元素只有一个key,而不能记录其他信息,就比如有一些题目不仅需要记录元素本身,还需要记录该元素出现的次数,这个时候set就分身乏术了
    • 而map是以键值对的形式存储的,所以可以在记录元素本身的时候,还能记录与元素相关的其他信息
    • 啊!map这么牛,还要他们两啥事啊?以后做题都用map不就完事了。好嘛通关秘籍+1·。
      在这里插入图片描述
    • 确实map可以适用大多数情况,但是使用map的空间消耗要比数组大一些,因为map要维护红黑树或者符号表(map内部的实现底层,这里就不多说了,感兴趣的小伙伴可以去了解一下),而且还要做哈希函数的运算。所以能用数组用数组嘛,不能使再看需求选择其他俩哥么就行了

    总结

    • 虽然map是万能的,但是却不见得是最优的,根据切实需要,选择set和数组,才是一个资深菜姬该有的风度和浪漫~
    • 最后祝还在努力的小伙伴们都能去到自己想去的地方,拿到自己想要的offer,既然都看到最后了,还麻烦高抬贵手点个赞(* ̄︶ ̄)~

    在这里插入图片描述

    展开全文
  • 只有干货没废话,Java哈希表常用用法
  • C语言哈希表用法

    万次阅读 多人点赞 2020-07-12 11:56:03
    哈希表在头文件"uthash.h"中已经有了,只需要简单学习一下用法即可。 1,哈希结构体 #include "uthash.h" typedef struct { int key; int value; UT_hash_handle hh; } Hash; Hash *hash = NULL; 其中UT_...
  • Java哈希表及其应用

    2022-02-23 09:46:30
    文章目录哈希表相关定义java哈希表的构造方法 哈希表相关定义 哈希表(hash table):也称散列表,是存储群体对象的集合类结构。是根据**键(Key)**而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个...
  • 换句话说, 哈希表用于创建使用哈希表进行存储的集合。它通常通过计算每个键的哈希码来优化查找, 并自动将其存储到另一个存储篮中, 并且当你当时从哈希表访问值时, 它会将哈希码与指定的键进行匹配。这是非通用类型的...
  • 前言 JDK8之前,底层采用“数组+链表”实现哈希...为了学习和测试哈希表,本文使用自制的学生Student类,存入HashSet中,再遍历其中的元素。通过在Student类中覆写hashCode和equals方法,让哈希表中不存在重复的元素。
  • C语言库函数的哈希表使用方法

    千次阅读 2022-04-14 12:54:32
    C语言库函数的哈希表使用方法
  • 本文实例讲述了C#使用foreach遍历哈希表(hashtable)的方法。分享给大家供大家参考。具体实现方法如下: using System; using System.Collection; namespace HashSampleApplication1 { class Program { static ...
  • C++之哈希表使用

    万次阅读 多人点赞 2019-07-13 22:31:46
    C++中的STL提供了hash_map来实现哈希表功能,在介绍hash_map的使用方法之前,我们先从哈希函数和哈希冲突来了解哈希表。 一、 哈希函数 所谓哈希函数就是从关键字(Key)到值(Value)的映射: Value=H(Key)Value=H...
  • Leetcode-哈希表

    2022-01-21 22:27:43
    方法一:可采用哈希表, 首先将数组中的所有数存在哈希表里,第二遍历数组,依次判断数组中的元素的前一个值是否在hash表中,直到数组中的元素的前一个值不在hash表中,则该值为某个连续序列的第一个值,则可看从该...
  • 一个完全在 MATLAB 中实现的通用哈希表,具有 O(1) 性能。 允许使用几乎任何任意 MATLAB 类型作为键或值,包括用户定义的类。 您可以通过提供自定义相等和哈希码函数来自定义行为。 一般来说,不如不允许任意类型...
  • 主要介绍了C#中哈希表(HashTable)用法,简单讲述了哈希表的原理并结合实例形式详细分析了C#针对哈希表进行添加、移除、判断、遍历、排序等操作的实现技巧,需要的朋友可以参考下
  • Java哈希表常用操作

    2021-09-30 23:14:55
    哈希表 理想的情况是希望不经过任何比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的关系,使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时,只要根据这个...
  • 哈希表是什么哈希表(散列表)是根据键(Key)直接访问内存存储位置的数据结构。根据键(Key)值将数据映射到内存中一个位置的函数称为哈希函数,根据哈希函数建立的记录数据的表称为哈希表哈希表的特点若关键字为...
  • 2) 添加 支持自定义数据值, 以及使用范例(用法比较另类) 0.4版(2018.11.22) 1) 修复 由于WIN10下,文本比较SSE4.2会产生奔溃,屏蔽掉文本比较SSE4.2 0.3版(2018.11.21) 1) 修复 取文本长度 AVX2和SSE2 修改成内存...
  • 一文看懂哈希表并学会使用C++ STL 中的哈希表

    千次阅读 多人点赞 2021-05-16 16:41:34
        最近在刷题以及做编程练习的作业时经常会用到哈希表,碰到一些想用的函数...本篇哈希表的作用如何使用STL库中的哈希表STL中哈希表的常用函数 哈希表的作用 如何使用STL库中的哈希表 STL中哈希表的常用函数 ...
  • C++ 哈希表

    千次阅读 2021-02-22 20:35:28
    哈希表的基本介绍: 散列表( Hash table,也叫哈希表)是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,...
  • 哈希表也称为散列表,是用来存储群体对象的集合类结构。什么是哈希表数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种顺序...
  • 链式哈希表

    千次阅读 2022-05-24 10:23:24
    线性哈希表的缺陷 但是链式哈希表可以采用分段的锁,这样既保证了线程安全,又有一定的并发量,提高了效率。当前我们库里面无序的关联容器并没有实现多线程中的线程安全问题,就是并没有去加锁,但是这并不妨碍当...
  • 算法:哈希表

    2022-03-25 20:54:48
    哈希表简介 哈希表:也叫做散列表。...哈希表的关键思想是使用哈希函数,将键 key 和值 value 映射到对应表的某个区块中。可以将算法思想分为两个部分: 向哈希表中插入一个关键字:哈希函数决定该关键字的对应值应
  • 除留余数法 常用的处理冲突的方法 开放寻址法 再散列法 链地址法(拉链法) 建立一个公共溢出区 二、哈希表的简单实现 散列函数求法:除余留数法 哈希冲突的处理方式:拉链法 图源百度百科 员工类 public class ...
  • 哈希表简介

    2022-05-21 15:36:50
    哈希表简介
  • javascript中没有像c#,java那样的哈希表(hashtable)的实现。在js中,object属性的实现就是hash表,因此只要在object上封装点方法,简单的使用obejct管理属性的方法就可以实现简单高效的hashtable。
  • 哈希表的原理和使用(C++代码)

    万次阅读 多人点赞 2018-08-12 22:48:32
    概念 散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f,是的每个关键字key对应一个存储位置f(key)...采用散列技术将记录存储在一块连续的存储空间中,这块连续空间称为散列表或哈希表(Hash-Tab...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 249,013
精华内容 99,605
关键字:

哈希表的用法