散列表结构 字典与集合

摘要：散列表结构字典与集合散列表散列表结构是字典和集合的一种实现方式。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字范围是到列表长度。即使使用一个高效的散列函数，仍然存在将两个键映射为同一个值的可能，这种现象称为碰撞。

散列表(Hash Table)结构是字典(Dictionary)和集合(Set)的一种实现方式。散列算法的作用是尽可能快地在数据结构中找到一个值。在散列表上插入、删除和取用数据都非常快，但是对于查找操作来说却效率地下

散列表是基于数组进行设计的，数组的长度是预先设定，如有需要可随时增加。所有元素根据和该元素对应的键，保存在数组的特定位置。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字范围是0到列表长度。散列函数的选择依赖于键的数据类型，在此我们对键的hash值对数组长度区余的方法。散列表的数组究竟应该有多大？这是编写散列函数时必须要考虑的。对散列表大小的限制，通常数组的长度应该是一个质数。

理想情况下，散列函数会将每个键值映射为唯一的数组索引，然而，键的数量是无限的，散列表的长度是有限的，一个理想的目标是让散列函数尽量将键均匀地映射到散列表中。即使使用一个高效的散列函数，仍然存在将两个键映射为同一个值的可能，这种现象称为碰撞(collision)。当碰撞发生时，我们需要方案去解决。

分离链接：实现散列表底层数组中，每个数组元素是一个新的数据结构，比如另一个数组(二维数组)，这样就能存储多个键了。即使两个键散列后的值相同，依然被保存在同样的位置，只不过它们在第二个数组中的位置不一样罢了。

线性探查：当发生碰撞时，线性探测法检测散列表的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。

负载因子：如果我们持续往散列表中添加数据空间会不够用。负载因子是已使用的空间比散列表大小的值。比如，散列表大小为13，已使用空间位8，负载因子位0.62。通常当负载因子超过0.8时，就要新开辟空间并重新散列了。

散列表的操作：

# 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

散列表的基本方法就是字典常用的方法，在此可以继承散列表类的方法，然后完善其他的字典支持的方法。

字典的操作：

# 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即可。具体实现如下。

集合的操作：

# 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