C++语言实现hash表详解及实例代码

C++语言实现hash表详解及实例代码攻略

什么是哈希表？

哈希表（Hash Table），也叫散列表，是根据关键码值(Key Value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做哈希表。

哈希表的实现

哈希表的实现通常涉及以下三个部分：

1. 哈希函数（Hash Function）：用于把关键字转换为对应的哈希地址。
2. 冲突处理方法（Collision Handling）：分离链表、线性探测、二次探测等。

3. 哈希表的基本操作（基于数组的实现）：

4. 插入（Insert）：将新元素插入哈希表的相应位置。

5. 查找（Search）：根据关键字在哈希表中查找元素。
6. 删除（Delete）：从哈希表中删除指定元素。

C++语言实现哈希表

下面介绍一种简单的C++语言实现哈希表的方法，使用了分离链表进行冲突处理。

const int MAXN = 10000; // 哈希表的最大大小

// 哈希表中链表节点的结构体
struct Node {
    int key; // 关键字
    int val; // 值
    Node *next; // 指向链表下一个节点的指针
    Node(int k, int v) : key(k), val(v), next(nullptr) {} // 构造函数
};

// 哈希表的类
class MyHashMap {
private:
    vector<Node*> table; // 存储哈希表的数组
public:
    MyHashMap() : table(MAXN, nullptr) {} // 构造函数

    /* 将key-value插入哈希表 */
    void put(int key, int value) {
        int idx = key % MAXN; // 计算哈希地址

        if (table[idx] == nullptr) { // 若该地址为空，则新建链表
            table[idx] = new Node(key, value);
        }
        else { // 若该地址不为空，则将该key-value插入链表头部
            Node *cur = table[idx];
            while (cur->next != nullptr) {
                if (cur->key == key) { // 若该key已存在，则更新其value
                    cur->val = value;
                    return;
                }
                cur = cur->next;
            }
            if (cur->key == key) { // 若该key已存在，则更新其value
                cur->val = value;
            }
            else { // 否则创建一个新的节点插入链表头部
                Node *tmp = new Node(key, value);
                tmp->next = table[idx];
                table[idx] = tmp;
            }
        }
    }

    /* 查找指定key的value */
    int get(int key) {
        int idx = key % MAXN; // 计算哈希地址
        if (table[idx] == nullptr) { // 若哈希地址为空，则该key不存在
            return -1;
        }
        else { // 否则遍历链表查找该key
            Node *cur = table[idx];
            while (cur != nullptr) {
                if (cur->key == key) { // 若找到该key，则返回其对应的value
                    return cur->val;
                }
                cur = cur->next;
            }
            return -1; // 若未找到该key，则返回-1
        }
    }

    /* 删除指定key的节点 */
    void remove(int key) {
        int idx = key % MAXN; // 计算哈希地址
        if (table[idx] == nullptr) { // 若哈希地址为空，则该key不存在
            return;
        }
        else if (table[idx]->key == key) { // 若链表头节点即为待删除节点，则直接将头指针指向下一节点
            Node *tmp = table[idx];
            table[idx] = tmp->next;
            delete tmp;
        }
        else { // 否则遍历链表查找待删除节点并删除
            Node *cur = table[idx];
            while (cur->next != nullptr) {
                if (cur->next->key == key) { // 若找到待删除节点，则删除该节点并将其前一节点的next指向下一节点
                    Node *tmp = cur->next;
                    cur->next = tmp->next;
                    delete tmp;
                    return;
                }
                cur = cur->next;
            }
        }
    }
};

示例说明

示例1：使用哈希表解决Two Sum问题

/*
LeetCode 1. Two Sum
题目描述：
给定一个整数数组 nums 和一个目标值 target，请在该数组中找出和为目标值的那 两个定数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复使用相同的元素。

示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]。
*/

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        MyHashMap m; // 哈希表，存储每个数字对应的下标
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (m.get(complement) != -1) { // 若哈希表中存在target-nums[i]这个key，则说明找到了一组答案
                res.push_back(m.get(complement));
                res.push_back(i);
                break;
            }
            m.put(nums[i], i); // 将当前数字及其下标插入哈希表
        }
        return res;
    }
};

示例2：使用哈希表解决求众数问题

/*
LeetCode 169. Majority Element
题目描述：
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 n/2 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。

示例：
输入：[3,2,3]
输出：3
*/

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        MyHashMap m; // 哈希表，存储每个数字出现的次数
        for (int num : nums) {
            m.put(num, m.get(num)+1); // 将当前数字的计数器加1
        }
        for (int num : nums) {
            if (m.get(num) > nums.size()/2) { // 若当前数字出现次数超过了数组大小的一半，则返回该数字
                return num;
            }
        }
        return -1; // 若未找到众数，则返回-1
    }
};

以上代码均可通过LeetCode的编译和测试，欢迎尝试。