码农要术:算法篇:哈希表

July 11, 2020

image-20200712013703682

image-20200712014132444

各位观众老爷大家好,今天准备开始一个系列,leetcode的题目讲解。

作为码农,算法是基本功。平时工作中会用到,面试的时候也是必考。对于学生来说,如果有程序设计竞赛的成绩,比如ACM,一般都会优先录取。对于社招来说,因为面试者和面试官基本上都不认识,怎么能短时间内看出你的能力呢,除了聊项目,那基本功肯定得考察一下了。

所以说学习算法肯定是不亏的。我的第一份工作是百度,这与当时参加2012年的百度之星的比赛也挺有关系。我搜了下邮件,成绩大概在全国前200名。

上学那会更多的是参加topcoder,还有各大高校的online judge系统,比如浙大的,北大的。

leetcode平台近几年也越来越火,大家纷纷在平台上磨练自己的算法能力。现在想定个小目标,用业余的时间,把leetcode的题目做一下。一方面是锻炼自己,长时间没有刷题,算法的知识有些遗忘。一方面是把自己学习算法的一些经验分享给各位观众老爷,希望能在面试或者工作中帮助到你。

好了,长话短说,我们开始第一题。

collision

开放寻址:python dict

拉链式:java HashMap,redis,unordered_map(libstdc++, boosting)

MurmurHash

nums_index = {val: idx for idx, val in enumerate(nums)}
for i in range(len(nums)):
  residual = target - nums[i]
  if residual in nums_index and i != nums_index[residual]:
    return (i, nums_index[residual])

# hit and run,走A
nums_index = {}
for i in range(0, len(nums)):
  residual = target - nums[i]
  if residual in nums_index:
    return [i, nums_index[residual]]
  nums_index[nums[i]] = i
  
class HashMap(object):
    def __init__(self, size):
        # bucket (raw_key_list, value_list)
        self.hashmap = [([],[]) for i in range(size)]

    def hash_function(self, x):
        # MurmurHash
        return x * 314159265 % len(self.hashmap)

    def insert(self, k, v):
        key = self.hash_function(k)
        bucket = self.hashmap[key]
        if k in bucket[0]:
            pass
        else:
            bucket[0].append(k)
            bucket[1].append(v)

    def get(self, k):
        key = self.hash_function(k)
        bucket = self.hashmap[key]
        if k in bucket[0]:
            return bucket[1][bucket[0].index(k)]
        return None

码农要术:算法篇:哈希表 - July 11, 2020 -