哈希表的封装和位图

2024-09-09 03:44
文章标签 封装 哈希 位图

本文主要是介绍哈希表的封装和位图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 2 封装
    • 2.1 基础框架
    • 2.2 迭代器(1)
    • 2.3 迭代器(2)
  • 3. 位图
    • 3.1 问题引入
    • 3.2 左移和右移？
    • 3.3 位图的实现
    • 3.4 位图的题目
    • 3.5 位图的应用

2 封装

2.1 基础框架

文章

有了前面map和set封装的经验，容易写出下面的代码

// UnorderedSet.h
#pragma once
#include "HashTable.h"
template <class K, class Hash = HashFunc<K>>
class UnorderedSet
{// 返回keystruct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:bool insert(const K& key){return _ht.Insert(key);}
private:HashTable<K, K, SetKeyOfT, Hash> _ht;
};

// UnorderedMap.h
#pragma once
#include "HashTable.h"
template <class K, class V,  class Hash = HashFunc<K>>
class UnorderedMap
{// 返回pair的first,即keystruct MapKeyOfT{const K& operator()(const pair<K, V> &kv){return kv.first;}};
public:bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}private:HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
};

// HashTable.h
template <class T>
struct HashNode
{HashNode(const T& data): _data(data), _next(nullptr){}HashNode* _next;T _data;
};
// UnorderedMap->HashTable<K, pair<K, V>>
// UnorderedSet->HashTable<K, K>
template <class K, class T, class KeyOfT , class Hash>
class HashTable
{typedef HashNode<T> Node;
public:// ...bool Insert(const T& data){// 如果已经有该元素了，返回falseif (Find(kot(data)))	return false;size_t sz = _table.size();// 负载因子设置到1if (_table.size() == _n){size_t newSz = sz * 2;vector<Node*> newTable;newTable.resize(newSz, nullptr);for (size_t i = 0; i < sz; ++i) {Node* cur = _table[i];while (cur) {Node* next = cur->_next;size_t hashI = hf(kot(cur->_data)) % newSz;// 头插到新链表cur->_next = newTable[hashI];newTable[hashI] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashI = hf(kot(data)) % sz;Node* newNode = new Node(data);// 头插newNode->_next = _table[hashI];_table[hashI] = newNode;++_n;return true;}// ...
private: vector<Node*> _table;size_t _n;Hash hf;KeyOfT kot;
};

其中HashTable.h中部分代码已经省略，详细见文章

2.2 迭代器(1)

写法1

// HashTable.h
template <class T>
struct __HTIterator
{typedef HashNode<T> Node;typedef __HTIterator<T> Self;Node* _node;vector<Node*>& _table;	// 方便找下一个桶size_t _hashI;		// 当前找到哪个桶了__HTIterator(Node* node, vector<Node*>& table, size_t hashI): _node(node), _table(table), _hashI(hashI){}Self& operator++(){if (_node->_next) {// 当前桶还有节点，走到下一个节点_node = _node->_next;}else {// 当前桶没有节点了，去找下一个桶++_hashI;while (_hashI < _table.size()) {if (_table[_hashI] != nullptr) {// 找到了非空节点_node = _table[_hashI];break;}++_hashI;}// 没有下一个有节点的桶了if (_hashI == _table.size()) {_node = nullptr;	// 让nullptr充当end()}}return *this;}bool operator!=(const Self& s){return _node != s._node;}T& operator*(){return _node->_data;}T* operator->(){return &(_node->_data);}
};template <class K, class T, class KeyOfT , class Hash = HashFunc<K>>
class HashTable
{// ...typedef __HTIterator<T> Iterator;Iterator begin(){// 找到第一个有存值的桶，传给迭代器for (size_t i = 0; i < _table.size(); i++) {if (_table[i] != nullptr) {return Iterator(_table[i], _table, i);}}// 找到最后还没有找到，证明是空哈希表return end();}Iterator end(){return Iterator(nullptr, _table, -1);}// ...
}

2.3 迭代器(2)

// 因为后面的__HTIterator使用了HashTable这个类，向上找找不到，所以需要前置声明
template <class K, class T, class KeyOfT, class Hash>
class HashTable;template <class K, class T, class KeyOfT, class Hash>
struct __HTIterator
{typedef HashNode<T> Node;typedef __HTIterator<K, T, KeyOfT, Hash> Self;Node* _node;HashTable<K, T, KeyOfT, Hash>* _ht;	// 方便找下一个桶size_t _hashI;		// 当前找到哪个桶了__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* ht, size_t hashI): _node(node), _ht(ht), _hashI(hashI){}Self& operator++(){if (_node->_next) {// 当前桶还有节点，走到下一个节点_node = _node->_next;}else {// 当前桶没有节点了，去找下一个桶++_hashI;while (_hashI < _ht->_table.size()) {if (_ht->_table[_hashI] != nullptr) {// 找到了非空节点_node = _ht->_table[_hashI];break;}++_hashI;}// 没有下一个有节点的桶了if (_hashI == _ht->_table.size()) {_node = nullptr;	// 让nullptr充当end()}}return *this;}// ...
};template <class K, class T, class KeyOfT, class Hash>
class HashTable
{typedef HashNode<T> Node;template <class K, class T, class KeyOfT, class Hash>friend struct __HTIterator;		// 让__HTIterator成为HashTable的友元，因为用到了_table这个私有属性
public:typedef __HTIterator<K, T, KeyOfT, Hash> Iterator;Iterator begin(){// 找到第一个有存值的桶，传给迭代器for (size_t i = 0; i < _table.size(); i++) {if (_table[i] != nullptr) {return Iterator(_table[i], this, i);}}// 找到最后还没有找到，证明是空哈希表return end();}Iterator end(){return Iterator(nullptr, this, -1);}// ...
}

const迭代器不再实现，太复杂了。

3. 位图

概念：所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

3.1 问题引入

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

