码农要术:算法篇:哈希表
July 11, 2020
各位观众老爷大家好,今天准备开始一个系列,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