面试题：Java自定义类型作Hashtable key时哈希冲突处理及影响

Question

假设在Java中已使用自定义类型作为Hashtable的键，当发生哈希冲突时，Hashtable内部是如何处理的？这种处理方式对自定义类型的设计有哪些额外要求？如果不满足这些要求可能会出现什么问题？

Answer 1

哈希冲突处理方式

在Java的Hashtable中，当发生哈希冲突时，采用链地址法（拉链法）来处理。即每个哈希桶（数组的每个元素）是一个链表头节点。当不同的键计算出相同的哈希值（哈希冲突）时，这些键值对会被存储到同一个链表中。

自定义类型设计的额外要求

1. 重写hashCode方法：自定义类型必须重写hashCode方法，以确保相同的对象返回相同的哈希码，不同的对象尽量返回不同的哈希码，这样可以减少哈希冲突的概率。
2. 重写equals方法：必须重写equals方法，用于判断两个对象在逻辑上是否相等。在哈希表中，当通过哈希码定位到链表后，会使用equals方法来判断链表中的元素是否与要查找的键相等。

不满足要求可能出现的问题

1. 查找失败：如果没有正确重写hashCode方法，可能导致不同的对象产生相同的哈希码，使得哈希表在查找时无法准确找到目标元素，因为它依赖哈希码来定位桶位置。
2. 逻辑判断错误：若没有正确重写equals方法，在哈希表查找时，即使找到了哈希桶中的链表，也无法准确判断链表中的元素是否为目标元素，可能导致错误的判断，如本来应该相等的对象被认为不相等，从而在插入或查找操作中出现逻辑错误。