hash map

image.png image.png image.png image.png image.png image.png image.png image.png

自定义hash方法

class People(object):
    def __init__(self, name, age, salary):
        self.name = name
        self.age = age
        self.salary = salary

    def __eq__(self, other):
        return (self.name, self.age, self.salary) == (other.name, other.age, other.salary)

    def __hash__(self):
        return hash((self.name, self.salary))

p = People('bob', 20, 3244)
# 如果没有实现 __hash__方法， 那么hash(p) 会报错 TypeError: unhashable type: 'People'
print(hash(p))

为什么字典的key不能是 list dict set 类型？

因为这些都是可变的数据类型，里面的值一变 hashcode就会变，再去table里就找不到了。

两个数组求交集

def intersection(array1, array2):
    return list(set(array1) & set(array2))


# 上面是去重后的交集
# 如果不去重的话
def intersection2(array1, array2):
    dict1 = {}
    for i in array1:
        if i in dict1:
            dict1[i] += 1
        else:
            dict1[i] = 1

    result = []
    for j in array2:
        if j in dict1 and dict1[j] > 0:
            result.append(j)
            dict1[j] -= 1

    return result


print(intersection2([1, 1, 2, 3], [1, 1, 4]))

珠宝和石头

def jewels_in_store(j, s):
    count = 0
    for i in s:            # O(s)
        if i in j:         # O(j)
            count += 1     # 总的 O(s*j)
    return count


# 上面时间复杂度应该是 O(n*m) 字符串的in是len(str)的时间复杂度
# 改进
def jewels_in_store2(j, s):
    count = 0
    j = set(j)              # 将j变为set O(j)
    for i in s:             # O(s)
        if i in j:          # (1)
            count += 1      # 总的时间复杂度 O(j+s)
    return count


# python的简洁之美
def jewels_in_store3(j, s):
    setj = set(j)
    return sum(i in setj for i in s)

LRU

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
可通过hashmap和一个双向链表实现

image.png