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

　　哈希表的原理
　　哈希表（又称散列表）的原理为：借助 哈希函数，将键映射到存储桶地址。更确切地说，
　　首先开辟一定长度的，具有连续物理地址的桶数组；
　　当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
　　当我们想要搜索一个键时，哈希表将使用哈希函数来找到对应的桶，并在该桶中进行搜索。
　　负载因子  又叫装填因子，是哈希表的一个重要参数，它反映了哈希表的装满程度。
　　冲突解决 :线性试探法 链地址法 公共溢出区法 再哈希法
　　哈希函数的性质
　　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 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                  int main() {     // 1. 初始化哈希集     unordered_set 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& keys) {     // 将 type 替换为 keys 的实际类型     unordered_set 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> 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& nums)           {          unordered_set set;          for(int i=0;i& nums) {      unordered_set 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 intersection(vector& nums1, vector& nums2) {     sort(nums1.begin(),nums1.end());     sort(nums2.begin(),nums2.end());     vectorvec;//指针变量     int flag=INT_MIN;     for(int i=0,j=0;inums2[j])         j++;         else         {             if(nums1[i]!=flag)         vec.push_back(nums1[i]);         flag=nums1[i];         i++;         j++;         }     }     return  vec;     } };