哈希表理论基础

哈希表是一种常见的数据结构，最大的优点是高效，在哈希表中插入、删除或查找一个元素都只需要O（1）的时间。因此，哈希表经常被用来优化时间效率。 哈希表的三种形式： - 数组（数组就是一个简单的哈希表，对于哈希表中的 key，如果哈希值比较连续且固定，我们可以用数组的下标来等同） - HashTable（如果每个元素都存在一个值到另一个值的映射，那么就用 HashMap） - HashSet（如果每个元素都只有一个值，或者有去重需要，则用 HashSet。例如，HashSet在图搜索时经常用来存储已经搜索过的节点） 尽管哈希表是很高效的数据结构，但这并不意味着哈希表能解决所有的问题。如果用哈希表作为字典存储若干单词，那么只能输入完整的单词在字典中查找。 - 如果对数据集中的元素排序能够有助于解决问题，那么用 **TreeSet** 或 **TreeMap** 可能更合适 - 如果需要知道一个动态数据集中的最大值或最小值，那么**堆**的效率可能更好。 - 如果希望能够根据前缀进行单词查找，如查找字典中所有以 “ex” 开头的单词，那么应该用**前缀树**作为实现字典的数据结构 <br> 设计哈希表通常需要考虑四个点： 1. 用什么来作容器？（数组） 2. 如何设计哈希函数 3. 如何处理哈希冲突（链地址法：数组的每个位置都对应一个链表，哈希值相同的元素都被添加到同一链表中） 4. 容器满了需要进行扩容和 rehash **面试题常考利用哈希表的特性去设计更高级的数据结构**