发现红黑树的速度还是没有hashtable的快

liexusong

因为PHP的数组是用HashTable写的, 所以我就写了一个用红黑树的结构扩展, 结果运行一看, 查询速度差不多, 但是插入的速度明显慢了很多, 唯一的好处就是内存使用比较少~

hellioncu

也不能一概而论，总能举出反例的

ecjtubaowp

有详细的测试吗？

liexusong

回复 3# ecjtubaowp


    有, 10万数据插入, HashTable需要0.2, 红黑树要0.5

搜索元素HashTable和红黑树都差不多是0.0002左右, 不过红黑树有时候会变化, HashTable基本上不会变~

另外我看过PHP的HashTable, 他还有resize的操作, 所以我觉得resize的消耗可以忽略不计的~

egmkang

红黑树是log(n)的时间复杂度,HashTable是O(1).

liexusong

回复 5# egmkang


    但是HashTable有碰撞啊~ 所以也不是O(1)的~

另外, 红黑树是按算法导论实现的, 所以应该还是可以的

egmkang

回复  egmkang


    但是HashTable有碰撞啊~ 所以也不是O(1)的~

另外, 红黑树是按算法导论实现的,  ...
liexusong 发表于 2011-03-25 16:46

HashTable的优势在于快速查找,通过好的HashCode算法,可以快速的找到那个节点.

雨夜流星

很正常啊，哈希的插入和查找过程差不多，不需要额外的操作，
但是rbtree插入时，需要进行旋转，慢一点是可以理解的

10万的数据，rbtree的比较最坏情况在14次左右，但是哈希最坏情况下，估计也不会超过10吧？

liexusong

嗯, 所以内存足的时候, HashTable是最好用的, 算法简单而且快

wb112200

树插入元素 有个遍历的过程...