02-哈希表

哈希表能够提供快速的插入操作和查找操作，主要是用key的hash值，和容量空间的size进行取余确定索引（无序）

1. 什么是哈希表

哈希表是根据传入的数据的key，value值进行填充，根据key找到它的hash值，再根据固定的数组size进行取余操作得到索引（无序，可能发生冲突覆盖），将key，value值放进数组。

2. 哈希表的优缺点

• 优点
  • 快速查询和插入数据
• 缺点
  • 无序
  • 哈希冲突

3. 一些其他概念

• 装载因子
  • 哈希表动态扩容的判断标志，一般为80%
• 重哈希
  • 开辟新的空间，为原来的2倍大小（二进制，左移一位就可以实现扩容二倍）
• 哈希冲突解决办法
  • 线性探查（向下一个移动直到找到相同的key）
  • 二次探查（+1平方，+2平方，+3平方直到找到相同的key）
  • 线性和链式结构结构（相同key的地方，使用链式结构加到next节点上）

4. 代码

class Array():
    def __init__(self, size=4):
        self.__size = size  # 记录容器大小
        self.__item = [None] * size  # 分配空间
        self.__length = 0

    def __setitem__(self, key, value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, key):
        return self.__item[key]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value


class Slot():
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value

    def __str__(self):
        return 'key: {} value: {}'.format(self.key, self.value)


class HashTable():
    def __init__(self):
        self.size = 4
        self.items = Array(self.size)
        self.length = 0

    def get_index(self, key):
        return hash(key) % self.size

    def find_index_to_insert(self, key):
        index = self.get_index(key)  # 获取key对应的索引
        if self.items[index] is None:
            return index
        else:
            while self.items[index] is not None:
                if self.items[index].key == key:  # 获取到相同的key
                    return index
                else:
                    index = (5 * index + 1) % self.size
            return index

    def put(self, key, value):  # 存放数据
        slot = Slot(key, value)
        index = self.find_index_to_insert(key)  # 获取key对应的索引
        self.items[index] = slot
        self.length += 1
        if self.load_factor():
            self.rehash()

    # 判断是否该扩容-装载因子
    def load_factor(self):
        return self.length / float(self.size) > 0.8

    # 扩充原来的空间大小-重哈希
    def rehash(self):
        # 保存原来的数据
        before = self.items
        # 设置新分配空间的大小
        self.size = self.size << 1
        # 分配新的空间
        self.items = Array(self.size)
        # 重置元素个数
        self.length = 0
        # 将原空间里的数据 放到新空间
        for slot in before:
            if slot:
                key = slot.key
                index = self.find_index_to_insert(key)
                self.items[index] = slot
                self.length += 1

    def find_key(self, key):
        index = self.get_index(key)  # 获取key对应的索引
        if self.items[index] is None:
            return None
        else:
            while self.items is not None:
                if key == self.items[index].key:  # 判断查找的Key是否与item里的key相同
                    return index
                else:
                    # 线性探查（有hash冲突的解决办法之一，还有二次探查和线性结构和链式结构结合等方法）
                    index = (5 * index + 1) % self.size
            return None

    def get(self, key):  # 获取数据
        index = self.find_key(key)  # 获取key对应的索引
        return self.items[index]