低头赶路
敬事如仪
目录
1、Unordered 系列容器：哈希桶与高效查找
unordered_map
unordered_set
2、 哈希桶实现的高级封装
2.1 模板参数与类型泛化
2.2 迭代器的设计与实现
3、 容器的上层抽象与封装
3.1 unordered_set 的高效封装
3.2 unordered_map 的高效封装与扩展
4、 面试题解析与实践经验
1、Unordered 系列容器：哈希桶与高效查找
unordered_map 和 unordered_set 是以哈希桶为底层结构的容器，主要用于快速查找指定数据。与其他容器相比，它们在查找元素时提供了显著的性能提升，但也有一些特殊的限制和特点。
unordered_map
unordered_map 是一种基于哈希表实现的容器，用于存储键值对 <key, value>。其主要特点如下：
key 快速查找对应的 value，查找效率显著高于 map。无序存储：元素的存储顺序并非按插入顺序，而是根据 key 的哈希值决定的数组下标，因此是无序的。修改规则： key 一旦插入后不可修改，value 可以修改。提供 [ ] 运算符来访问或插入元素。迭代器：仅支持正向迭代器，无法反向迭代。性能特点：尽管查找速度非常快，但迭代速度较慢。 unordered_set
unordered_set 与 unordered_map 类似，但只存储 key，没有对应的 value。其主要特点如下：
key 快速判断元素是否存在，查找效率远高于 set。无序存储：与 unordered_map 一样，元素按照 key 的哈希值存储，存储顺序无特定顺序。修改规则： 只存储 key，不能修改 key 的值。不提供 [ ] 运算符进行元素访问。迭代器：同样只提供正向迭代器，不支持反向迭代。 常用接口
无论是 unordered_map 还是 unordered_set，它们都提供了一些相似的接口，便于用户进行高效操作。
迭代器接口：
| 函数 | 功能介绍 |
|---|---|
begin() | 返回容器第一个元素的迭代器 |
end() | 返回容器最后一个元素之后的位置的迭代器 |
cbegin() | 返回容器第一个元素的 const 迭代器 |
cend() | 返回容器最后一个元素之后位置的 const 迭代器 |
常用功能函数：
| 函数 | 功能介绍 |
|---|---|
find(const K& key) | 查找指定 key，返回对应元素的迭代器 |
count(const K& key) | 返回容器中 key 对应的元素个数 |
insert() | 向容器中插入元素 |
erase() | 删除指定元素 |
clear() | 清空容器中的所有元素 |
swap(unordered_map&) | 交换两个容器的元素 |
哈希桶操作：
| 函数 | 功能介绍 |
|---|---|
bucket_count() | 返回哈希桶的总数 |
bucket_size(size_t n) | 返回指定桶 n 中的元素数量 |
bucket(const K& key) | 返回指定 key 所在的桶编号 |
总结
unordered_map 适用于需要根据键值对进行快速查找的场景，支持对value 的修改，提供高效的查找性能，但迭代操作相对较慢。unordered_set 适用于去重或判断元素是否存在的场景，只存储 key，不支持随机访问，通过哈希表提供快速查找。 两者都以哈希桶为底层结构，提供高效的查找能力，适合大数据量的快速查找场景，但其性能和功能之间也存在一定的折衷。
2、 哈希桶实现的高级封装
2.1 模板参数与类型泛化
底层哈希桶的泛型编程改造：适配不同数据类型
unordered_map 和 unordered_set 都基于开散列（哈希桶）实现，其底层数据存储虽然相似，但存储的数据类型却有所不同。unordered_map 存储的是键值对 pair<k, v>，而 unordered_set 只存储键值 key。为了让哈希桶能够适配不同的数据存储需求，我们通过泛型编程进行改造，利用模板参数来实现这种适配。
四个关键模板参数
为了实现数据存储的灵活性，我们需要引入四个模板参数，确保底层哈希桶能够根据不同的需求进行配置：
class K：表示键值类型key，这是最基本的模板参数，决定了哈希表的键类型。class T：表示存储的数据类型，可以是 pair<k, v>（用于 unordered_map）或者仅为 key（用于 unordered_set）。class KeyOfT：这是一个关键的模板参数，通过仿函数定义如何从存储的数据类型 T 中提取 key。这一环节是适配不同数据类型的核心，非常巧妙地利用了仿函数来进行转换，使得哈希桶能够灵活应对不同存储方式。class HashFunc：这是用来将 key 转换为哈希值（size_t 类型），进而映射到哈希桶的数组下标。它是哈希表的基础，通过该函数确定 key 的分布。 通过模板参数实现适配
通过这四个模板参数的组合，底层哈希桶就能够根据上层 unordered_map 或 unordered_set 的需求，灵活存储不同类型的数据。例如，在 unordered_map 中，T 为 pair<k, v>，而在 unordered_set 中，T 仅为 key。而 KeyOfT 则通过仿函数来确保能够从 T 中正确地提取出 key。
这种方式通过灵活的模板参数，使得底层哈希桶能够根据上层容器的不同需求进行调整，极大地提高了代码的复用性和适配性。
总结
通过引入四个模板参数（K、T、KeyOfT、HashFunc），我们实现了一个通用的哈希桶结构，能够根据需求灵活存储 key 或 key-value 对。这种设计将数据的存储与哈希桶的实现分离，使得容器能够高效且灵活地适配不同的应用场景。
template<class K>struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};template<>struct HashFunc<string>{size_t operator()(const string& s){// BKDRsize_t hash = 0;for (auto ch : s){hash += ch;hash *= 131;}return hash;}};template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>class HashTable{ //设置为友元关系否则 迭代器++无法访问 私有成员 _tables 友元声明和前置声明都需要加上模板参数template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct HTIterator;typedef HashNode<T> Node;public:typedef HTIterator<K,T, T&, T*, KeyOfT, Hash> Iterator;typedef HTIterator<K,T, const T&, const T*, KeyOfT, Hash> ConstIterator;Iterator Begin(){}Iterator End(){}ConstIterator Begin()const{}ConstIterator End()const{}inline unsigned long __stl_next_prime(unsigned long n){static const int __stl_num_primes = 28;static const unsigned long __stl_prime_list[__stl_num_primes] ={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, 3221225473, 4294967291};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list +__stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}public:HashTable():_tables(__stl_next_prime(0)),_n(0){}// 拷贝构造 赋值重载~HashTable(){}pair<Iterator,bool> Insert(const T& data){}Iterator Find(const K& key){}bool Erase(const K& key){}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 表中存储数据个数};我们的模版参数修改之后，我们的函数体也要进行改造，不能直接写死，要符合泛型编程：
函数基本都是修改了原本的cur->_kv.first 变为 kot(cur->_kv)，通过仿函数来获取key值，并且返回值设置为迭代器。这样无论我们传入的是pair<k , v> 或 key，都可以通过仿函数获取对应的key值！
下面给出插入函数的代码，其余函数的改造可以参考【C++】——精细化哈希表架构：理论与实践的综合分析-CSDN博客 中的开散列实现策略，核心加了仿函数获取key值！！
pair<Iterator,bool> Insert(const T& data){KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return { it,false };Hash hash;// 负载因子等于1时候 进行扩容if (_n==_tables.size()){vector<Node*> newtable(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插到新链表size_t hashi = hash(kot(cur->_data)) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return {Iterator(newnode,this),true};}2.2 迭代器的设计与实现
实现迭代器：访问与修改数据的强大武器
在实现容器的封装时，迭代器是不可或缺的一部分。迭代器不仅让我们能够使用基于范围的 for 循环，还可以方便地访问和修改容器中的数据。因此，设计一个高效的迭代器是必不可少的一环。
哈希表的迭代器设计
哈希表的迭代器与传统容器的迭代器略有不同，主要体现在遍历规则和内部机制。我们需要构建一个迭代器框架，来支持高效的元素访问和遍历。
核心要素
节点指针：迭代器的核心是节点指针，用于访问哈希表中的数据。每个节点表示哈希桶中的一个元素。
支持++运算符：迭代器必须支持 ++ 运算符，用于遍历哈希表中的元素。移动规则如下：
HashTable），以便获取下一个桶。 基本运算符：
!= 和 ==：用于比较两个迭代器是否指向相同元素或是否不同。* 和 ->：提供对元素的访问，用于解引用和成员访问。 构造函数设计
在迭代器的构造函数中，我们使用 const HT* _ht 类型的指针作为参数，以保证只能读取哈希表数据而不能修改。这也是出于对容器封装的安全考虑，避免上层传入 const HT*，从而影响迭代器的行为。
template<class K,class T, class Ref,class Ptr, class KeyOfT, class Hash>struct HTIterator{typedef HashNode<T> Node;typedef HashTable<K,T, KeyOfT, Hash>HT;typedef HTIterator <K,T, Ref, Ptr, KeyOfT, Hash> Self;Node* _node;const HT* _ht; //为什么变为const 下面的 const End() 传的this 是const类型 如果这里 _ht不是const那么权限放大不通过HTIterator(Node* node, const HT* ht):_node(node), _ht(ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}Self& operator++(){ //....}};解决迭代器的前置声明与 ++ 运算符问题
在设计哈希表的迭代器时，遇到了一些常见的问题。特别是当我们将迭代器放在哈希表类的外部时，会出现编译错误：编译器无法识别 HashTable 类型。这是因为 HashTable 类在迭代器定义之后才进行声明，因此编译器在迭代器类的定义时无法访问到 HashTable 类。
解决方法
我们有两种解决方案来避免这个问题：
前置声明：在迭代器之前为 HashTable 添加前置声明，这样编译器就能识别 HashTable 的存在。
// 前置声明 告诉编译器 HashTable 是类模板后面有定义template<class K,class T, class KeyOfT, class Hash>class HashTable;
将迭代器放入 HashTable 内部：我们也可以将迭代器类定义为 HashTable 的内部类，这样就不需要前置声明了。内部类直接访问外部类的成员，因此迭代器能够直接访问 HashTable 的数据和方法。
template <typename Key, typename Value>class HashTable {public: class Iterator { // 迭代器类定义 };};
第二种方法将迭代器类与哈希表类紧密结合，是一种常见的做法，能够避免前置声明的麻烦，同时也更符合对象的封装思想。但是为了兼容之前哈希架构，我们选择前置声明。
++ 运算符的实现：遍历哈希表
实现 ++ 运算符是哈希表迭代器中的关键部分。我们需要处理两个主要的情况：
++ 运算符的逻辑
当前桶未遍历完：直接移动到当前桶中的下一个元素，即通过 cur = cur->next 访问下一个节点。
当前桶已遍历完：如果 cur->next 为 nullptr，说明当前桶已遍历完，需要跳转到下一个桶的第一个元素。我们需要从哈希表中查找下一个有效的桶。
结束遍历：如果找到了下一个桶，继续遍历；如果没有找到，说明已经遍历完所有元素，迭代器指向容器末尾。
代码实现：++ 运算符
Self& operator++(){if (_node->_next){//当前哈希桶还有数据，那就走到当前桶下一个节点_node = _node->_next;}else{//当前哈希桶走完了，找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){_node = _ht->_tables[hashi];if (_node)break;else++hashi; //没有这个陷入死循环} // 走完了所以桶 end（）给的空来标识_nodeif (hashi == _ht->_tables.size()){_node = nullptr; }}return *this;}这样我们的迭代器就完成了，再在hashtable中实例化普通迭代器和const迭代器：
public:typedef HTIterator<K,T, T&, T*, KeyOfT, Hash> Iterator;typedef HTIterator<K,T, const T&, const T*, KeyOfT, Hash> ConstIterator;Iterator Begin(){if (_n == 0)return End(); //找到第一个不为空的桶for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return Iterator(cur, this);}}//遍历完了都为空直接返回return End();}Iterator End(){return Iterator(nullptr, this);}ConstIterator Begin()const{if (_n == 0)return End();for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return ConstIterator(cur, this);}}return End();}ConstIterator End()const{return ConstIterator(nullptr, this);}这样底层就实现好了，接下来我们开始在上层做动作！
3、 容器的上层抽象与封装
3.1 unordered_set 的高效封装
unordered_set 是一种基于哈希表（哈希桶）实现的容器，它只存储 key 值，并通过哈希值实现快速查找。为了确保哈希表操作的高效性和数据的一致性，我们在设计 unordered_set 时需要注意以下几个关键点：
底层设计
数据存储： unordered_set 只存储 key 值，而不是键值对，因此其存储的元素是不可修改的。为了保证哈希表的稳定性，key 值一旦插入就不可更改，这要求在底层存储时必须将 key 设置为 const 类型，确保数据的不可修改性。
获取 key 的仿函数： 在 unordered_set 中，虽然只存储 key 值，但我们需要从存储的元素中提取出 key 来进行哈希计算。为此，我们使用 仿函数（例如 SetKeyOfT）来从存储的元素中提取 key。对于 unordered_set，存储的元素本身就是 key，因此仿函数的功能就是直接返回该元素。
哈希函数： 为了在哈希表中定位元素的位置，unordered_set 需要提供一个哈希函数。这个哈希函数将 key 转换为哈希值，进而映射到哈希表的桶中。上层容器可以通过提供自定义的哈希函数来决定哈希计算的方式，以确保元素能够均匀分布在哈希桶中。
函数调用与封装： 在大多数情况下，unordered_set 中的常见操作（如插入、查找、删除等）会直接调用底层哈希表的相关函数。通过这种方式，unordered_set 能够有效地封装底层细节，提供高效的接口供外部使用。
迭代器设计
迭代器是容器访问和操作元素的重要工具。在 unordered_set 的设计中，迭代器需要具备以下几个重要特性：
明确迭代器类型： 在实例化迭代器时，我们需要使用 typename 关键字明确指出 iterator 是一个类型，而不是一个变量或其他类型。这是因为编译器可能会将迭代器识别为一个普通变量，从而导致编译错误。因此，使用 typename 可以确保编译器正确解析迭代器类型。
遍历逻辑： 由于 unordered_set 是基于哈希表实现的，元素的存储顺序是无序的。因此，迭代器需要能够遍历哈希表中的所有桶和桶内的元素。迭代器的 ++ 运算符需要根据桶的遍历规则进行处理：
基本迭代器操作： 迭代器需要支持标准的操作，如 !=（不等于）、==（等于）、*（解引用）等。通过这些操作，我们直接复用一下底层函数。
template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin()const{return _ht.Begin();}const_iterator end()const{return _ht.End();}pair<iterator,bool> insert(const K& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase();}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht; //typedef 的参数 一定跟定义的成员变量一致 不可缺省};测试一下！！
void test_set1(){xc::unordered_set<string> S;vector<string> arr = { "sort" , "hello" , "XXXCCC" , "Hi" };for (auto e : arr){S.insert(e);}xc::unordered_set<string>::iterator it = S.begin();cout << "-------while循环遍历--------" << endl;while (it != S.end()){//(*it)++;std::cout << *it << endl;++it;}cout << "-------基于范围的for循环--------" << endl;for (auto e : S){//e++;cout << e << endl;}cout << "-------查找\"hello\"--------" << endl;cout << *(S.find("hello")) << endl;}
3.2 unordered_map 的高效封装与扩展
unordered_map 是一种基于哈希表实现的容器，它存储的是 键值对 pair<key, value>，与 unordered_set 不同的是，unordered_map 需要同时管理 key 和 value，而且提供了通过 key 查找和修改对应 value 的能力。
底层设计
数据存储： unordered_map 储存的是 pair<key, value>，其中 key 是键，value 是值。由于 key 在哈希表中起到索引作用，因此必须保证 key 的不可修改性。这意味着 key 必须定义为 const key，确保其在插入后不会被改变，从而保持哈希值的稳定性。
为了实现这一点，unordered_map 的内部实现通常会使用 pair<const key, value> 来存储数据。
获取 key 的仿函数： unordered_map 需要能够从存储的 pair<key, value> 中提取出 key，以便进行哈希计算。我们使用 仿函数 MapKeyOfT 来从 pair 类型中提取 key。这与 unordered_set 类似，但不同的是，这里我们提取的是 pair 的第一个元素作为 key。
哈希函数： 与 unordered_set 相同，unordered_map 也需要提供哈希函数来计算 key 的哈希值。哈希函数将 key 转换为哈希值，用于在哈希表中定位对应的桶。通过为 unordered_map 提供自定义的哈希函数，用户可以控制哈希的分布，以实现更均匀的元素分配。
函数封装： unordered_map 的大部分操作（如插入、查找、删除等）会直接调用底层哈希表的相关函数。通过这种方式，容器的操作能够保持简洁且高效，同时屏蔽了哈希表的复杂实现细节。
迭代器设计
unordered_map 的迭代器设计与 unordered_set 类似，也需要具备以下特点：
明确迭代器类型： 与 unordered_set 一样，在实例化 unordered_map 的迭代器时，我们需要使用 typename 关键字显式地声明 iterator 是一个类型，而不是变量或其他类型。这是为了避免编译器的歧义，确保迭代器能够正常工作。
遍历逻辑： 由于 unordered_map 基于哈希表实现，元素的存储顺序是无序的。因此，迭代器需要支持哈希表的桶遍历。与 unordered_set 类似，unordered_map 迭代器在遍历时也需要处理桶内元素的顺序和不同桶之间的跳转。
基本迭代器操作： unordered_map 的迭代器需要支持常见的操作，如 !=（不等于）、==（等于）、*（解引用）等。这些操作可以复用使得能够方便地访问和修改容器中的 key-value 。
[ ] 操作符的实现
unordered_map 中的 [ ] 操作符是一个非常重要且常用的功能。其基本运算规则如下：
key 已经存在，[ ] 运算符会返回该 key 对应的 value。如果 key 不存在，则会进行插入，插入的 value 会设置为默认构造的初始值（如整数的默认值是 0，指针的默认值是 nullptr 等）。 为了实现这一功能，我们可以通过调用底层的 Insert 函数。Insert 函数会检查是否已经存在相同的 key，如果 key 已存在则不会插入重复数据，并返回对应的迭代器。通过 Insert 的方式，我们能够确保 unordered_map 中不会有重复的 key，同时当 key 不存在时能够自动进行插入操作。
template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin()const{return _ht.Begin();}const_iterator end()const{return _ht.End();}V& operator[](const K& key){pair<iterator, bool>ret = insert({ key,V() });//return ret.first.operator->()->second;return ret.first->second; //省略了一个 ->}pair<iterator,bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase();}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};测试一下：
void test_map2(){unordered_map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边，剩余";dict["insert"] = "插⼊";dict["string"];unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){ //不能修改first，可以修改second//it->first += 'x'; it->second += 'x';cout << it->first << ":" << it->second << endl;++it;} cout << endl;}
4、 面试题解析与实践经验
在处理大规模数据时，尤其是面对超过100GB的日志文件或其他海量数据集，如何高效地找到频繁出现的元素（如IP地址、整数等）成了一个关键问题。以下我们将探讨几种常用的技术手段，结合实际问题，提出更加优化的解决方案。
问题一：如何找到出现次数最多的IP地址？
对于一个超过100GB的日志文件，其中记录了大量的IP地址，最直观的做法是遍历一遍文件，使用哈希表统计每个IP出现的次数。这样做的问题在于，哈希表的内存消耗可能非常大，尤其是当日志文件体积庞大时，哈希表本身的开销可能导致无法处理整个数据集。为了应对这个挑战，可以考虑以下优化方案：
优化方法：
分治法： 将超大日志文件分割成多个小文件。每个小文件的大小基于内存限制来划分，然后针对每个小文件使用哈希表统计IP出现次数。这样，每次处理的数据量不会超过内存限制，能够有效减少内存开销。
哈希分区： 基于IP地址的哈希值将日志数据分布到多个小文件中。每个小文件独立处理，计算IP地址的频率，最后将各个小文件的统计结果合并。这种方法有效地将数据分散到不同节点，减少了单一节点的内存压力。
外部排序： 对于内存有限的情况，可以采用外部排序算法。首先提取所有IP地址，将其排序，然后对每个IP的出现次数进行计数。使用外部排序将日志文件分批加载到内存中处理，最后合并计数结果，找出出现次数最多的IP地址。
问题二：如何找到Top K的IP地址？
当问题进一步扩展为找到Top K的IP地址时，我们不仅需要统计每个IP的出现次数，还需要根据这些统计信息进行排序。考虑到数据集的庞大，直接将所有结果加载到内存中进行排序不切实际。以下是更加优化的做法：
优化方法：
提取与排序： 使用Linux命令行工具（如awk、grep）提取IP地址，首先对这些地址进行排序。接着使用uniq -c命令对IP地址进行去重计数。最后，通过再次排序并使用head -n K来获取出现次数最多的Top K个IP地址。
具体命令：
awk '{print $1}' log_file | sort | uniq -c | sort -nr | head -n K
外部排序与合并： 如果数据量非常庞大且内存不足，采用外部排序来处理：首先将日志数据分批次加载到内存中，进行排序和计数，然后逐步合并这些中间结果，最终找出Top K的IP地址。
问题三：如何处理100亿个整数，找出只出现一次的整数？
当我们需要处理超大规模的数据集，例如有100亿个整数，并且内存仅为1GB，寻找只出现一次的整数成为一个挑战。普通的计数方法不适用，因为它需要在内存中存储所有整数的计数信息，超出了内存承载能力。此时可以借助位图（Bitmap）等高效的数据结构进行处理。
位图方法：
初始化位图： 创建一个足够大的位图，用于标记每个整数的出现情况。位图是一个位数组，每个整数在位图中占用一个位置。若某整数第一次出现，将其对应的位设置为1；若该整数再次出现，则将对应的位设置为-1。最终，位图中标记为1的整数就是只出现一次的整数。
高效存储： 由于位图是以位为单位存储数据，相较于传统的哈希表，它的内存使用更加紧凑，非常适合于内存受限的情况下进行处理。
问题四：如何找到两个文件中100亿个整数的交集？
当面对两个文件中各有100亿个整数，且内存仅为1GB时，如何高效地找到它们的交集是一个典型的外部数据处理问题。我们可以采用以下两种优化方法：
方法一：分治法与哈希分桶
分治法： 将两个文件各自分割成多个小文件，大小根据内存限制来决定。然后使用哈希表对每个小文件中的整数进行计数，找出交集。
哈希分桶： 使用哈希函数将文件中的整数分布到多个桶中。对于每个桶，可以在内存中处理这部分数据，找出交集。最后将各个桶的结果合并，得到两个文件的交集。
方法二：外部排序
排序： 分别对两个文件进行外部排序。由于内存有限，数据可以逐步加载进内存进行排序，并将排序后的数据存储回磁盘。
合并： 通过外部归并排序的方式，逐步合并两个文件中的数据。通过一次遍历，找出两个文件中的交集。
问题五：如何处理出现次数不超过2次的整数？
当我们需要在一个超大文件中找出所有出现次数不超过2次的整数，并且内存限制为1GB时，可以采用以下方法：
方法一：分治法 + 哈希表
分治法： 将大文件分割成多个小文件，并根据内存限制逐步处理每个小文件。使用哈希表统计每个整数的出现次数。
过滤： 遍历每个哈希表，筛选出出现次数不超过2次的整数，并将其输出到结果文件中。
合并结果： 将各个小文件的结果合并，最终得到出现次数不超过2次的整数。
方法二：哈希分桶
哈希分桶： 使用哈希函数将文件中的整数分配到多个桶中。在每个桶中使用哈希表统计出现次数。
过滤与合并： 对每个桶内的结果进行过滤，找出出现次数不超过2次的整数，然后将各个桶的结果合并。