1 unordered_map 和 unordered_set
unordered系列的库是以哈希桶为底层的容器,其是用来快速寻找指定数据。这里主要介绍unordered_map和unordered_set。
unordered_map
<key , value>
键值对的容器,可以通过Key
快速寻找到其对应的value
,注意Key和value的类型可以不一样。并且key不可更改,value可以更改![ ]
下标访问!unordered_set
[ ]
下标访问!他们都提供以下接口:
迭代器
函数 | 功能介绍 |
---|---|
begin | 返回unordered_map第一个元素的迭代器 |
end | 返回unordered_map最后一个元素下一个位置的迭代器 |
cbegin | 返回unordered_map第一个元素的const迭代器 |
cend | 返回unordered_map最后一个元素下一个位置的const迭代器 |
功能函数
函数 | 功能介绍 |
---|---|
iterator find(const K& key) | 返回key在哈希桶中的位置 |
size_t count(const K& key) | 返回哈希桶中关键码为key的键值对的个数 |
insert | 向容器中插入键值对 |
erase | 删除容器中的键值对 |
void clear() | 清空容器中有效元素个数 |
void swap(unordered_map&) | 交换两个容器中的元素 |
桶操作
函数 | 功能介绍 |
---|---|
size_t bucket_count()const | 返回哈希桶中桶的总个数 |
size_t bucket_size(size_t n)const | 返回n号桶中有效元素的总个数 |
size_t bucket(const K& key) | 返回元素key所在的桶号 |
接下来我们就来实现这些功能!
unordered_map 和 unordered_set的底层是开散列版本的哈希表(哈希桶),但是他们两个储存的数据却不一样:一个是键值对pair<k , v>
, 一个是键值key
。所以为了可以让哈希桶适配,就要进行泛型编程的改造,增加模版参数。由上层的unordered_map 和 unordered_set控制底层的哈希桶存储什么数据,因此我们需要添加一个class T
模版参数,供上层决定储存什么数据。与之对应的,从数据中获取key
的仿函数。
这样加上将转换key为size_t的仿函数,共用四个模版参数:
class k
: 表明键值key的类型,这是最基本的。class T
: 储存的数据类型:pair<k , v>
或 key
。class KeyOfT
: 如何从T
中获取key
,这是很关键的,是我感觉最巧妙的一环,通过仿函数来适配不同类型,太妙了!class HashFunc
:将key值转换为size_t的数组下标。通过这四个模版参数,就可以通过传入对应的参数来保证适配!(迭代器我们后续来实现)
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
public:
typedef HashNode<T> Node;
iterator begin()
{}
iterator end()
{}
const_iterator begin() const
{}
const_iterator end() const
{}
HashTable()
:hs(),
kot()
{
_table.resize(10, nullptr);
_n = 0;
}
//插入数据
pair<iterator, bool> insert(const T kv)
{}
//删除
bool erase(const K& key)
{}
//查找
iterator find(const K& key)
{}
private:
//底层是一个指针数组
vector<Node*> _table;
//有效数量
size_t _n;
//仿函数
Hash hs;
KeyOfT kot;
};
我们的模版参数修改之后,我们的函数体也要进行改造,不能直接写死,要符合泛型编程:
函数基本都是修改了原本的cur->_kv。first 变为 kot(cur->_kv),通过仿函数来获取key值,并且返回值设置为迭代器。这样无论我们传入的是pair<k , v>
或 key
,都可以通过仿函数获取对应的key值!下面给出插入函数的代码,其余函数的改造类似!
插入函数
//插入数据
pair<iterator, bool> insert(const T kv)
{
iterator it = find(kot(kv));
if (it != end())
return make_pair(it, false);
//扩容
if (_n == _table.size() * 0.7)
{
//直接把原本的节点移动到新的table中即可
vector<Node*> newtable(2 * _table.size());
//遍历整个数组
for (int i = 0; i < _table.size(); i++)
{
if (_table[i])
{
Node* cur = _table[i];
while (cur)
{
//获取数据
Node* next = cur->_next;
//计算新的映射
//kot(cur->_kv) 来获取 T 中的key
size_t hashi = hs(kot(cur->_kv)) % newtable.size();
//进行头插
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
}
}
_table.swap(newtable);
}
//首先寻找到合适下标
size_t hashi = hs(kot(kv)) % _table.size();
//进行头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode , this), true);
}
实现封装一定少不了迭代器!!!迭代器可是强大的武器,有了迭代器就可以使用基于范围的for循环,还可以通过迭代器来访问修改数据。
那么我们就要来写一个迭代器,来供我们使用。
哈希表的迭代器和之前写过的迭代器有所不同,我们来看奥:我们搭建一个基本框架:
++
运算,可以移动到下一个节点。移动规则:当前桶没走完就移动到下一个元素, 当前桶走完了就移动到下一个桶的第一个元素,而移动到下一个桶需要哈希表表,所以内部需要有一个哈希表!= == * ->
运算。const HashTable* ht
低权限,因为我们不会对其修改,还要避免上层传入``const HashTable* `,所以要做好预防!template<class Ref , class Ptr>
struct _HTIterator
{
typedef _HTIterator<Ref, Ptr> Self;
//成员
Node* _node;
//哈希表
const HashTable* _pht;
//构造函数
_HTIterator(Node* node, const HashTable* ht)
:_node(node),
_pht(ht)
{}
//++
Self& operator++()
{
}
//判断很好写
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
Ref operator*() const
{
return _node->_kv;
}
Ptr operator->() const
{
return &_node->_kv;
}
};
如果我们将迭代器正常放在哈希表的外面,会发现报错:编译器不认识 HashTable
,很正常,因为HashTable
在其后面才进行定义,所以我们可以在迭代器之前加一个HashTable
前置声明!或者使用内部类,把迭代器放HashTable内部就好了!
然后我们就来解决这个++
的问题:
cur = cur ->next
即可!//++
Self& operator++()
{
Hash hs;
KeyOfT kot;
//++
//当前桶没走完就移动到下一个 桶走完了就移动到下一个桶
if (_node->_next) _node = _node->_next;
else
{
//桶走完了就移动到下一个桶
size_t i = hs(kot(_node->_kv)) % _pht->_table.size();
i++;
for (; i < _pht->_table.size(); i++)
{
if (_pht->_table[i])
break;
}
//走完循环有两种可能,要进行判断
if (i == _pht->_table.size())
_node = nullptr;
else
{
_node = _pht->_table[i];
}
}
return *this;
}
这样我们的迭代器就完成了,再在hashtable中实例化普通迭代器和const迭代器:
//迭代器
typedef _HTIterator<T&, T*> iterator;
//const 迭代器
typedef _HTIterator<const T&, const T*> const_iterator;
然后加入我们begin()和end()函数
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
return iterator(_table[i], this);
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin() const
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
return const_iterator(_table[i], this);
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
这样底层就实现好了,接下来我们开始在上层做动作!
底层的哈希桶我们已经改造完毕了,接下来就是在上层来调用:
先来看unordered_set,其底层要注意:
Hashtable
中的函数就可以!这样我们可以搭建起一个框架
//仿函数
template<class K>
struct SetKeyOfT
{
const K operator()(const K& k)
{
return k;
}
};
template<class K ,class Hash = HashFunc<K>>
class my_unoerder_set
{
public:
//迭代器
typedef typename HashTable<K, const K, SetKeyOfT<K>, Hash >::iterator iterator;
typedef typename HashTable<K, const K, SetKeyOfT<K>, Hash >::const_iterator const_iterator;
pair<iterator , bool> insert(const K& k)
{
return _table.insert(k);
}
iterator find(const K& k)
{
return _table.find(k);
}
bool erase(const K& k)
{
return _table.erase(k);
}
iterator begin()
{
return _table.begin();
}
iterator end()
{
return _table.end();
}
const_iterator begin() const
{
return _table.begin();
}
const_iterator end() const
{
return _table.end();
}
private:
HashTable<K,const K, SetKeyOfT<K> , Hash > _table;
};
这样就设置好了,我们来测试一下:
void test_set1()
{
my_unoerder_set<string> S;
vector<string> arr = { "sort" , "hello" , "JLX" , "Hi" };
for (auto e : arr)
{
S.insert(e);
}
my_unoerder_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;
}
测试结果:
完美,这样unordered_set就完成了,当然还可以继续完善功能函数,其他的函数比较简单就不加赘述。
继续来看unordered_map:
pair<k , v>
,而且注意k值不能修改所以要传入pair<const k , v>
!Hashtable
中的函数就可以![ ]
操作:非常简单,[ ]
的运算规则是:如果对应key已经存在,就返回其value值。不存在就进行插入,value设置为初始值,所以直接调用Insert函数就可以,因为Insert函数不会插入重复的数据并且会返回对应的迭代器!//仿函数
template<class K , class V>
struct MapKeyOfT
{
const K& operator()(const pair<K , V>& kv)
{
return kv.first;
}
};
template<class K , class V, class Hash = HashFunc<K>>
class my_unoerder_map
{
public:
//迭代器
typedef typename HashTable< K, pair<const K, V>, MapKeyOfT<K, V> , Hash>::iterator iterator;
typedef typename HashTable< K, pair<const K, V>, MapKeyOfT<K, V> , Hash>::const_iterator const_iterator;
pair<iterator, bool> insert(pair<const K, V> kv)
{
return _table.insert(kv);
}
iterator find(const K& k)
{
return _table.find(k);
}
bool erase(const K& k)
{
return _table.erase(k);
}
iterator begin()
{
return _table.begin();
}
iterator end()
{
return _table.end();
}
//[]操作
V& operator[](const K& k)
{
pair<iterator, bool> it = insert(make_pair( k , V() ));
return it.first->second;
}
private:
HashTable<K, pair<const K , V>, MapKeyOfT<K , V> , Hash> _table;
};
我们来进行一下测试奥:
void test_unordered_map()
{
my_unoerder_map<string, int> countMap;
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
for (auto& e : arr)
{
countMap[e]++;
}
my_unoerder_map<string, int>::iterator it = countMap.begin();
while (it != countMap.end())
{
//(*it).first += 2;
cout << (*it).first << ':' << (*it).second << endl;
++it;
}
}
运行结果:
完美!!!
哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址? 错误回答:通过哈希表,遍历一遍该文件,获取到每个IP地址出现的次数,再遍历一遍哈希表,得到出现次数的IP地址。 … 这样的回答是对哈希理解的不够深导致的,我们看题目条件:超过100G大小的log file!哈希中负载因子一般为0.5 ~ 0.7,所以会有很多空间是浪费的,文件本身已经100G了,可想而知这个哈希表会有多大了! 我们可以使用
正确回答(分治 + 哈希):
与上题条件相同,如何找到top K的IP?如何直接用Linux系统命令实现?
正确答案:
awk '{print $1}' log_file | sort | uniq -c | sort -nr | head -n K
位图应用
给定100亿个整数,设计算法找到只出现一次的整数?
正确回答:可以使用位图(Bitmap)数据结构来有效地解决问题。位图是一种数据结构,用于存储与处理布尔值,其中每个值只占用一个位(bit)的空间。位图中是一个整型数组,每个整型可以储存32个比特位
1
。如果整数再次出现,则将其在位图中对应的位设置为-1
,在出现就不进行处理。这样,最终位图中为1的位对应的整数就是只出现一次的整数。1
的位,这些位对应的整数就是只出现一次的整数。给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
正确回答:
位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数
正确回答: