4 ms·

It's constant-time lookup (only two possible places to check). But if you give it the "return 4" hash function, it will fail to insert after the second or third

by cbhl 8y ago

It's constant-time lookup (only two possible places to check). But if you give it the "return 4" hash function, it will fail to insert after the second or third entry. The result is the same, you have to fall back to something (changing the hash function; making the table larger; open addressing with chaining; etc.)

mikeash 8y ago
That’s boring. Any algorithm can be constant time if you’re allowed to fail after a constant amount of work.
- jolux 8y ago
  It will rebuild the hashtable when that happens. As long as the load factor remains below 50%, (for the most basic implementation) insertions will remain constant anyways. You don't need to allocate new tables.
  - mikeash 8y ago
    How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.
    - jolux 8y ago
      Have you read about how the algorithm works?
      - mikeash 8y ago
        A bit. When you collide in both tables, you switch to a different hash function and try again. With real-world data, that should work great. But with pathological data (i.e. the worst case behavior) that will never succeed.
- cbhl 8y ago
  If you phrase the problem as "design a better hash table, given the hash function h(x) = 4", then the obvious first thing to do is discard the provided hash function, and use any reasonable hash table implementation with a new hash function, say h'(x) = x. (If x "is an object" instead of a primitive type; then some underlying representation of x in a register is a pointer; that memory address can typically be converted to an integer that can be the hash value.) Thus, I would argue that the problem reduces to the case where you have a reasonable hash function.

by cbhl 8y ago

mikeash 8y ago

That’s boring. Any algorithm can be constant time if you’re allowed to fail after a constant amount of work.

jolux 8y ago
It will rebuild the hashtable when that happens. As long as the load factor remains below 50%, (for the most basic implementation) insertions will remain constant anyways. You don't need to allocate new tables.
- mikeash 8y ago
  How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.
  - jolux 8y ago
    Have you read about how the algorithm works?
    - mikeash 8y ago
      A bit. When you collide in both tables, you switch to a different hash function and try again. With real-world data, that should work great. But with pathological data (i.e. the worst case behavior) that will never succeed.
cbhl 8y ago
If you phrase the problem as "design a better hash table, given the hash function h(x) = 4", then the obvious first thing to do is discard the provided hash function, and use any reasonable hash table implementation with a new hash function, say h'(x) = x. (If x "is an object" instead of a primitive type; then some underlying representation of x in a register is a pointer; that memory address can typically be converted to an integer that can be the hash value.) Thus, I would argue that the problem reduces to the case where you have a reasonable hash function.