forked from ssjssh/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHashMap.py
More file actions
159 lines (133 loc) · 4.85 KB
/
Copy pathHashMap.py
File metadata and controls
159 lines (133 loc) · 4.85 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#!/usr/bin/env python
# -*- coding:UTF-8
__author__ = 'shenshijun'
class HashMap(object):
"""
使用链接法解决哈希冲突,使用乘法哈希哈希函数
如果空间需要扩充,那么仅仅简单地把存储空间扩展为双倍,然后重新计算一遍哈希函数
另外类似于LinkedHashMap,哈希表里面的元素有组成了一个链表,用来保持插入顺序
"""
# 来自算法导论乘法哈希函数的值,暂时仅支持2**32个元素
HASH_CONST = 2654435769
DEFAULT_SIZE_POWER = 3
DEFAULT_SIZE = 2 << DEFAULT_SIZE_POWER # aka16
DEFAULT_LOAD_FACTOR = 0.75 # 默认装载因子0.75
class Node(object):
"""
哈希表中存储的节点
"""
def __init__(self, key, value, hash_code, prev, nex):
"""
"""
self.key = key
self.value = value
self.hash_code = hash_code
self.nex = nex
self.prev = prev
def __cmp__(self, other):
return cmp(self.key, other.key)
def __str__(self):
return "".join(["Node(key=", str(self.key), ",value=",
str(self.value), ",hash=", str(self.hash_code), ",has_next=",
str(True if self.nex is not None else False), ")"])
def __unicode__(self):
return self.__str__()
def __init__(self):
""""""
self.__load_factor = 0
self.__size = 0 # 表示真正存储的元素有几个
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)]
def hash(self, key):
"""
乘法哈希函数
:param key:
:return:
"""
return (((HashMap.hash_code(key)) * HashMap.HASH_CONST) % (2 ** 32)) >> (32 - self.__power)
@classmethod
def hash_code(cls, key):
"""
计算键的hash值,由于Python中的内建对象并没有很好地提供哈希值,因此需要自己计算
:param key:
:return:
"""
return abs(hash(key))
def __resize(self):
if self.__load_factor > HashMap.DEFAULT_LOAD_FACTOR:
# 如果哈希表太满了,则把原来的所有元素都重新插入到哈希表中去
self.__cap *= 2
self.__power += 1
old_values = self.__values
self.__values = [[] 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:
self.__setitem__(cur_node.key, cur_node.value)
cur_node = cur_node.nex
def foreach(self, f):
cur_node = self.__head
while cur_node is not None:
yield f(cur_node.key, cur_node.value)
cur_node = cur_node.nex
def __get(self, key):
index = self.hash(key)
indexed_nodes = self.__values[index]
for node in indexed_nodes:
if node.key == key:
return node
return None
def __contains__(self, key):
node = self.__get(key)
return False if node is None else True
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)
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 not exists_flag:
exists_nodes.append(node)
self.__size += 1
if self.__last_put is not None:
self.__last_put.nex = node
self.__last_put = node
if self.__head is None:
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]
return old_value
def __len__(self):
return self.__size
def __str__(self):
return "\n".join(self.foreach(lambda key, value: "Node(key=%s,value=%s)" % (key, value)))
def main():
d = HashMap()
for x in xrange(0, 1000):
d["ssh" + str(x)] = x
print len(d)
print d
del d['ssj100']
print d['ssj100']
if __name__ == "__main__":
main()