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

一、集合

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

二、映射

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

三、哈希表

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
'''

四、Histograms（直方图、柱状图）

未解决

最后

以上就是美丽宝贝为你收集整理的Python学习笔记（六）——集合、映射与哈希表的全部内容，希望文章能够帮你解决Python学习笔记（六）——集合、映射与哈希表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。