hashmap(C++扩展库)上限问题导致程序崩溃
老蔡最近在编游戏方面的程序,因为map的插入和查找的时间复杂度比hashmap的大,所以为了优化游戏引擎,将map都改成了hashmap,用空间上扩大开销换取时间上的节省。但却碰到了二维hashmap插入过多数据后程序崩溃的问题。
话说这个测试程序要跑3-4个小时才崩溃,要知道C++奔跑起来的效率是很高的,三个多小时前的数据测试完全没有问题,说明hashmap一定程度上是比较可靠的。而数据插入到大约7103824条左右,hashmap的线性表就崩了。报错:list insert iterator outside range(之前是不报错的,要加入一个DEBUG宏)。看了一下hashmap的源码,发现问题所在:它将元素的hash值存入了一个线性表List,用来节省查找所需的时间,而它的List的类型又是int,导致这个int溢出后,线性表就无法插入数据了,于是写入不了数据,导致程序崩溃。(最后发现,是自己的32位系统一个进程内存超过了限制。。。) 算了一下帐,map利用红黑树排序,时间复杂度也就只有O(Log2N),也不是太多,而stl应该更加安全吧。毕竟是C++发家的家伙,用的人也不计其数,所以换回了std::map,继续测试。