C++ 如何定义哈希表 |21xrx.com

C++ 如何定义哈希表

2023-06-28 02:47:07 深夜i -- --

C++ 哈希表定义

哈希表是一种数据结构，它通过哈希函数和数组来存储和操作键值对。在C++中，哈希表可以使用STL（标准模板库）库中的unordered_map类来实现，也可以手动实现。

使用STL库的unordered_map类

unordered_map类属于STL标准模板库中的关联容器，可以用来存储任意类型的键值对。它采用哈希表来实现，可以快速地进行查找、插入和删除操作。

unordered_map的定义格式如下：


std::unordered_map<键类型, 值类型> my_map;

其中键类型和值类型分别为要存储的键和值的类型。

手动实现哈希表

如果不想使用STL库中的unordered_map类，也可以手动实现哈希表。手动实现哈希表的步骤如下：

1. 定义哈希函数

哈希函数是用来计算键的哈希值的函数。它将键转换为哈希值，以便将键映射到哈希表的合适位置。哈希函数应该是高效、均匀且无序的。常用的哈希函数包括除留余数法、平方取中法、FNV1a等。

以下是一个简单的哈希函数示例：


size_t hash_function(const std::string& key)
{
  size_t hash_value = 0;
  for (const char& c : key) {
    hash_value = hash_value * 31 + static_cast<size_t>(c);
  }
  return hash_value;
}

2. 定义哈希表结构体

哈希表结构体是用来存储键值对的数据结构。它应该包含一个数组和一个哈希函数成员变量。

以下是一个哈希表结构体示例：


template<typename KeyType, typename ValueType>
struct HashTable
{
  std::vector<std::pair<KeyType, ValueType>> data_;
  std::function<size_t(const KeyType&)> hash_function_;
};

其中data_是用来存储键值对的vector数组，hash_function_是用来计算键的哈希值的函数指针。

3. 定义插入、查找和删除操作

哈希表的插入、查找和删除操作都是通过哈希函数来实现的。插入操作将键值对插入到哈希表中的合适位置，查找操作通过哈希值查找键值对，删除操作将指定的键值对从哈希表中删除。

以下是一个哈希表的插入、查找和删除操作示例：


template<typename KeyType, typename ValueType>
void insert(HashTable<KeyType, ValueType>& hash_table, const KeyType& key, const ValueType& value)
{
  auto hash_value = hash_table.hash_function_(key);
  hash_table.data_[hash_value].emplace_back(key, value);
}
template<typename KeyType, typename ValueType>
std::pair<bool, ValueType> find(const HashTable<KeyType, ValueType>& hash_table, const KeyType& key)
{
  auto hash_value = hash_table.hash_function_(key);
  for (const auto& i : hash_table.data_[hash_value]) {
    if (i.first == key) {
      return std::make_pair(true, i.second);
    }
  }
  return std::make_pair(false, ValueType());
}
template<typename KeyType, typename ValueType>
bool remove(HashTable<KeyType, ValueType>& hash_table, const KeyType& key)
{
  auto hash_value = hash_table.hash_function_(key);
  for (auto it = hash_table.data_[hash_value].begin(); it != hash_table.data_[hash_value].end(); ++it) {
    if (it->first == key) {
      hash_table.data_[hash_value].erase(it);
      return true;
    }
  }
  return false;
}

通过以上三个步骤，可以手动实现一个简单的哈希表。当然，若要实现更高效、更稳定的哈希表，还需要考虑哈希表大小、哈希函数的优化等因素。

上一篇: idea打包java可执行jar包

下一篇: Python和Node.js的比较

评论区

()

相似文章