HashTable

Dictionary, Set, 例题

底层机制

set是简化版hashtable，而hashtable的本质其实是array（或者说Python里的list），因为list的本质就是array index和value的映射。所以关键问题是把key转换成index。一般分成3步：

1. 通过key和hash function计算它的hash_number=hash(key) 这一步虽然可能有collision但是可能性比较低

2. index=hash_number%N, N是array size。 这一步有很大概率有collision，取决于N的大小

3. 如果有hash collision，两种方法来解决（正文）； 如果没有，list[index]=value

Dictionary 使用场景

TF-IDF (Term Frequency- Inverse Document Frequency) 统计词频时，可以用list来统计频率，但是使用list的缺点是每次更新频率的时间复杂度都是O(n), 只能遍历一遍、找到词、给词频+1； 随着单词变多，这个过程就变得低效了。

在Python中，可以使用dictionary的结构来实现高效的“更新词频“的需求。

def words_to_frequencies (words):
    myDict={}
    for word in words:
        if word in myDict:
            myDict[word]+=1
        else:
            myDict[word]=1
    return myDict

Time Complexity: O(n)

Space Complexity: O(1) 如果我们不算return值的话，那没有额外空间的消耗

Example: 查找高频

如果要找到频率最高的word，分两步1. 遍历，找到最大的值； 2. 找到list，返回

def most_common_words (freqs):
    best = max(freqs.values())
    words = [
        key                                        #代表元 expression    
        for key, val in freqs.items()              #for循环
        if val==best                               #判断条件
        ]
    return (words, best)   

List comprehension的写法：[expression for elem in collection if condition]

相类似的字典也有dictionary comprehension，只需要把[] 换成{}

{key_expression: value_expression for value in collection if condition}

Example：合并大小写的频次

mydic = {'a': 10, 'b': 6, 'A': , 'B': }

new_mydic={
    k.lower(): mydict.get(k.lower(), 0) + mydic.get(k.upper(),0)
    for k in mydic.keys()
}

#output: {'a': 17, 'b': 34, 'z': 3}

get():

Python 字典(Dictionary) get() 函数返回指定key的value，如果值不在字典中返回默认值。

语法

dict.get(key, default=None)

参数

• key -- 字典中要查找的键。

• default -- 如果指定键的值不存在时，返回该默认值。

返回值

返回指定键的值，如果值不在字典中返回默认值None。

实例

dict = {'Name': 'Zara', 'Age': 27}

print "Value : %s" %  dict.get('Age')
print "Value : %s" %  dict.get('Sex', "Never")

以上实例输出结果为：

Value : 27
Value : Never

Example: Top K freq words

第一步：先把词频算出来

第二步：sorting，按照单词的频率排序，而且是频率加负号，按负的频率排序，频率越大顺序越小。 或者也可以用key = lambda kv: kv[1], reverse=True

sorted的syntax: sorted(iterable, key=key, reverse=reverse)

再次注意，dictionary没有顺序！所以不能直接输出前x个。

class Solution(object):
  def topKFrequent(self, combo, k):
    """
    input: string[] combo, int k
    return: string[]
    """
    # write your solution here

    mydict={}
    for char in combo:
      if char in mydict:
        mydict[char]+=1
      else:
        mydict[char]=1

    sorted_tuple=sorted(mydict.items(), key= lambda kv: -kv[1] )

    return [x[0] for x in sorted_tuple][:k]

前面部分是O(n), sort部分都是O(nlogn), 最后一步还是O(n), 最终就是O(nlogn)

这里输出的是dict_keys

如果使用collections这个package，然后把items转成list 可以通过。

class Solution(object):
  def topKFrequent(self, combo, k):
    """
    input: string[] combo, int k
    return: string[]
    """
    # write your solution here
    import collections
    import heapq
    counts = collections.Counter(combo)
    items = list(counts.items())
    items.sort(key=lambda item:(-item[1],item[0]))
    return [item[0] for item in items[0:k]]

另外还可以用heap做这道题，也就是把整理好的dict一个个push到max heap或者min heap里。因为Python内置函数的heap是一个min heap，如果想用它做max heap，在每个元素push进去的时候对value取负号。然后在有元素可pop并且pop出来的元素数量<=k的前提下一个个pop元素, append到result上，然后反过来输出。

Max Heap

class Solution(object):
  def topKFrequent(self, combo, k):
    """
    input: string[] combo, int k
    return: string[]
    """
    # write your solution here
    # max heap
    mydict={}
    for char in combo:
      if char in mydict:
        mydict[char]+=1
      else:
        mydict[char]=1
      
    import heapq  
    freq=[]
    for char in mydict.keys():
      heapq.heappush(freq, (-mydict[char], char))
    
    topk, i =[],0
    while i < k and len(freq)>=1:
        topk.append(heapq.heappop(freq)[1])
        i+=1
    return topk

