跟随代码随想录进行笔记整理

---

哈希表hash table

• 数据结构：key-value
• 常见的三种哈希结构 and 什么情况下选用该数据结构
  • 数组（索引，值）（初始化为a = []）
    • 💚（首选）哈希值比较小且范围可控时
    • ord()函数可用于获取给定字母的ASCII码值。用法举例：ord(a)
  • 集合unordered_set
    • 💚哈希值比较大时，或元素值分布比较分散（如：1，10，1000）
  • 映射（C++中unordered_map）（python中的字典，初始化为a = {}或a = dict()）
    • 💚有key有value时
• ⭐️适用场景：用于快速判断某个元素是否在集合中【牺牲空间换取时间】
• 哈希函数：hash function可以把传入的数据key转化为不同的数值，映射到哈希表的索引上index = hashFunction(name) = hashCode(name) % tableSize
• 哈希碰撞：如果数据经过哈希函数转化后，多个key映射到相同的索引上时，则称出现了哈希碰撞
  • 哈希碰撞的解决办法：
    • 拉链法：将冲突的元素存储到链表中，从而通过索引找到相应元素。
      
  • 线性探测法使用前提：一定要保证tableSize大于dataSize
    • 如果发生碰撞了，那就先放置其中一个元素，然后找下一个空位来放置剩余元素