散列表结构 字典与集合
散列表
散列表(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