Python的集合set原理
集合（set）是一个无序的不重复元素序列。
可以使用大括号 { } 或者 set() 函数创建集合，注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。
|
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
157
158
159
160
161
162
163
164
165
166
167
168
|
class Array(object): def __init__(self, size=32, init=None): self._size = size self._items = [init] * self._size def __getitem__(self, index): return self._items[index] def __setitem__(self, index, value): self._items[index] = value def __len__(self): return self._size def clear(self, value=None): for i in range(len(self._items)): self._items[i] = value def __iter__(self): for item in self._items: yield itemclass Slot(object): """定义一个 hash 表 数组的槽 注意，一个槽有三种状态，看你能否想明白 1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到 UNUSED 就不用再继续探查了 2.使用过但是 remove 了，此时是 HashMap.EMPTY，该探查点后边的元素扔可能是有key 3.槽正在使用 Slot 节点 """ def __init__(self, key, value): self.key, self.value = key, valueclass HashTable(object): # 表示从未被使用过 UNUSED = None # 使用过，但是被删除了 EMPTY = Slot(None, None) def __init__(self): self._table = Array(8, init=HashTable.UNUSED) self.length = 0 # 负载因子 @property def _load_factor(self): return self.length/float(len(self._table)) def __len__(self): return self.length # 哈希函数 用内置的哈希哈数进行哈希一下，然后对数组长度取模 def _hash(self, key): return abs(hash(key)) % len(self._table) def _find_key(self, key): # 得到第一个值的位置 index = self._hash(key) _len = len(self._table) # 当这个槽不是未使用过的，才接着往下找；如果是未使用过的，这个key肯定不存在 while self._table[index] is not HashTable.UNUSED: # 槽使用过，但是被删除了 if self._table[index] is HashTable.EMPTY: # cpython解决哈希冲突的一种方式 index = (index*5 + 1) % _len continue elif self._table[index] == key: return index else: index = (index * 5 + 1) % _len return None # 检测槽是否能被插入 def _slot_can_insert(self, index): return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED) # 找到能被插入的槽的index def _find_slot_insert(self, key): # 得到第一个值的位置 index = self._hash(key) _len = len(self._table) while not self._slot_can_insert(index): index = (index * 5 + 1) % _len return index # in 操作符 def __contains__(self, key): index = self._find_key(key) return index is not None def add(self, key, value): if key in self: index = self._find_key(key) # 更新值 self._table[index].value = value return False else: index = self._find_slot_insert(key) self._table[index] = Slot(key, value) self.length += 1 if self._load_factor > 0.8: return self._rehash() return True def _rehash(self): oldtable = self._table newsize = len(self._table) * 2 # 新的table self._table = Array(newsize, HashTable.UNUSED) self.length = 0 for slot in oldtable: if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY: index = self._find_slot_insert(slot.key) self._table[index] = slot self.length += 1 def get(self, key, default=None): index = self._find_key(key) if index is None: return default else: return self._table[index].value def remove(self, key): index = self._find_key(key) if index is None: raise KeyError value = self._table[index].value self.length -= 1 # 把槽设置为空槽 self._table[index] = HashTable.EMPTY return value def __iter__(self): for slot in self._table: if slot not in (HashTable.UNUSED, HashTable.EMPTY): yield slot.valueclass SetADT(HashTable): def add(self, key): return super(SetADT, self).add(key, True) def __and__(self, other_set): # 求交集 new_set = SetADT() for element_a in self: if element_a in other_set: new_set.add(element_a) return new_set def __sub__(self, other_set): # 求差集 new_set = SetADT() for element_a in self: if element_a not in other_set: new_set.add(element_a) return new_set def __or__(self, other_set): # 求交集 new_set = SetADT() for element_a in self: new_set.add(element_a) for element_b in other_set: new_set.add(element_b) return new_set |
以上就是Python 实现集合Set的示例的详细内容，更多关于Python 实现集合Set的资料请关注服务器之家其它相关文章！
原文链接：https://www.cnblogs.com/guotianbao/p/12731390.html
