• 相同键值 映射到相同索引
• 尽量把键映射到不同位置，越分散越好

将一些键值 存储到一个数组中 - 散列表

将整数打散，常用除留余数法

余数可能会相同，出现 collision

• open hash - 开散列
  • separate chaining - 拉链法： 冲突时插入链表，按插入先后顺序
• close hash - 闭散列 - 开放定址法(open addressing) - 线性探测：内存数量大于键值数量，发生冲突则向下遍历直到找到空位

哈希表的性能 - 受装因子影响 Load Factor \(\alpha = \frac{N}{M}\)

N is the number of entries occupied in the hash table

M is the number of buckets

拉链法实现开散列

    class Node:
        def __init__(self, key, calue):
            self.key = key
            self.value = value
            self.next = None
            
    class ChainingHashTable:
        def __init__(self, size):
            """
            初始化散列表大小和数组
            """
            self.size = size
            self.hash_table = [None] * size
            
        def _hash(self, key):
            """
            散列函数、将键转换为散列索引
            """
            return key % self.size
            
        def insert(self, key, value):
            """
            向散列表中插入键值对
            """
            index = self._hash(key)
            if self.hash_table[index] is None:
                self.hash_table[index] = Node(key, value)
            else:
                # 索引位置不为空，遍历链表找到合适位置插入新节点
                current = self.hash_table[index]
                while current.next:
                    current = current.next
                current.next = Node(key, value)    
                
        def serch(self, key):        
            """
            散列表中查找给定键的值
            """
            index = self._hash(key)
            current = self.hash_table[index]
            while current:
                if current.key == key:
                    return current.value
                current = current.next
            return None