Hash Table

发表于

哈希表定义：

哈希表，使用哈希函数组织数据，来支持快速插入和搜索的数据结构

哈希表类型：

*哈希集合 ： 集合数据结构的实现之一，用于存储非重复值

*哈希映射： 映射数据结构的实现之一，用于存储（key, value) 键值对

哈希表原理：

使用哈希函数将键映射到存储桶

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

*当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索

搜索：已知映射函数，我们就知道这个值应该被放在哪个桶中，然后去那个桶里面找我们这个值在不在

插入：使用映射函数解析键值，映射到相应的桶中

Hash Table 相关问题

Leetcode 49

Given an array of strings, group anagrams together.

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

将单词拆分排序后作为key，value为一个list，将排序前的单词插入list

在Python中如果访问字典中不存在的键，会引发KeyError异常。因此，可以采用collections.defaultdict来初始化字典。defaudict初始化函数接受一个类型作为参数，当访问不存在的key时，可以实例化一个值作为默认值，从而省去了使用dict时需要判断key是否存在的问题。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        ans = collections.defaultdict(list)
        for s in strs:
            ans[tuple(sorted(s))].append(s)#tuple 是将列表转换为列表
            return ans.values()

Leetcode 76

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        need = collections.Counter(t)#它是一个无序的容器类型，以字典的键值对形式存储，其中元素作为key，其计数作为value。
        missing = len(t)
        start, end = 0,0
        i=0#左指针
        for j,char in enumerate(s,1):#j是右指针
            if need[char]>0:
                missing -=1
            need[char] -=1
            if missing == 0:#找到了包含所有target的区间
                while i<j and need[s[i]]<0:#左指针右移,还包含所有元素，缩小区间长度
                    need[s[i]] += 1
                    i += 1
                need[s[i]] +=1 #左指针右移后不能包括所有元素
                missing +=1
                if end ==0 or j-i < end-start:#现在找到了i，j更短
                    start,end = i,j
                i+=1
                #都包含了之后右移左指针，一旦包含不全，就右移右指针
        return s[start:end]