  1. 遍历，时间复杂度O(N)

  2. 排序(O(NlogN))，利用二分查找: logN

  3. 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

​ image-20240908131159204

可以计算一下，40亿个数，需要开2^32bit，即512MB

3.2 左移和右移？

image-20240908154458368

vs是以小端字节序存储的，左移指的是像高地址移动，右移是指向低地址移动，并不是按移动的方向定义的

执行完i = 1

image-20240908155207271

执行完i <<= 8

image-20240908155231047

image-20240908155547251

3.3 位图的实现

// N表示需要多少bit位
template<size_t N>
class MyBitset
{
public:MyBitset(){_bits.resize(N / 32 + 1, 0);}/*把x映射的位置1* x在数组的第几个整形呢？		i = x / 32* x在这个整形的第几个位呢？   j = x % 32*/ void set(size_t x) {size_t i = x / 32;size_t j = x % 32;// 或等上1<<j_bits[i] |= (1 << j);}// 把x映射的位置0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;// 与等上~(1<<j)_bits[i] &= (~(1 << j));}// 检查x所在的bit是0还是1bool test(size_t x){size_t i = x / 32;size_t j = x % 32;// 与上1return _bits[i] & (1 << j);}
private:vector<size_t> _bits;
};

image-20240908162435739

上面的3.1的问题，我们可以开一个bitset来解决

// solution 1
MyBitset<0xffffffff> bs;
// solution 2
MyBitset<-1> bs2;

3.4 位图的题目

  1. 给定100亿个整数，设计算法找到只出现一次的整数？

使用两个bitset，00表示出现0次，01表示出现1次，10表示出现2次或者2次以上

template<size_t N>
class TwoBitset
{
public:/** 00->01* 01->10* 10->same*/void set(size_t x){if (!_bs1.test(x) and !_bs2.test(x)) {_bs2.set(x);}else if (!_bs1.test(x) and _bs2.test(x)) {_bs1.set(x);_bs2.reset(x);}}/* 打印出现一次的数字 */void PrintOnce(){for (size_t i = 0; i < N; i++) {if (!_bs1.test(i) and _bs2.test(i))cout << i << ' ';}cout << endl;}private: MyBitset<N> _bs1;MyBitset<N> _bs2;
};
  1. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

与上面类似：将这些整数各自映射到一个位图，一个值在两个位图都存在，则是交集

  1. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

也是一样，两个位图，00表示出现0次，01表示出现1次，10表示出现2次，11表示出现3次及以上

3.5 位图的应用

  1. 快速查找某个数据是否在一个集合中
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记

这篇关于哈希表的封装和位图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1150065。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...
JavaSE——封装、继承和多态

JavaSE——封装、继承和多态

1. 封装 1.1 概念      面向对象程序三大特性：封装、继承、多态 。而类和对象阶段，主要研究的就是封装特性。何为封装呢？简单来说就是套壳屏蔽细节 。     比如：对于电脑这样一个复杂的设备，提供给用户的就只是：开关机、通过键盘输入，显示器， USB 插孔等，让用户来和计算机进行交互，完成日常事务。但实际上：电脑真正工作的却是CPU 、显卡、内存等一些硬件元件。
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
封装MySQL操作时Where条件语句的组织

封装MySQL操作时Where条件语句的组织

在对数据库进行封装的过程中，条件语句应该是相对难以处理的，毕竟条件语句太过于多样性。 条件语句大致分为以下几种： 1、单一条件，比如：where id = 1; 2、多个条件，相互间关系统一。比如：where id > 10 and age > 20 and score < 60; 3、多个条件，相互间关系不统一。比如：where (id > 10 OR age > 20) AND sco
阅读更多...
PHP: 深入了解一致性哈希

PHP: 深入了解一致性哈希

前言 随着memcache、redis以及其它一些内存K/V数据库的流行，一致性哈希也越来越被开发者所了解。因为这些内存K/V数据库大多不提供分布式支持(本文以redis为例)，所以如果要提供多台redis server来提供服务的话，就需要解决如何将数据分散到redis server，并且在增减redis server时如何最大化的不令数据重新分布，这将是本文讨论的范畴。 取模算法 取模运
阅读更多...
哈希表题总结

哈希表题总结

哈希表题总结 hot100两数之和字母异位词分组最长连续序列 hot100 两数之和 题目链接： 1.两数之和 代码： class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();int n = nums.length;for
阅读更多...
【吊打面试官系列-Redis面试题】说说 Redis 哈希槽的概念？

【吊打面试官系列-Redis面试题】说说 Redis 哈希槽的概念？

大家好，我是锋哥。今天分享关于 【说说 Redis 哈希槽的概念？】面试题，希望对大家有帮助； 说说 Redis 哈希槽的概念？ Redis 集群没有使用一致性 hash,而是引入了哈希槽的概念，Redis 集群有 16384 个哈希槽，每个 key 通过 CRC16 校验后对 16384 取模来决定放置哪个槽， 集群的每个节点负责一部分 hash 槽。
阅读更多...
LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入：nums = [1,2,1,1,3],
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2