Next: 3.8 Skip Lists
Up: 3. Dictionaries
Previous: 3.6.4 Result 4: Deletion
- When a hash table has a large number of entries (ie., let us say n
2m in open hash table or
0.9m in closed hash table), the average
time for operations can become quite substantial. In such cases, one idea is
to simply create a new hash table with more number of buckets (say twice or any
appropriate large number).
- In such a case, the currently existing elements will have to be inserted
into the new table. This may call for
This effort will be less than it took to insert them into the original table.
- rehashing of all these key values
- transferring all the records
- Subsequent dictionary operations will be more efficient and can more than
make up for the overhead in creating the larger table.