我是否必须散列整个密钥才能平均节省 O(1) 的时间复杂度？
Do I have to hash the entire key in order to save time-complexity of O(1) on average?
假设我有散列 table 和一个均匀分布的散列函数，并且它使用链表的单独链接。
table中保存的key是一对(a,b)（不限数），我按照hash(a)插入到table中（忽略b).
操作 find、insert 和 delete 是否平均仍在 O(1) 时间内？或者我必须散列整个密钥，包括 b?
不，这不能保证您预期的 O(1) 查找。例如，假设您散列 (0, 0), (0, 1), (0, 2), (0, 3), ..., (0, n-1)。所有 n 个这些值都将散列到 table 中的相同位置（因为第二个组件被忽略），因此无论散列函数如何对第一个组件 (0) 进行散列，您最终都会得到 n 个元素哈希中的相同位置 table，使您的查找在最坏的情况下退化为花费时间 Θ(n)。
一般来说，使用散列table时需要对整个密钥进行散列。否则，通过保持密钥的一部分不变并更改其他部分，很容易导致散列冲突。
如果您使用 (a, b) 作为键，但仅基于 hash(a) 进行存储，那么只要您有多个具有相同值 a 的对象，就会发生冲突。比如(1, 2)和(1, 3)都会hash到同一个bucket，所以要遍历链表。对性能的实际影响取决于您的数据集，但平均而言，您将 not 仍然具有 O(1) 性能。
关于a和b，你事先知道什么吗？如果不是，则需要对两者进行哈希处理。如果您知道它们都是相当随机的，那么单独基于一个的散列应该足够好，尽管散列 2 个整数的计算量不应该比单个整数多。
假设我有散列 table 和一个均匀分布的散列函数，并且它使用链表的单独链接。
table中保存的key是一对(a,b)（不限数），我按照hash(a)插入到table中（忽略b).
操作 find、insert 和 delete 是否平均仍在 O(1) 时间内？或者我必须散列整个密钥，包括 b?
不，这不能保证您预期的 O(1) 查找。例如，假设您散列 (0, 0), (0, 1), (0, 2), (0, 3), ..., (0, n-1)。所有 n 个这些值都将散列到 table 中的相同位置（因为第二个组件被忽略），因此无论散列函数如何对第一个组件 (0) 进行散列，您最终都会得到 n 个元素哈希中的相同位置 table，使您的查找在最坏的情况下退化为花费时间 Θ(n)。
一般来说，使用散列table时需要对整个密钥进行散列。否则，通过保持密钥的一部分不变并更改其他部分，很容易导致散列冲突。
如果您使用 (a, b) 作为键，但仅基于 hash(a) 进行存储，那么只要您有多个具有相同值 a 的对象，就会发生冲突。比如(1, 2)和(1, 3)都会hash到同一个bucket，所以要遍历链表。对性能的实际影响取决于您的数据集，但平均而言，您将 not 仍然具有 O(1) 性能。
关于a和b，你事先知道什么吗？如果不是，则需要对两者进行哈希处理。如果您知道它们都是相当随机的，那么单独基于一个的散列应该足够好，尽管散列 2 个整数的计算量不应该比单个整数多。