New answers tagged hash-tables
0
votes
What is a good load factor for seperate chaining (closed addressing)?
According to this Python does a rehashing when the load factor reaches $2/3$.
0
votes
Averege time complexity of open addressing
Implementations will typically store the hash value inside the table - this will save lots of hash value calculations.
For the hash value of the key being looked up, it depends on the caller how often ...
1
vote
Accepted
Averege time complexity of open addressing
Define the load factor of a hash table with open addressing to be $n/m$, where $n$ is the number of elements in the hash table and $m$ is the number of slots. It can be shown that the expected time ...
2
votes
Accepted
Consistent Hashing Algorithm Without Distribution / Load Balancing
The below is with 0-based indexing for the buckets.
We assume we have some hash function $h(k) \rightarrow [0,1)$.
When looking up $k$ check the last node (index $N-1$) and the node $\lfloor Nh(k) \...
Top 50 recent answers are included
Related Tags
hash-tables × 255data-structures × 106
hash × 88
algorithms × 46
hashing × 38
algorithm-analysis × 29
time-complexity × 23
probability-theory × 16
terminology × 8
arrays × 8
asymptotics × 7
runtime-analysis × 7
distributed-systems × 7
dictionaries × 7
complexity-theory × 6
search-trees × 6
probabilistic-algorithms × 6
strings × 5
sets × 5
binary-trees × 4
space-complexity × 4
randomized-algorithms × 4
efficiency × 4
bloom-filters × 4
optimization × 3