Min Heap

Example: Palindromic Testing

给一个单词，测试它能否被写成回文数的形式。能满足回文的条件，那就必须满足除了中间的数可能一个外，其余的都是偶数个；换句话说，奇数的字母只有1个，其余都是偶数个。所以我们需要建立字母到频率的字典，计算频率的个数。

def is_palindromic(word):
    freq = {}
    for i in range(len(word)):
        if word[i] in freq:
            freq[word[i]]+=1
        else:
            freq[word[i]]=1
    odd_cnt = 0
    for key in freq.key():
        if freq[key]%2==1:
            odd_cnt += 1
            if odd_cnt > 1:
                return False
    return True 

Time Complexity: O(n)

Space Complexity: O(C) C是distinct chars in string

Example: Subarray Sum to Target II

Given an array nums and a target value k, find the total number of subarrays that sums to k.

Nums = [1,6,5,2,3,4,0] k=7, return 4 prefixS = [0,1,7,12,14,17,21,21] prefixS[j]-prefixS[i]==target <--->prefixS[j]-target==prefixS[i]

O(n) time, O(C) space, c is the number of distinct values

class Solution(object):
  def numOfSubarraySumToK(self, nums, k):
    """
    input: int[] nums, int k
    return: int
    """
    # write your solution here
    sums, count = 0,0
    mydict={}
    for num in nums:
      if sums not in mydict:
        mydict[sums]=0
      mydict[sums]+=1 #注意这句和下句的先后顺序
      sums+=num
      if sums-k in mydict:
        count+=mydict[sums-k]
    return count

Example: Nearest repeated entries in an array

重复的单词最近的距离 key是单词，value是位置，距离只需要减一下、更新为距离。

def nearest_repeat (arr):
    word_ind = {}
    dist = float('inf')
    for i in range(len(arr)):
        if arr[i] in word_ind:
            dist = min(dist, i -word_ind[arr[i]])
        word_ind[arr[i]] = i
    return dist

Time Complexity: O(n)

Space Complexity: O(C) C是distinct entries in arr

Example: 2 sum unsorted, no dup

return index, O(n) time and O(n) space

def 2sum(nums, target):
    if len(nums)<=1:
        return False
    dict={}
    for i in range (nums):
        if nums[i] in dict:
            return (dict[num[i]], i)
        else:
            dict[target-nums[i]]=i
    return False

Example: Nearest repeated entries in an array

Example: Longest Contained Range

brute-force: sort, O(nlogn), search, O(n)

set: “中心开花，左右出发“，以任何一个元素出发，往两边扩展

1. 先放进集合里

2. pop 任取元素，左右扩展

def longest_contained_range(arr):
    unprocessed = set(arr)
    maxlen = 0
    while unprocessed:
        elem = unprocessed.pop()
        lower = elem - 1
        while lower in unprocesssed:
            unprocessed.remove(lower)
            lower = lower-1
        upper = elem + 1
        while upper in unprocessed:
            unprocessed.remove(upper)
            upper = upper+1
        maxlen = max(maxlen, upper-lower-1)
    return maxlen

时间 O(n)

空间 O(C)

list vs. dictionary

list存储的是单独的元素，而字典存储的是对应关系（mapping），或者叫它映射。我们叫它Key-value pair，键值-存储值。

对任何一个数据结构，都需要知道 创建、增、删、查、改

创建

my_dict = {}
grades = {'Ana': 'B', 'John': 'A+', 'Denise': 'A', 'Katy': 'A'}

查找

字典没有顺序，只能按key查找，所以必须是存在在字典里的元素，不然直接run下行就会出现key error

grades['John']

还有一个函数，get 如果找不到，可以给None

print (grades.get ('Bob'))

判断key在不在字典里，就可以用lookup的操作，

'John' in grades  #return False
'Daniel' in grades #return True 

增改

加一个新的entry、改已有的syntax，都可以很简单的

grades['John'] = 'A'
grades['Ana'] = 'B+'

删除

del grades['Ana'] #从字典里取这个key，然后删了
grades.pop('Ana')  #随机pop出一个Ana（如果有两个Ana）

拿到key的集合

python2 用grades.keys() return的是[‘A’, 'A', 'A+', 'B'] （value的list）

python3 的return是 （value的view）

view都不会占额外的空间，就像是range和xrange的区别

当然也可以用list(dict.keys()) ，占空间呗

拿到value的集合

