Hashtable 哈希表原理与哈希算法对比

Hash 表也称散列表，也有直接译作哈希表，是一种特殊的数据结构，同数组、链表以及二叉排序树等相比较有很明显的区别：它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这源于 Hash 表设计的特殊性，它采用函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。

java.util.Hashtable 是 Java 中最早的哈希表实现，自 JDK 1.0（1996 年）就已存在。在现代 Java 中它依然保留，但仅用于向后兼容旧代码：非线程安全场景推荐使用 HashMap，需要线程安全时推荐使用 ConcurrentHashMap，两者性能和易用性都更好，Hashtable 已不建议在新代码中使用。

Hash 表的设计思想

对于一般的线性表，比如链表，如果要存储联系人信息：

张三 13980593357
李四 15828662334
王五 13409821234
张帅 13890583472

可能会设计一个结构体包含姓名、手机号码这些信息，然后把 4 个联系人的信息存到一张链表中。当要查找“李四 15828662334”这条记录是否在这张链表中，或者想要得到李四的手机号码时，可能会从链表的头结点开始遍历，依次将每个结点中的姓名同“李四”进行比较，直到查找成功或者失败为止，这种做法的时间复杂度为 O(n)。即使采用二叉排序树进行存储，也最多为 O(logn)。假设能够通过“李四”这个信息直接获取到该记录在表中的存储位置，就能省掉中间关键字比较的这个环节，复杂度直接降到 O(1)。Hash 表就能够达到这样的效果。

Hash 表采用一个映射函数 f : key -> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置。通常情况下，这种映射关系称作 Hash 函数，而通过 Hash 函数和关键字计算出来的存储位置（注意这里的存储位置只是表中的存储位置，并不是实际的物理地址）称作 Hash 地址。比如上述例子中，假如联系人信息采用 Hash 表存储，则当想要找到“李四”的信息时，直接根据“李四”和 Hash 函数计算出 Hash 地址即可。

hashCode 与 equals 的关系

有人会说，可以直接根据 hashCode 值判断两个对象是否相等吗？肯定是不可以的，因为不同的对象可能会生成相同的 hashCode 值。虽然不能根据 hashCode 值判断两个对象是否相等，但是可以直接根据 hashCode 值判断两个对象不等——如果两个对象的 hashCode 值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过 equals 方法。

也就是说，对于两个对象：

• 如果调用 equals 方法得到的结果为 true，则两个对象的 hashCode 值必定相等
• 如果 equals 方法得到的结果为 false，则两个对象的 hashCode 值不一定不同
• 如果两个对象的 hashCode 值不等，则 equals 方法得到的结果必定为 false
• 如果两个对象的 hashCode 值相等，则 equals 方法得到的结果未知

哈希表的优点与局限

哈希表可以提供快速的插入操作和查找操作。不论哈希表中有多少数据，插入和删除（有时包括查找）只需要接近常量的时间，即 O(1) 的时间级，实际上只需要几条机器指令。

哈希表运算得非常快，在计算机程序中，如果需要在一秒钟内查找上千条记录，通常使用哈希表（例如拼写检查器），速度明显比树快——树的操作通常需要 O(N) 的时间级。哈希表不仅速度快，编程实现也相对容易。

哈希表也有一些缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

而且，也没有一种简便的方法可以按任何一种顺序（例如从小到大）遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。

然而，如果不需要有序遍历数据，并且可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。

哈希算法对比

哈希洪水攻击

哈希洪水攻击（hash flooding）指攻击者故意构造大量具有相同哈希值的字符串：

• 导致哈希表退化成链表，性能从 O(1) 降到 O(n)
• 可能让服务器因为处理这些数据而变慢甚至崩溃

维护记录