4 ms·

I'm unaware of any hash table implementations which successfully insert elements in absolute constant time in the event of collisions.

ot 16y ago
Chained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)
- pmjordan 16y ago
  Chaining requires a memory allocation and list insertion on collisions - is it fair to call that absolute constant time? Probability of this happening depends on the number of elements in the container.
  - silentbicycle 16y ago
    Pooling memory for allocating links turns the allocation into amortized constant time. List insertion is O(1) if you insert it at the head, and while moving the most-recently-accessed link to the head of the chain doesn't change the worst case behavior, it greatly improves the average in practice (and is dead easy).
  - ot 16y ago
    As silentbycicle said, list insertion at the head is constant time. About allocation, I agree with you that it is "slow", but all reasonable computation models count a memory allocation as a constant time operation. If we want to go down that road and measure also memory operations, even random memory access would not be worst-case constant time: the MMU has to map the page to the physical location, and this is usually a logarithmic or amortized constant time operation.
    - silentbicycle 16y ago
      Yeah, allocation is usually included in the constant factors. Keep them in mind, though - things like locality can have a big impact.
- ckuehne 16y ago
  You are kidding, right? The name chain itself suggest linear worst case behavior.
  - s3graham 16y ago
    "insertion".
    - ckuehne 16y ago
      My fault. Just saw constant time and chain in one sentence and panicked ;)
ckuehne 16y ago
Well, there is perfect hashing [1]. Of course it does only work under several assumptions. And you pay for it in terms of time it takes to construct the hash function or in terms of space. [1] http://en.wikipedia.org/wiki/Perfect_hash_function http://en.wikipedia.org/wiki/Perfect_hash_function

ot 16y ago

Chained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)

pmjordan 16y ago
Chaining requires a memory allocation and list insertion on collisions - is it fair to call that absolute constant time? Probability of this happening depends on the number of elements in the container.
- silentbicycle 16y ago
  Pooling memory for allocating links turns the allocation into amortized constant time. List insertion is O(1) if you insert it at the head, and while moving the most-recently-accessed link to the head of the chain doesn't change the worst case behavior, it greatly improves the average in practice (and is dead easy).
- ot 16y ago
  As silentbycicle said, list insertion at the head is constant time. About allocation, I agree with you that it is "slow", but all reasonable computation models count a memory allocation as a constant time operation. If we want to go down that road and measure also memory operations, even random memory access would not be worst-case constant time: the MMU has to map the page to the physical location, and this is usually a logarithmic or amortized constant time operation.
  - silentbicycle 16y ago
    Yeah, allocation is usually included in the constant factors. Keep them in mind, though - things like locality can have a big impact.
ckuehne 16y ago
You are kidding, right? The name chain itself suggest linear worst case behavior.
- s3graham 16y ago
  "insertion".
  - ckuehne 16y ago
    My fault. Just saw constant time and chain in one sentence and panicked ;)

ckuehne 16y ago

Well, there is perfect hashing [1]. Of course it does only work under several assumptions. And you pay for it in terms of time it takes to construct the hash function or in terms of space. [1] http://en.wikipedia.org/wiki/Perfect_hash_function http://en.wikipedia.org/wiki/Perfect_hash_function