11.代码随想录-哈希表（上）

哈希表理论基础

        定义

��       哈希表（散列表hash table），存储键值对。

        这里建议大家去看一下map的底层实现，gomap的底层和redis中字典的实现方式是基本一致的。

        哈希碰撞

        两个key都映射到了一个哈希表上的同一个索引位置，就是hash碰撞。这里两种处理方式，gomap和redis都使用的拉链法，即哈希表上索引的节点是一个链表的头结点，所有key的哈希值映射到这个索引点的都成为这个链表上的节点。当然也可能出现某个链表上的节点过多导致效率降低的情况，这部分往下就的扩容相关的知识，面试go是需要掌握的。另外一种是线性探测法，需要tablesize大于datasize，把碰撞的元素放到下面，但是会产生聚集效果，比如1，2，3都有元素，下一个hash为1，2，3的都会放到4。然后为了解决这种现象导致的效率降低还有二次探测法等等。

有效的字母异位词

        题干：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

        测试地址：. - 力扣（LeetCode）        

        暴力循环可以解决，但是显然使用map非常简单。

func isAnagram(s string, t string) bool {record := [26]int{}for _, v := range s {record[v-'a']++}for _, r := range t {record[r-'a']--}return record == [26]int{}   }

        第二种方法就只遍历一次字符串就可以了

func isAnagram(s string, t string) bool {if len(s) != len(t) {return false}records := [26]int{}for i := 0; i  
两个数组的交集
 
        题干：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
 
        测试地址：. - 力扣（LeetCode）
 
func intersection(nums1 []int, nums2 []int) []int {numsmap1, numsmap2 := make(map[int]bool, 0), make(map[int]bool, 0)res := make([]int, 0)for _, v := range nums1 {numsmap1[v] = true}for _, v := range nums2 {if numsmap2[v] == false{numsmap2[v] = trueif numsmap2[v] == true && numsmap1[v] == true {res = append(res, v)}}}return res}
 
快乐数
 
        题干：编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。如果 n 是快乐数就返回 True ；不是，则返回 False 。
 
        测试地址：. - 力扣（LeetCode）
 
        也很简单的一题，用来熟悉对map的使用挺好的。
 
func isHappy(n int) bool {num := make(map[int]bool, 0)for n != 1 && num[n] != true {num[n] = truen = getsum(n)}return n == 1}func getsum(n int) (sum int) {for n != 0 {sum = (n%10)*(n%10) + sumn /= 10}return sum}
 
两数之和
 
        题干：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 
        测试地址：. - 力扣（LeetCode）
 
        最简单的题了，梦开始的地方。这里利用map直接查询的特点可以直接去寻找我们想要的值。
 
func twoSum(nums []int, target int) []int {m := make(map[int]int)    for i, v := range nums {        j, ok := m[target-v]        if ok {            return []int{j, i}        }        m[v] = i    }    return nil}