标签： pythonhashmap
2014-10-15 18:42 533人阅读 评论(0) 收藏 举报
分类：版权声明：本文为博主原创文章，未经博主允许不得转载。
[python] view
plain copy
- class LinearMap(object):
- def __init__(self):
- self.items = []
- def add(self, k, v):
- self.items.append((k, v))
- def get(self, k):
- for key, val in self.items:
- if key == k:
- return val
- raise KeyError
- class BetterMap(object):
- def __init__(self, n=100):
- self.maps = []
- for i in range(n):
- self.maps.append(LinearMap())
- def find_map(self, k):
- index = hash(k) % len(self.maps)
- return self.maps[index]
- def add(self, k, v):
- m = self.find_map(k)
- m.add(k, v)
- def get(self, k):
- m = self.find_map(k)
- return m.get(k)
- class <b style="color:#000;background:#66ffff">HashMap</b>(object):
- def __init__(self):
- self.maps = BetterMap(2)
- self.num = 0
- def get(self, k):
- return self.maps.get(k)
- def add(self, k, v):
- if self.num == len(self.maps.maps):
- self.resize()
- self.maps.add(k, v)
- self.num += 1
- def resize(self):
- new_map = BetterMap(self.num * 2)
- for m in self.maps.maps:
- for k, v in m.items:
- new_map.add(k, v)
- self.maps = new_map
- def main(script):
- import string
- m = <b style="color:#000;background:#66ffff">HashMap</b>()
- s = string.ascii_lowercase
- for k, v in enumerate(s):
- m.add(k, v)
- for k in range(len(s)):
- print k, m.get(k)
- if __name__ == '__main__':
- import sys
- main(*sys.argv)
