@@ -20,14 +20,17 @@ class Node(object):
2020 哈希表中存储的节点
2121 """
2222
23- def __init__ (self ,key ,value ,hash_code ,prev , nex ):
23+ def __init__ (self ,key ,value ,hash_code ,nex , last_insert , next_insert ):
2424"""
25+ nex用来解决链表的哈希冲突
26+ next_insert用来记录下一个插入的元素
2527 """
2628self .key = key
2729self .value = value
2830self .hash_code = hash_code
2931self .nex = nex
30- self .prev = prev
32+ self .last_insert = last_insert
33+ self .next_insert = next_insert
3134
3235def __cmp__ (self ,other ):
3336return cmp (self .key ,other .key )
@@ -44,13 +47,13 @@ def __init__(self):
4447""""""
4548self .__load_factor = 0
4649self .__size = 0 # 表示真正存储的元素有几个
47- self .__power = HashMap .DEFAULT_SIZE_POWER
50+ self .__power = HashMap .DEFAULT_SIZE_POWER # 把哈希表大小存储为幂数，这样的好处不用在扩展时再从头计算
4851self .__cap = HashMap .DEFAULT_SIZE # 表示哈希表的容量
4952self .__head = None
50- self .__last_put = None
51- self .__values = [[] for x in range (0 ,self .__cap )]
53+ self .__last_put = None # 存储上一个插入时的元素，这样便于在插入新元素的时候用指针把他们按照插入顺序连接起来
54+ self .__values = [None for x in range (0 ,self .__cap )]# 主要使用的列表
5255
53- def hash (self ,key ):
56+ def __get_index (self ,key ):
5457"""
5558 乘法哈希函数
5659 :param key:
@@ -72,67 +75,87 @@ def __resize(self):
7275# 如果哈希表太满了,则把原来的所有元素都重新插入到哈希表中去
7376self .__cap *= 2
7477self .__power += 1
75- old_values = self .__values
76- self .__values = [[]for x in xrange (0 ,self .__cap )]
78+ self .__values = [None for x in xrange (0 ,self .__cap )]
7779self .__size = 0
7880self .__load_factor = 0
7981self .__last_put = None
8082cur_node = self .__head
8183self .__head = None
82- while cur_node is not None :
84+ while cur_node :
8385self .__setitem__ (cur_node .key ,cur_node .value )
84- cur_node = cur_node .nex
86+ cur_node = cur_node .next_insert
8587
8688def foreach (self ,f ):
8789cur_node = self .__head
88- while cur_node is not None :
90+ while cur_node :
8991yield f (cur_node .key ,cur_node .value )
90- cur_node = cur_node .nex
92+ cur_node = cur_node .next_insert
9193
9294def __get (self ,key ):
93- index = self .hash (key )
94- indexed_nodes = self .__values [index ]
95- for node in indexed_nodes :
96- if node .key == key :
97- return node
95+ index = self .__get_index (key )
96+ indexed_node = self .__values [index ]
97+ while indexed_node :
98+ if indexed_node .key == key :
99+ return indexed_node
100+ indexed_node = indexed_node .nex
98101return None
99102
100103def __contains__ (self ,key ):
101104node = self .__get (key )
102- return False if node is None else True
105+ return node
103106
104107def __getitem__ (self ,item ):
105108node = self .__get (item )
106109return None if node is None else node .value
107110
108111def __setitem__ (self ,key ,value ):
109- node = self .Node (key , value , HashMap . hash_code ( key ), self . __last_put , None )
110- index = self . hash ( key )
112+ index = self .__get_index (key )
113+
111114exists_nodes = self .__values [index ]
112115exists_flag = False
113- for x in range (0 ,len (exists_nodes )):
114- if node == exists_nodes [x ]:
115- exists_nodes [x ]= node
116- exists_flag = True
116+ if exists_nodes :
117+ cur_node = exists_nodes
118+ while cur_node :
119+ if cur_node .key == key :
120+ exists_flag = True
121+ cur_node .value = value
122+ node = cur_node
123+ break
124+ cur_node = cur_node .nex
125+
117126if not exists_flag :
118- exists_nodes .append (node )
127+ node = self .Node (key ,value ,HashMap .hash_code (key ),exists_nodes ,self .__last_put ,None )
128+ self .__values [index ]= node
119129self .__size += 1
120- if self .__last_put is not None :
121- self .__last_put .nex = node
130+
131+ if self .__last_put :
132+ self .__last_put .next_insert = node
122133self .__last_put = node
123- if self .__head is None :
134+ if not self .__head :
124135self .__head = node
125- self .__load_factor = float (self .__size )/ self .__cap
126136self .__resize ()
127137
128138def __delitem__ (self ,key ):
129139old_value = None
130- index = self .hash (key )
131- indexed_nodes = self .__values [index ]
132- for x in xrange (len (indexed_nodes )):
133- if indexed_nodes [x ].key == key :
134- old_value = indexed_nodes [x ].value
135- del indexed_nodes [x ]
140+ index = self .__get_index (key )
141+ indexed_node = self .__values [index ]
142+ last_node = None
143+ while indexed_node :
144+ if indexed_node .key == key :
145+ old_value = indexed_node .value
146+ if last_node :
147+ last_node .nex = indexed_node .nex
148+ else :
149+ self .__values [index ]= indexed_node .nex
150+ # 处理哈希表
151+ self .__size -= 1
152+ if indexed_node .last_insert :
153+ indexed_node .last_insert .next_insert = indexed_node .next_insert
154+
155+ if indexed_node .next_insert :
156+ indexed_node .next_insert .last_insert = indexed_node .last_insert
157+ last_node = indexed_node
158+ indexed_node = indexed_node .nex
136159return old_value
137160
138161def __len__ (self ):
@@ -148,8 +171,10 @@ def main():
148171d ["ssh" + str (x )]= x
149172print len (d )
150173print d
151- del d ['ssj100' ]
152- print d ['ssj100' ]
174+ del d ['ssh100' ]
175+ print d ['ssh100' ]
176+ print (len (d ))
177+ print (d )
153178
154179
155180if __name__ == "__main__" :
