散列表(Hash Table)结构是字典(Dictionary)和集合(Set)的一种实现方式。散列算法的作用是尽可能快地在数据结构中找到一个值。在散列表上插入、删除和取用数据都非常快,但是对于查找操作来说却效率地下
散列表是基于数组进行设计的,数组的长度是预先设定,如有需要可随时增加。所有元素根据和该元素对应的键,保存在数组的特定位置。使用散列表存储数据时,通过一个散列函数将键映射为一个数字,这个数字范围是0到列表长度。散列函数的选择依赖于键的数据类型,在此我们对键的hash值对数组长度区余的方法。散列表的数组究竟应该有多大?这是编写散列函数时必须要考虑的。对散列表大小的限制,通常数组的长度应该是一个质数。
理想情况下,散列函数会将每个键值映射为唯一的数组索引,然而,键的数量是无限的,散列表的长度是有限的,一个理想的目标是让散列函数尽量将键均匀地映射到散列表中。即使使用一个高效的散列函数,仍然存在将两个键映射为同一个值的可能,这种现象称为碰撞(collision)。当碰撞发生时,我们需要方案去解决。
负载因子:如果我们持续往散列表中添加数据空间会不够用。负载因子是已使用的空间比散列表大小的值。比如,散列表大小为13,已使用空间位8,负载因子位0.62。通常当负载因子超过0.8时,就要新开辟空间并重新散列了。
散列表的操作:
方法 | 操作 |
---|---|
put | 向散列表添加新键值,或更新键的值 |
remove | 从散列表删除键值 |
get | 返回键索引到的值 |
# python3
class HashTable:
def __init__(self, size=11):
self._keys = [None] * size
self._values = [None] * size
self._length = 0
# 获取负载因子
@property
def _load_factor(self):
return self._length / float(len(self._keys))
# 散列函数
def _hash_func(self, key):
l = len(self._keys)
idx = abs(hash(key)) % l
# 获取空索引
while self._keys[idx] is not None and \
self._keys[idx] != key:
idx = (idx + l + 1) % l
return idx
def put(self, key, value):
idx = self._hash_func(key)
# 更新
if self._keys[idx] == key:
self._values[idx] = value
# 添加
elif self._keys[idx] is None:
self._keys[idx] = key
self._values[idx] = value
self._length += 1
# 检查负载因子
if self._load_factor >= 0.8:
self._rehash()
def get(self, key):
idx = self._hash_func(key)
if self._keys[idx] == key:
return self._values[idx]
return None
def remove(self, key):
idx = self._hash_func(key)
if self._keys[idx] == key:
self._keys[idx] = None
self._values[idx] = None
self._length -= 1
elif self._keys[idx] is None:
self._values[idx] = None
else:
return -1
# 重新散列,扩展大小
def _rehash(self):
old_keys = self._keys
old_value = self._values
new_size = len(self._keys) * 2
self._keys = [None] * new_size
self._values = [None] * new_size
self._length = 0
for idx in range(len(old_keys)):
if old_keys[idx] is not None:
self.put(old_keys[idx], old_value[idx])
def length(self):
return self._length
散列表的基本方法就是字典常用的方法,在此可以继承散列表类的方法,然后完善其他的字典支持的方法。
字典的操作:
方法 | 操作 |
---|---|
keys | 返回所有键 |
values | 返回所有值 |
items | 返回所有键值对 |
# python3
class Dict(HashTable):
def keys(self):
return [key for key in self._keys if key is not None]
def values(self):
return [value for value in self._values if value is not None]
def items(self):
return [(self._keys[idx], self._values[idx])
for idx in range(0, len(self._keys))
if self._keys[idx] is not None]
def __iter__(self):
return iter(self.keys())
def __len__(self):
return self.length()
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, value):
self.put(key, value)
def __contains__(self, key):
idx = self._hash_func(key)
return self._keys[idx] is not None
集合是一种包含不同元素的数据结构。集合中的元素被称为成员。集合的两个重要特性:首先,集合中的成员是无序的;其次:集合中不允许相同的成员存在。
集合的定义:
集合的运算:
其实集合也是个散列表,散列表有键和值,在这里我们把值设置位True即可。具体实现如下。
集合的操作:
方法 | 操作 |
---|---|
put | 向集合添加成员。 |
remove | 从集合移除成员。 |
union | 接收一个集合进行并集运算返回结果 |
intersection | 接收一个集合进行交集运算返回结果 |
difference | 接收一个集合进行补集运算返回结果 |
# python3
class Set(HashTable):
def put(self, key):
return super(Set, self).put(key, value=True)
# 并集运算
def union(self, other):
if isinstance(other, Set):
temp = other
for key in self._keys:
temp.put(key)
return temp
else:
raise TypeError
# 交集运算
def intersection(self, other):
if isinstance(other, Set):
temp = Set()
for key in self._keys:
if key in other:
temp.put(key)
return temp
else:
raise TypeError()
# 补集运算
def difference(self, other):
if isinstance(other, Set):
temp = Set()
for key in self._keys:
if key not in other:
temp.put(key)
return temp
else:
raise TypeError()
def __or__(self, other):
return self.union(other)
def __and__(self, other):
return self.intersection(other)
def __sub__(self, other):
return self.difference(other)
def __len__(self):
return self._length
def __iter__(self):
for key in self._keys:
if key is not None:
yield key
def __contains__(self, key):
idx = self._hash_func(key)
return self._keys[idx] is not None