Python学习笔记（六）——集合、映射与哈希表

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
class Set:
def __init__(self):
self._theElements = list()
def __len__(self):
return len(self._theElements)
def __contains__(self, element):
ndx = self._findPosition(element)
return ndx < len(self) and self._theElements[ndx] == element
def add(self, element):
if element not in self:
ndx = self._findPosition(element)
self._theElements.insert(ndx, element)
def remove(self, element):
assert element in self, "The element must be in the set."
ndx = self._findPosition(element)
self._theElements.pop(ndx)
def _findPosition(self, element):
low = 0
high = len(self._theElements) - 1
while low <= high:
mid = (high + low) // 2
if self._theElements[mid] == element:
return mid
elif element < self._theElements[mid]:
high = mid - 1
else:
low = mid + 1
return low
def __eq__(self, setB):
if len(self) != len(setB):
return False
else:
return self.isSubsetOf(setB)
def isSubsetOf(self, setB):
for element in self:
if element not in setB:
return False
return True
# def union(self, setB):
#
newSet = Set()
#
newSet._theElements.extend(self._theElements)
#
for element in setB:
#
if element not in self:
#
newSet._theElements.append(element)
#
return newSet
def union(self, setB):
newSet = Set()
a = 0
b = 0
while a < len(self) and b < len(setB):
valueA = self._theElements[a]
valueB = self._theElements[b]
if valueA < valueB:
newSet._theElements.append(valueA)
a += 1
elif valueA > valueB:
newSet._theElements.append(valueB)
b += 1
else:
newSet._theElements.append(valueA)
a += 1
b += 1
while a < len(self):
newSet._theElements.append(self._theElements[a])
a += 1
while b < len(setB):
newSet._theElements.append(setB._theELements[b])
b += 1
return newSet
def interset(self, setB):
newSet = Set()
for element in self._theElements:
if element in setB:
newSet._theElements.append(element)
return newSet
def difference(self, setB):
newSet1 = self.union(setB)
newSet2 = self.interset(setB)
newSet = Set()
for element in newSet1:
if element not in newSet2:
newSet._theElements.append(element)
return newSet
def __iter__(self):
return _SetIterator(self._theElements)
class _SetIterator:
def __init__(self, theset):
self._theset = theset
self._curNdx = 0
def __iter__(self):
return self
def __next__(self):
if self._curNdx < len(self._theset):
entry = self._theset[self._curNdx]
self._curNdx += 1
return entry
else:
raise StopIteration

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
class Map:
def __init__(self):
self._entryList = list()
def __len__(self):
return len(self._entryList)
def __contains__(self, key):
ndx = self._findPosition(key)
return ndx is not None
# Adds a new entry to the map if the key does exist.
# Otherwise, the new value replaces the current value associated with the key.
def add(self, key, value):
ndx = self._findPosition(key)
if ndx is not None:
# if the key was found
self._entryList[ndx].value = value
return False
else:
entry = _MapEntry(key, value)
self._entryList.append(entry)
return True
def valueOf(self, key):
ndx = self._findPosition(key)
assert ndx is not None, "Invalid map key."
return self._entryList[ndx].value
def remove(self, key):
ndx = self._findPosition(key)
assert ndx is not None, "Invalid map key."
ndx = self._entryList.pop(ndx)
def __iter__(self):
return _MapIterator(self._entryList)
def _findPosition(self, key):
for i in range(len(self)):
if self._entryList[i].key == key:
return i
return None
class _MapEntry:
def __init__(self, key, value):
self.key = key
self.value = value
class _MapIterator:
def __init__(self, themap):
self._themap = themap
self._curNdx = 0
def __iter__(self):
return self
def __next__(self):
if self._curNdx < len(self._themap):
entry = self._themap[self._curNdx]
self._curNdx += 1
return entry
else:
raise StopIteration

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
from array import Array
class _MapEntry:
def __init__(self, key, value):
self.key = key
self.value = value
class HashMap:
UNUSED = None
# 大写表示常量
EMPTY = _MapEntry(None, None)
def __init__(self):
self._table = Array(7)
self._count = 0
self._maxCount = len(self._table) - len(self._table) // 3
def __len__(self):
return self._count
def __contains__(self, key):
slot = self._findSlot(key, False)
return slot is not None
# Adds a new entry to the map if the key does not exist. Otherwise, the
# new value replaces the current value associated with the key.
def add(self, key, value):
if key in self:
slot = self._findSlot(key, False)
self._table[slot].value = value
return False
else:
slot = self._findSlot(key, True)
self._table[slot] = _MapEntry(key, value)
self._count += 1
if self._count == self._maxCount:
self._rehash()
return True
def valueOf(self, key):
slot = self._findSlot(key, False)
assert slot is not None, "Invalid map key."
return self._table[slot].value
def remove(self, key):
slot = self._findSlot(key, False)
assert slot is not None, "Invalid map key."
self._table[slot] = self.EMPTY
return True
def __iter__(self):
return _HashMapIterator(self._table)
# Finds the slot containing the key or where the key can be added.
# forInsert indicates if the search is for an insertion, which locates
# the slot into which the new key can be added.
def _findSlot(self, key, forInsert):
slot = self._hash1(key)
step = self._hash2(key)
M = len(self._table)
while self._table[slot] is not self.UNUSED:
if forInsert and 
(self._table[slot] is self.UNUSED or self._table[slot] is self.EMPTY):
return slot
elif not forInsert and 
(self._table[slot] is not self.EMPTY and self._table[slot].key == key):
return slot
else:
slot = (slot + step) % M
if self._table[slot] is self.UNUSED and forInsert and 
(self._table[slot] is self.UNUSED or self._table[slot] is self.EMPTY):
return slot
def _rehash(self):
origTable = self._table
newSize = len(self._table) * 2 + 1
self._table = Array(newSize)
self._count = 0
self._maxCount = newSize - newSize // 3
for entry in origTable:
if entry is not self.UNUSED and entry is not self.EMPTY:
key = entry.key
slot = self._findSlot(key, True)
self._table[slot] = entry
self._count += 1
def _hash1(self, key):
return abs(hash(key)) % len(self._table)
def _hash2(self, key):
return 1 + abs(hash(key)) % (len(self._table) - 2)
class _HashMapIterator:
def __init__(self, theHashMap):
self._theHashMap = theHashMap
self._curNdx = 0
def __iter__(self):
return self
def __next__(self):
if self._curNdx < len(self._theHashMap):
entry = self._theHashMap[self._curNdx]
self._curNdx += 1
return entry
else:
raise StopIteration
def main():
lst = [46,23,67,67]
hashmap = HashMap()
c = 1
for i in lst:
hashmap.add(i,c)
c += 1
for h in hashmap:
if h == None:
print("not be filled")
else:
print(h.key, h.value)
lst = [46,23,67,'s','a','d','s','s',54,54,67,32,8]
hashmap = HashMap()
c = 1
for i in lst:
hashmap.add(i,c)
c += 1
for h in hashmap:
if h == None:
print("not be filled")
else:
print(h.key, h.value)
main()
'''
output:
67 4
not be filled
23 2
not be filled
46 1
not be filled
not be filled
not be filled
s 8
32 12
d 6
not be filled
not be filled
not be filled
67 11
23 2
46 1
not be filled
8 13
54 10
a 5
not be filled
'''