哈希表和哈希函数及相关练习

哈希表的原理

哈希表（又称散列表）的原理为：借助 哈希函数，将键映射到存储桶地址。更确切地说，

首先开辟一定长度的，具有连续物理地址的桶数组；

当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；

当我们想要搜索一个键时，哈希表将使用哈希函数来找到对应的桶，并在该桶中进行搜索。

负载因子 又叫装填因子，是哈希表的一个重要参数，它反映了哈希表的装满程度。

冲突解决:线性试探法 链地址法 公共溢出区法 再哈希法

哈希函数的性质

1)input 无穷

2)output s 固定大小

3)insame outsame

4)输入输出会发生碰撞

5)具有离散性

哈希函数的特征

1)相同输入导致相同输出

2)不同输入均匀分布

设计一个哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。

bool contains(key) 返回哈希集合中是否存在这个值 key 。

void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

#define MAX_LEN 100000          // 初始化桶的数量

class MyHashSet {
private:
    vector<int> set[MAX_LEN];   // 使用数组实现哈希集合
    
    /** 返回对应的桶的索引 */
    int getIndex(int key) {
        return key % MAX_LEN;
    }
    
    /** 在特定的桶中搜索键，如果该键不存在则返回 -1 */
    int getPos(int key, int index) {
        // 每个桶中包含一个列表，遍历所有桶中的元素来寻找特定的键
        for (int i = 0; i < set[index].size(); ++i) {
            if (set[index][i] == key) {
                return i;
            }
        }
        return -1;
    }
public:
    
    MyHashSet() {
        
    }
    
    void add(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos < 0) {
            // 如果键不存在，则添加
            set[index].push_back(key);
        }
    }
    
    void remove(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos >= 0) {
            // 如果键存在，则删除
            set[index].erase(set[index].begin() + pos);
        }
    }
    
    bool contains(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        return pos >= 0;
    }
};

//哈希集合的操作
#include <unordered_set>               

int main() {
    // 1. 初始化哈希集
    unordered_set<int> hashset;   
    // 2. 新增键
    hashset.insert(3);
    hashset.insert(2);
    hashset.insert(1);
    // 3. 删除键
    hashset.erase(2);
    // 4. 查询键是否包含在哈希集合中
    if (hashset.count(2) <= 0) {
        cout << "键 2 不在哈希集合中" << endl;
    }
    // 5. 哈希集合的大小
    cout << "哈希集合的大小为: " << hashset.size() << endl; 
    // 6. 遍历哈希集合
    for (auto it = hashset.begin(); it != hashset.end(); ++it) {
        cout << (*it) << " ";
    }
    cout << "在哈希集合中" << endl;
    // 7. 清空哈希集合
    hashset.clear();
    // 8. 查看哈希集合是否为空
    if (hashset.empty()) {
        cout << "哈希集合为空！" << endl;
    }
}


/*
 * 使用哈希集合寻找重复元素的模板
 */
bool findDuplicates(vector<Type>& keys) {
    // 将 type 替换为 keys 的实际类型
    unordered_set<Type> hashset;
    for (Type key : keys) {
        if (hashset.count(key) > 0) {
            return true;
        }
        hashset.insert(key);
    }
    return false;
}

设计一个哈希映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

MyHashMap() 用空映射初始化对象

void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。

int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。

void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

#define MAX_LEN 100000            // 初始化桶的数量

class MyHashMap {
private:
    vector<pair<int, int>> map[MAX_LEN];       // 使用数组实现哈希集合
    
    /** 返回指定桶的索引 */
    int getIndex(int key) {
        return key % MAX_LEN;
    }
    
    /** 在桶中搜索键，如果不存在则返回 -1 */
    int getPos(int key, int index) {
        // 每个桶包含一个数组，遍历桶中的所有元素来查找指定的 key
        for (int i = 0; i < map[index].size(); ++i) {
            if (map[index][i].first == key) {
                return i;
            }
        }
        return -1;
    }
    
public:
    MyHashMap() {
        
    }
    
    /** value 始终为正 */
    void put(int key, int value) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos < 0) {
            map[index].push_back(make_pair(key, value));
        } else {
            map[index][pos].second = value;
        }
    }
    
    /** 如果存在映射关系，则返回 value，否则返回 -1 */
    int get(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos < 0) {
            return -1;
        } else {
            return map[index][pos].second;
        }
    }
    
    /** 如果存在 key 的映射，则删除该映射关系 */
    void remove(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos >= 0) {
            map[index].erase(map[index].begin() + pos);
        }
    }
};

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) 
    
    {
         unordered_set<int> set;
         for(int i=0;i<nums.size();i++)
    {
        if(set.find(nums[i])!=set.end())
        {
            return true;
            break;
        }
        else{
            set.insert(nums[i]);
        }
    }
       return false;
    }
};

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
     unordered_set<int> hash;
     for(int x:nums)
     {
         if(hash.find(x) == hash.end())
        hash.insert(x);
        else
        hash.erase(x);
     }
     return *hash.begin();
    }
};

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(),nums1.end());
    sort(nums2.begin(),nums2.end());
    vector<int>vec;//指针变量
    int flag=INT_MIN;
    for(int i=0,j=0;i<nums1.size()&&j<nums2.size();)
    {
        if(nums1[i]<nums2[j])
        i++;
        else if(nums1[i]>nums2[j])
        j++;
        else
        {
            if(nums1[i]!=flag)
        vec.push_back(nums1[i]);
        flag=nums1[i];
        i++;
        j++;
        }
    }
    return  vec;
    }
};