类似👆

requirements for keys

1. Key必须unique，不能重复；第二次的一样的值会把第一个覆盖掉

2. Key必须是immutable的类型 所以X={[1]:0}不对，list unhashable

像Y={(1,2):10}就行，str也行

Dictionary Implementation

字典，hash的实现里，不需要去查找每个元素了，而是有一系列的buckets。每次有一个key，先算hashfunction（key），通过这个值，来得到bucket的序号。hashfunc可以接收任何变量，最后它能计算出一个integer，下面的code中，array_size是一个常数，也就是bucket size. 用算好的hash来%array_size, 得到index，意味着最后要把它放到index的桶里去找。

hash = hashfunc(key)
index = hash % array_size

Hash Collision

假设两个key，x和y，本身x!=y, 但是hash(x)==hash(y), 就有了collision，因为它们被映射到了同一个bucket里，所以在第二行一定一样。

此外，因为array_size是一个定值，即使1不一样了，到2还是有可能一样，那还是会collision。

如果有perfect hashing, array_size又是无穷大（这在实际情况中是不存在的），就不会有冲突。

那么 现实中如何解决hash collision？

策略一： open addressing

如果算出来的数值被占了，发生了hash collision，就占用它最近的没有被占用的单元。

策略二：separate chaining

在每一个bucket里，就做成链表，把下一个人直接占在它后面 worst case就是，如果bucket=1(概率极低), 那么就变成了singly linked list，那么查找的时间复杂度又是O(n)了 不过，on average 还是可以O(1)

Time Complexity of different operations on dictionary

|Operation | Avg | Worst |

Search O(1) O(n)

Add O(1) O(n)

Delete O(1) O(n)

Update O(1) O(n)

Set

有时我们并不关心value，只关心key本身，这个时候dict就退化成了set，集合。集合就是只包含了key的hashtable。需要注意的是，集合本身可变mutable，但是里面包含的元素不变。所以增删查改咯～

Add

x = {"a","b","c","d"}
x.add("e") #one element

x.update({"e", "f"}) #multiple elements

remove

如果remove的元素不在，使用x.remove会报keyerror； 但是使用x.discard("a")不会报

如果从中随意删除任何一个(因为set没有顺序，所以真的不知道删了哪个... )，x.pop()； 如果是清空，x.clear() ；

union

下面是集合操作的取并集 这个x和y是用set（）把list变成集合

x = set(["Postcard", "Radio", "Telegram"])

y = set([ "Radio", "Television"])

print x.union(y)

更多

set也有set comprehension

{expression for value in collection if condition}

squared = {x**2 for x in [1,1,2]}

Recap

1. One to one mapping

2. <key, value> pair, key map to value

3. Key, no duplicates

4. Value, allow duplicates

5. hash_set is a set {1,3}, it only contains keys

In python, hash_set is set; hash_table is dictionary

题目

find one missing from unsorted array

1. use a set, iterate over the input array Average O(n) Worst O(n^2)

2. for each number from 1 to n: find if it's in the set Average O(n) Worst O(n^2)

优化 use a boolean[]

因为连续，可以放进物理连续的boolean array里 Step 1: for each element in the input array (value=i), put it into the seen[i]=true O(n) Step 2: for each element from 1...n: check if seen[i]==true O(n)

数学

等差数列求和，减去sum of input array，剩下的就是output Space O(1) but it may overflow

bit operation XOR

• 交换律 a XOR b = b XOR a

• 结合律 a XOR (b XOR c) = (a XOR b) XOR c

• 0是单元 0 XOR a = a

• a XOR a =0

class Solution(object):
  def missing(self, array):
    """
    input: int[] array
    return: int
    """
    # write your solution here
    n = len(array)+1
    xor = 0
    for i in range(1, n+1):
      xor ^= i
    for num in array:
      xor ^= num
    
    return xor

find common numbers between 2 sorted arrays a[M], b[N]

需要确认 如果有重复元素怎么办

Assume没有重复 或者 有重复元素只输出一次

Hashset

比较大小，把小的放进hashset

Step 1: Insert all elements from smaller array a into the hash set

Step 2: For each element in array b, check if it's in the HashSet or not

Time = O(M+N) average, worst O(M^2+N*M) Space = O(M)

谁小移谁

不相等就谁小移谁，相等就分别往前

Time = O(M+N) Space = O(1)

class Solution(object):
  def common(self, A, B):
    """
    input: int[] A, int[] B
    return: Integer[]
    """
    # write your solution here
    i, j = 0, 0
    result = []
    while (i<len(A) and j<len(B)):
      if (A[i]==B[j]):
        result.append(A[i])
        i+=1
        j+=1
      elif A[i]<B[j]:
        i+=1
      else:
        j+=1
    return result

