Skip to main content
3 votes
Accepted

Efficient data structure for fast Insertions, lookups, and union operations on sets

Here are a few ideas: There are balanced binary search tree variants which are designed for efficient union/meld, such as weight-balanced trees. It's fairly well-established that the purpose of ...
Pseudonym's user avatar
  • 22.3k
3 votes
Accepted

Do edge lists have O(E) storage if default values are used for absent keys?

Just as an initial comment, it's not entirely settled what Bachmann big-oh notation formally means when you have more than one variable. There are multiple competing definitions. But let's leave that ...
Pseudonym's user avatar
  • 22.3k
2 votes

Time complexity of delete and insert operations in a hash table

Deleting is obvious, you need to find the element to delete, that's a lookup. but once you have the element you can delete it in O(1). Part of inserting an element into a hash table tends to include ...
ratchet freak's user avatar
1 vote
Accepted

Hash function for use with hash table, given power distributed integers

Use any standard hash function. It will work fine. You don't need a special hash function just for this distribution of data. An imbalanced distribution does not cause an increase in collisions. If ...
D.W.'s user avatar
  • 162k
1 vote
Accepted

Search times for hash tables using open addressing for collision resolution

If you have a table with space for 20,000 entries, and you store 19,990 keys then the load factor gets high. You’d expect it to go lower if you remove 15,000 keys, but because of your “deleted” ...
gnasher729's user avatar
  • 30.7k
1 vote

How to select hash functions for cuckoo hashing?

Great question, well, actually a family of questions :) Let's start with Cyckoo hashing. I checked the Wikipedia article to be sure, and indeed it doesn't mention any families. So, the answer is ...
Bulat's user avatar
  • 1,898
1 vote

Need help with adding elements to hashtable with linear probing

It is the hash function h(k) that determines the position. They don't specify the hash function, but instead they give the value to which h(k) evaluates for both tables. The hash function is usually a ...
Paul Schutte's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible