python内建的dict（字典）类使用的是hash算法，因此它的key不是有序的。而C++中的std::map或std::set使用的是平衡二叉树（通常为红黑树），其key是有序的。在网上搜了搜，找到了一个用C和pyrex混合实现的红黑树模块，python-rbtree。 我编写了一个极简单的测试程序，在Solaris x86 + python 2.4.4平台上运行，分别使用dict和rbtree，插入两百万个记录（key是3个整型，value是1个整型，你大概猜到我在干什么了吧 ）。且在dict插入完…
哈希表又名散列表，其主要目的是用于解决数据的快速定位问题。考虑如下一个场景。 一列键值对数据，存储在一个table中，如何通过数据的关键字快速查找相应值呢？不要告诉我一个个拿出来比较key啊，呵呵。 大家都知道，在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 …