作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] 用red-black tree解hash的collision
时间Thu Dec 29 22:45:17 2011
Assume that we have a hash table with collisions resolved by chaining.
Attempting to improve the performance of this implementation, we use a
red-black tree for each slot instead of an unsorted linked list,
resulting in a hash table with collisions resolved "by red-black trees".
Assume that a simple uniform hashing function is utilized and the load factor
of the hash table is α. What is the running time for unsuccessful searches
and insertions for our new implementation, respectively?
这是100台大资工所的题目
我自己的想法是都是O(lgn) 可是感觉没那麽简单..是不是要用到α?
请问有人对这题有什麽想法吗?
谢谢!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.118.110.186
※ 编辑: mqazz1 来自: 140.118.110.186 (12/29 22:47)