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

　　哈希表的原理
　　哈希表（又称散列表）的原理为：借助哈希函数，将键映射到存储桶地址。更确切地说，
　　首先开辟一定长度的，具有连续物理地址的桶数组；
　　当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
　　当我们想要搜索一个键时，哈希表将使用哈希函数来找到对应的桶，并在该桶中进行搜索。
　　负载因子又叫装填因子，是哈希表的一个重要参数，它反映了哈希表的装满程度。
　　冲突解决：线性试探法链地址法公共溢出区法再哈希法
　　哈希函数的性质
　　1）input无穷
　　2）outputs固定大小
　　3）insameoutsame
　　4）输入输出会发生碰撞
　　5）具有离散性
　　哈希函数的特征
　　1）相同输入导致相同输出
　　2）不同输入均匀分布
　　设计一个哈希集合
　　不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
　　实现MyHashSet类：
　　voidadd（key）向哈希集合中插入值key。
　　boolcontains（key）返回哈希集合中是否存在这个值key。
　　voidremove（key）将给定值key从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。defineMAXLEN100000初始化桶的数量classMyHashSet｛private：vectorintset〔MAXLEN〕；使用数组实现哈希集合返回对应的桶的索引intgetIndex（intkey）｛returnkeyMAXLEN；｝在特定的桶中搜索键，如果该键不存在则返回1intgetPos（intkey，intindex）｛每个桶中包含一个列表，遍历所有桶中的元素来寻找特定的键for（inti0；iset〔index〕。size（）；i）｛if（set〔index〕〔i〕key）｛returni；｝｝return1；｝public：MyHashSet（）｛｝voidadd（intkey）｛intindexgetIndex（key）；intposgetPos（key，index）；if（pos0）｛如果键不存在，则添加set〔index〕。pushback（key）；｝｝voidremove（intkey）｛intindexgetIndex（key）；intposgetPos（key，index）；if（pos0）｛如果键存在，则删除set〔index〕。erase（set〔index〕。begin（）pos）；｝｝boolcontains（intkey）｛intindexgetIndex（key）；intposgetPos（key，index）；returnpos0；｝｝；哈希集合的操作includeunorderedsetintmain（）｛1。初始化哈希集unorderedsetinthashset；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（autoithashset。begin（）；it！hashset。end（）；it）｛cout（it）；｝cout在哈希集合中endl；7。清空哈希集合hashset。clear（）；8。查看哈希集合是否为空if（hashset。empty（））｛cout哈希集合为空！endl；｝｝使用哈希集合寻找重复元素的模板boolfindDuplicates（vectorTypekeys）｛将type替换为keys的实际类型unorderedsetTypehashset；for（Typekey：keys）｛if（hashset。count（key）0）｛returntrue；｝hashset。insert（key）；｝returnfalse；｝
　　设计一个哈希映射
　　不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
　　实现MyHashMap类：
　　MyHashMap（）用空映射初始化对象
　　voidput（intkey，intvalue）向HashMap插入一个键值对（key，value）。如果key已经存在于映射中，则更新其对应的值value。
　　intget（intkey）返回特定的key所映射的value；如果映射中不包含key的映射，返回1。
　　voidremove（key）如果映射中存在key的映射，则移除key和它所对应的value。defineMAXLEN100000初始化桶的数量classMyHashMap｛private：vectorpairint，intmap〔MAXLEN〕；使用数组实现哈希集合返回指定桶的索引intgetIndex（intkey）｛returnkeyMAXLEN；｝在桶中搜索键，如果不存在则返回1intgetPos（intkey，intindex）｛每个桶包含一个数组，遍历桶中的所有元素来查找指定的keyfor（inti0；imap〔index〕。size（）；i）｛if（map〔index〕〔i〕。firstkey）｛returni；｝｝return1；｝public：MyHashMap（）｛｝value始终为正voidput（intkey，intvalue）｛intindexgetIndex（key）；intposgetPos（key，index）；if（pos0）｛map〔index〕。pushback（makepair（key，value））；｝else｛map〔index〕〔pos〕。secondvalue；｝｝如果存在映射关系，则返回value，否则返回1intget（intkey）｛intindexgetIndex（key）；intposgetPos（key，index）；if（pos0）｛return1；｝else｛returnmap〔index〕〔pos〕。second；｝｝如果存在key的映射，则删除该映射关系voidremove（intkey）｛intindexgetIndex（key）；intposgetPos（key，index）；if（pos0）｛map〔index〕。erase（map〔index〕。begin（）pos）；｝｝｝；
　　给你一个整数数组nums。如果任一值在数组中出现至少两次，返回true；如果数组中每个元素互不相同，返回false。classSolution｛public：boolcontainsDuplicate（vectorintnums）｛unorderedsetintset；for（inti0；inums。size（）；i）｛if（set。find（nums〔i〕）！set。end（））｛returntrue；break；｝else｛set。insert（nums〔i〕）；｝｝returnfalse；｝｝；
　　给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。classSolution｛public：intsingleNumber（vectorintnums）｛unorderedsetinthash；for（intx：nums）｛if（hash。find（x）hash。end（））hash。insert（x）；elsehash。erase（x）；｝returnhash。begin（）；｝｝；
　　给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。classSolution｛public：vectorintintersection（vectorintnums1，vectorintnums2）｛sort（nums1。begin（），nums1。end（））；sort（nums2。begin（），nums2。end（））；vectorintvec；指针变量intflagINTMIN；for（inti0，j0；inums1。size（）jnums2。size（）；）｛if（nums1〔i〕nums2〔j〕）i；elseif（nums1〔i〕nums2〔j〕）j；else｛if（nums1〔i〕！flag）vec。pushback（nums1〔i〕）；flagnums1〔i〕；i；j；｝｝returnvec；｝｝；