Python hashmap

2023-01-31 04:01:47 python hashmap
 
标签： pythonHashMap
2014-10-15 18:42 533人阅读 评论(0) 收藏 举报
 分类：
 

版权声明：本文为博主原创文章，未经博主允许不得转载。

[python] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. class LinearMap(object):  
  2.   
  3.     def __init__(self):  
  4.         self.items = []  
  5.   
  6.     def add(self, k, v):  
  7.         self.items.append((k, v))  
  8.   
  9.     def get(self, k):  
  10.         for key, val in self.items:  
  11.             if key == k:  
  12.                 return val  
  13.         raise KeyError  
  14.   
  15.   
  16. class BetterMap(object):  
  17.   
  18.     def __init__(self, n=100):  
  19.         self.maps = []  
  20.         for i in range(n):  
  21.             self.maps.append(LinearMap())  
  22.   
  23.     def find_map(self, k):  
  24.         index = hash(k) % len(self.maps)  
  25.         return self.maps[index]  
  26.   
  27.     def add(self, k, v):  
  28.         m = self.find_map(k)  
  29.         m.add(k, v)  
  30.   
  31.     def get(self, k):  
  32.         m = self.find_map(k)  
  33.         return m.get(k)  
  34.   
  35.   
  36. class <b style="color:#000;background:#66ffff">HashMap</b>(object):  
  37.     def __init__(self):  
  38.         self.maps = BetterMap(2)  
  39.         self.num = 0  
  40.   
  41.     def get(self, k):  
  42.         return self.maps.get(k)  
  43.   
  44.     def add(self, k, v):  
  45.         if self.num == len(self.maps.maps):  
  46.             self.resize()  
  47.   
  48.         self.maps.add(k, v)  
  49.         self.num += 1  
  50.   
  51.     def resize(self):  
  52.         new_map = BetterMap(self.num * 2)  
  53.   
  54.         for m in self.maps.maps:  
  55.             for k, v in m.items:  
  56.                 new_map.add(k, v)  
  57.   
  58.         self.maps = new_map  
  59.   
  60.   
  61. def main(script):  
  62.     import string  
  63.   
  64.     m = <b style="color:#000;background:#66ffff">HashMap</b>()  
  65.     s = string.ascii_lowercase  
  66.   
  67.     for k, v in enumerate(s):  
  68.         m.add(k, v)  
  69.   
  70.     for k in range(len(s)):  
  71.         print k, m.get(k)  
  72.   
  73.   
  74. if __name__ == '__main__':  
  75.     import sys  
  76.     main(*sys.argv)  

相关文章