如果M<<<N Binary Search

For each element in b[N], run binary search M times.

Time = O(MlogN) Space = O(1)

2 sum sorted

因为是sorted，所以可以用2 pointers的方法，利用增加和减小的单调性：一个往前移一个往后移；如果现在的和比target小，移动i往后；如果比现在的target大，移动j往前。

def two_sum(list, target):
    i,j = 0, len(list)-1
    while i<j:
        if list[i]+list[j] < target:
            i += 1
        elif list[i]+list[j] > target:
            j -= 1
        elif list[i]+list[j] == target:
            return True
    return False
    
# Time O(n)
# Space O(1)

2 sum unsorted

利用set的性质，经过的数字都存下来；用target的数字和当前经过的数字相减，如果得到的结果在之前的set里，就找到了，return true。否则，false。

def two_sum(list, target):
    hashset = set()
    for key in list:
        if (target-key) in hashset:
            return True
        else:
            hashset.add(key)
    return False
    
# Time O(n)
# Space O(n)

2 sum with duplicates

[10, 2, 2, 13, 2], target 4

• 如果题目要output多少对，用一个dict，存count： {10:1, 2:2, ...}

• 如果题目要output哪些index的组合，dict里是list of index: {10:(0), 2:(1,2), ...}

def two_sum_duplicate(arr, sum):
    dic = {}
    count = 0
    for key in arr:
        if sum-key in dic:
            count+=dic[sum-key]
        if key in dic:
            dic[key]+=1
        else:
            dic[key]=1
    return count

# Time O(n)
# Space O(n)

3 sum unsorted

方法一：走n遍的2 sum。Time O( $n^2$ ) Space O(n)

方法二：先排序，反正已经O( $n^2$ )了，就算先排序也不会影响这个时间复杂度，那就排序吧！可以让空间复杂都变成O(1)。

def three_sum (array, target):
    if array is None or len(array)==0:
        return False
    
    array.sort()
    for i in range(len(array)-2):
        start = i + 1
        end = len(array)-1
        while start<end:
            tmp_sum = array[start] + array[end] + array[i]
            if tmp_sum == target:
                return True
            elif tmp_sum < target:
                start += 1
            else:
                end -= 1
        return False
        
# Time O(n2)
# Space O(1)

4 sum unsorted

方法一：走n遍的3 sum。O( $n^3$ )

for i in range(len(array)-3):
  for j in range(i+1, len(array)-2):
    #2sum  
  
# Time O(n3)
# Space O(1)

方法二：变成2个2sum，如何找到pair of 2 sum, 和是target。 1. 先配对 O( $n^2$ ) 2. sort一遍或者hashset O( $n^2$ ) 3. 在配对的时候要检查它是否是用过的 O(1)

class twoSumPair:
    def __init__(self, index1, index2):
        self.index1 = index1
        self.index2 = index2
        self.number1 = array[index1]
        self.number2 = array[index2]
        self.sum = self.number1 + self.number2

    pairlist=[twoSumPair(0,1), twoSumPair(0,2), twoSumPair(0,3), twoSumPair(0,4),
    twoSumPair(1,2),twoSumPair(1,3)...]

k sum

在array里选k个数字组成sum=target。DFS，k个数字的subset

2 difference sorted

2 pointers，错一位同向而行。因为如果是相向而行，目前的值大于target，那么移动i或者j都行，所以到底移动哪个？ 两个都尝试时间复杂度就会变高。同向而行，如果当前值大于target，移动i向前；如果当前值小于target，移动j向前。

def two_difference(array,target):
    i,j = 0, 1
    while j<len(array):
        if array[j]-array[i] < target:
            j += 1
        elif array[j]-array[i] > target:
            i += 1
        elif:
            return True
    return False
    
# Time O(n)
# Space O(1)

2 difference unsorted

1. 创建set

2. loop array，检查set里的元素是否等于array[i]-target或者array[i]+target

def two_sum(list, target):
    hashset = set()
    for key in list:
        if (key-target) in hashset or (target+key) in hashset:
            return True
        else:
            hashset.add(key)
    return False
    
# Time O(n)
# Space O(n)

Longest sublist without duplicate values.

1 2 3 1 4 3 longest is 2 3 1 4

def longest_sub_list(list):
    hashset=set()
    longest=0
    slow=fast=0
    while fast<len(list):
        while list[fast] in hashset:
            hashset.remove(list[slow])
            slow+=1
        hashset.add(list[fast])
        longest = max(longest, fast-slow+1)
        fast+=1
    return longest