4 ms·

I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and th

I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.

19870213 8y ago
The standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?
- mikeash 8y ago
  You could, but it’s theoretically possible to have keys whose hashes always collide, even with different hash functions. This is not a purely theoretical concern, I should note. There are practical DoS attacks that can be carried out by deliberately crafting colliding keys. The current state of the art seems to be to make it impractical for attackers to accomplish this by incorporating secret data into the hash function, rather than by ensuring the theoretical worst case is acceptable. Which is probably the right approach.
- rurban 8y ago
  My limit is 128. 5 is very common with a high load factor and fast hash function.
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.

19870213 8y ago

The standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?

mikeash 8y ago
You could, but it’s theoretically possible to have keys whose hashes always collide, even with different hash functions. This is not a purely theoretical concern, I should note. There are practical DoS attacks that can be carried out by deliberately crafting colliding keys. The current state of the art seems to be to make it impractical for attackers to accomplish this by incorporating secret data into the hash function, rather than by ensuring the theoretical worst case is acceptable. Which is probably the right approach.
rurban 8y ago
My limit is 128. 5 is very common with a high load factor and fast hash function.

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.