C++ 手写 HashMap 实现 |21xrx.com

C++ 手写 HashMap 实现

2023-07-03 18:48:34 深夜i -- --

C++ HashMap 手写实现

C++是一门高效的编程语言，近年来在一些大型项目中得到广泛应用。其中，HashMap是常用的数据结构之一，可以用于快速查找和插入数据。本文将介绍如何手写一个基于C++的HashMap实现。

首先，需要定义一个HashMap的结构体，包含键值对和哈希表的大小等信息：


struct HashMap {
  int size;
  vector<pair<int, int>>* buckets;
};

其中，buckets是一个指向vector的指针，其中每一个元素都是一个键值对。接着，可以定义一个哈希函数来将输入的键值转换为哈希表中的位置：


int hash(int key, int size)
  return key % size;

这个哈希函数非常简单，将输入的key对哈希表的大小取模即可。然后，就可以开始实现HashMap的插入和查询操作了。首先，是插入操作：


void put(HashMap* map, int key, int value) {
  int pos = hash(key, map->size);
  if (map->buckets[pos].empty()) {
    map->buckets[pos].push_back(make_pair(key, value));
  } else {
    for (auto& kv : map->buckets[pos]) {
      if (kv.first == key)
        kv.second = value;
        return;
      
    }
    map->buckets[pos].push_back(make_pair(key, value));
  }
}

这段代码首先计算出要插入的位置，然后判断该位置是否为空。如果为空，直接在该位置插入新的键值对。如果不为空，需要遍历该位置上的所有键值对，判断是否已经存在该键，如果存在，则更新对应的值，否则在该位置后面插入新的键值对。

然后，是查询操作：


int get(HashMap* map, int key) {
  int pos = hash(key, map->size);
  for (auto& kv : map->buckets[pos]) {
    if (kv.first == key)
      return kv.second;
    
  }
  return -1;
}

这段代码也非常简单，首先计算出要查询的位置，然后遍历该位置上的所有键值对，判断是否存在该键，如果存在，则返回对应的值，如果不存在，则返回-1。

最后，在主函数中，可以创建一个HashMap对象，并向其中插入若干个键值对，然后可以查询指定的键，并输出对应的值。完整的代码如下所示：


#include <iostream>
#include <vector>
using namespace std;
struct HashMap {
  int size;
  vector<pair<int, int>>* buckets;
};
int hash(int key, int size)
  return key % size;
void put(HashMap* map, int key, int value) {
  int pos = hash(key, map->size);
  if (map->buckets[pos].empty()) {
    map->buckets[pos].push_back(make_pair(key, value));
  } else {
    for (auto& kv : map->buckets[pos]) {
      if (kv.first == key)
        kv.second = value;
        return;
      
    }
    map->buckets[pos].push_back(make_pair(key, value));
  }
}
int get(HashMap* map, int key) {
  int pos = hash(key, map->size);
  for (auto& kv : map->buckets[pos]) {
    if (kv.first == key)
      return kv.second;
    
  }
  return -1;
}
int main() {
  HashMap* map = new HashMap;
  map->size = 10;
  map->buckets = new vector<pair<int, int>>[10];
  put(map, 1, 10);
  put(map, 2, 20);
  put(map, 3, 30);
  cout << get(map, 1) << endl;
  cout << get(map, 2) << endl;
  cout << get(map, 3) << endl;
  return 0;
}

通过手写HashMap的实现，不仅可以加深对C++语言的理解，还可以更好地掌握哈希表等数据结构的底层原理，为编程工作打下坚实的基础。

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

下一篇: 如何编写最简单的C++程序？

评论区

()

相似文章