3 ms·

It depends entirely on what you need to guarantee. Using a hash tabel you guarantee with a very high probability that you only remove duplicated elements. If yo

• wruza 8y ago
  Hash tables don’t work in a way that you assume here. Original keys don’t get lost, so you can check whether a key is actually in the table or just makes a collision. In its simplest case, HT is an array1 of array2s of key-value pairs, where array1 is indexed via [hash(key) % a1.length] and then array2 (aka bucket) is searched linearly for a given key by comparing contents.
  • hvidgaard 8y ago
    A hash table does not need to have a collision resolution strategy. It's only definition is key/value pair. That you can have buckets function to avoid collisions is "extra" so to speak. C# linq .Distinct() does not do that, it only checks on the key.
    • masklinn 8y ago
      > A hash table does not need to have a collision resolution strategy. A hash table absolutely needs a collision resolution strategy, the collision in question being different keys having the same hash. > C# linq .Distinct() does not do that, it only checks on the key. …? There's nothing other than a key, Distinct stores items from the source iterator into a set.
    • wruza 8y ago
      A hash table is a well-known term that covers multiple algorithms, but I never seen one that worked the way you describe. False positive lookups is a property of bloom filter-like struct, not of a hash table. Using false positives to remove duplicates would be wrong indeed. Ed: I missed “It's only definition is key/value pair” part. No, that’s called key-value list or table. Hash table uses hashes of keys to partition itself into quick lookup segments - that’s the point.