修改hashmap实现中的bug。

ssjssh · ssjssh · commit d89a2c8fee41 · 2015-09-27T15:56:55.000+08:00
diff --git a/src/ssj/map/hash_map.py b/src/ssj/map/hash_map.py
@@ -20,14 +20,17 @@ class Node(object):
         哈希表中存储的节点
         """
 
-        def __init__(self, key, value, hash_code, prev, nex):
+        def __init__(self, key, value, hash_code, nex, last_insert, next_insert):
             """
+            nex用来解决链表的哈希冲突
+            next_insert用来记录下一个插入的元素
             """
             self.key = key
             self.value = value
             self.hash_code = hash_code
             self.nex = nex
-            self.prev = prev
+            self.last_insert = last_insert
+            self.next_insert = next_insert
 
         def __cmp__(self, other):
             return cmp(self.key, other.key)
@@ -44,13 +47,13 @@ def __init__(self):
         """"""
         self.__load_factor = 0
         self.__size = 0  # 表示真正存储的元素有几个
-        self.__power = HashMap.DEFAULT_SIZE_POWER
+        self.__power = HashMap.DEFAULT_SIZE_POWER  # 把哈希表大小存储为幂数，这样的好处不用在扩展时再从头计算
         self.__cap = HashMap.DEFAULT_SIZE  # 表示哈希表的容量
         self.__head = None
-        self.__last_put = None
-        self.__values = [[] for x in range(0, self.__cap)]
+        self.__last_put = None  # 存储上一个插入时的元素，这样便于在插入新元素的时候用指针把他们按照插入顺序连接起来
+        self.__values = [None for x in range(0, self.__cap)]  # 主要使用的列表
 
-    def hash(self, key):
+    def __get_index(self, key):
         """
         乘法哈希函数
         :param key:
@@ -72,67 +75,87 @@ def __resize(self):
             # 如果哈希表太满了,则把原来的所有元素都重新插入到哈希表中去
             self.__cap *= 2
             self.__power += 1
-            old_values = self.__values
-            self.__values = [[] for x in xrange(0, self.__cap)]
+            self.__values = [None for x in xrange(0, self.__cap)]
             self.__size = 0
             self.__load_factor = 0
             self.__last_put = None
             cur_node = self.__head
             self.__head = None
-            while cur_node is not None:
+            while cur_node:
                 self.__setitem__(cur_node.key, cur_node.value)
-                cur_node = cur_node.nex
+                cur_node = cur_node.next_insert
 
     def foreach(self, f):
         cur_node = self.__head
-        while cur_node is not None:
+        while cur_node:
             yield f(cur_node.key, cur_node.value)
-            cur_node = cur_node.nex
+            cur_node = cur_node.next_insert
 
     def __get(self, key):
-        index = self.hash(key)
-        indexed_nodes = self.__values[index]
-        for node in indexed_nodes:
-            if node.key == key:
-                return node
+        index = self.__get_index(key)
+        indexed_node = self.__values[index]
+        while indexed_node:
+            if indexed_node.key == key:
+                return indexed_node
+            indexed_node = indexed_node.nex
         return None
 
     def __contains__(self, key):
         node = self.__get(key)
-        return False if node is None else True
+        return node
 
     def __getitem__(self, item):
         node = self.__get(item)
         return None if node is None else node.value
 
     def __setitem__(self, key, value):
-        node = self.Node(key, value, HashMap.hash_code(key), self.__last_put, None)
-        index = self.hash(key)
+        index = self.__get_index(key)
+
         exists_nodes = self.__values[index]
         exists_flag = False
-        for x in range(0, len(exists_nodes)):
-            if node == exists_nodes[x]:
-                exists_nodes[x] = node
-                exists_flag = True
+        if exists_nodes:
+            cur_node = exists_nodes
+            while cur_node:
+                if cur_node.key == key:
+                    exists_flag = True
+                    cur_node.value = value
+                    node = cur_node
+                    break
+                cur_node = cur_node.nex
+
         if not exists_flag:
-            exists_nodes.append(node)
+            node = self.Node(key, value, HashMap.hash_code(key), exists_nodes, self.__last_put, None)
+            self.__values[index] = node
             self.__size += 1
-        if self.__last_put is not None:
-            self.__last_put.nex = node
+
+        if self.__last_put:
+            self.__last_put.next_insert = node
         self.__last_put = node
-        if self.__head is None:
+        if not self.__head:
             self.__head = node
-        self.__load_factor = float(self.__size) / self.__cap
         self.__resize()
 
     def __delitem__(self, key):
         old_value = None
-        index = self.hash(key)
-        indexed_nodes = self.__values[index]
-        for x in xrange(len(indexed_nodes)):
-            if indexed_nodes[x].key == key:
-                old_value = indexed_nodes[x].value
-                del indexed_nodes[x]
+        index = self.__get_index(key)
+        indexed_node = self.__values[index]
+        last_node = None
+        while indexed_node:
+            if indexed_node.key == key:
+                old_value = indexed_node.value
+                if last_node:
+                    last_node.nex = indexed_node.nex
+                else:
+                    self.__values[index] = indexed_node.nex
+                # 处理哈希表
+                self.__size -= 1
+                if indexed_node.last_insert:
+                    indexed_node.last_insert.next_insert = indexed_node.next_insert
+
+                if indexed_node.next_insert:
+                    indexed_node.next_insert.last_insert = indexed_node.last_insert
+            last_node = indexed_node
+            indexed_node = indexed_node.nex
         return old_value
 
     def __len__(self):
@@ -148,8 +171,10 @@ def main():
         d["ssh" + str(x)] = x
     print len(d)
     print d
-    del d['ssj100']
-    print d['ssj100']
+    del d['ssh100']
+    print d['ssh100']
+    print(len(d))
+    print(d)
 
 
 if __name__ == "__main__":
