unordered_map、unordered_set 底层原理及其相关面试题?

Nen 2022-01-07 14:56

- 程序员

（1）unordered_map、unordered_set的底层原理

unordered_map的底层是一个防冗余的哈希表（采用除留余数法）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，时间复杂

度为O(1)；而代价仅仅是消耗比较多的内存。

使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数（一般使用除留取余法），也叫做散列函数），使得每个元素的key都

与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照key为每一个元素“分类”，然后

将这个元素存储在相应“类”所对应的地方，称为桶。

但是，不能够保证每个元素的key与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，

换句话说，就是把不同的元素分在了相同的“类”之中。一般可采用拉链法解决冲突：

（2）哈希表的实现

“`c++

#include

#include #include

#include

using namespace std;

const int hashsize = 12;

//定一个节点的结构体

template

struct HashNode

{

T _key;

U _value;

};

//使用拉链法实现哈希表类

template

class HashTable

{

~HashTable() {}

bool insert_data(const T &key, const U &value);

int hash(const T &key);

bool hash_find(const T &key);

private:

vector<list<HashNode<T, U>>> vec;//将节点存储到容器中

};

//哈希函数（除留取余）

template

int HashTable<T, U>::hash(const T &key)

{

return key % 13;

}

//哈希查找

template

bool HashTable<T, U>::hash_find(const T &key)

{

int index = hash(key);//计算哈希值

for (auto it = vec[index].begin(); it != vec[index].end(); ++it)

{

if (key it -> _key)//如果找到则打印其关联值

{

cout << it->_value << endl;//输出数据前应该确认是否包含相应类型

return true;

}

return false;

}

//插入数据

template

bool HashTable<T, U>::insert_data(const T &key, const U &value)

{

//初始化数据

HashNode<T, U> node;

node._key = key;

node._value = value;

for (int i = 0; i < hashsize; ++i)

{

if (i hash(key))//如果溢出则把相应的键值添加进链表

{

vec[i].push_back(node);

return true;

}

int main(int argc, char const *argv[])

{

HashTable<int, int> ht;

static default_random_engine e;

static uniform_int_distribution u(0, 100);

long long int a = 10000000;

for (long long int i = 0; i < a; ++i)

ht.hash_find(114);

clock_t end_time = clock();

cout << “Running time is: ” << static_cast(end_time – start_time) / CLOCKS_PER_SEC * 1000 <<

“ms” << endl;//输出运行时间。

system(“pause”);

return 0;

}

unordered_map、unordered_set 底层原理及其相关面试题?

轩辕小不懂的其他提问

类似问题

unordered_map、unordered_set 底层原理及其相关面试题?

轩辕小不懂 的其他提问

类似问题

轩辕小不懂的其他提问