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