Question

如何提高list查找效率，10万数据用一个list存，查询快，还是用多个list存，查询快

c++用list实现hashmap 功能，key 和value均为string ,查询10万数据，如何提速

Answer 1

如果数据无序，那种方法都不快，最好就是顺序查

如果是ArrayList且有序 ，最好是折半查找

如果是想分多个list，那么保证段间有序是一种不错的办法
最好的情况是分sqrt(100000)个list，每个的数据是sqrt(100000)个，段间有序，段内随便，用分块查找速度还不错

如果只是用一个list，而且是LinkedList，那么没有好办法，就是直接查，有序也不行

追问

c++用list实现hashmap 功能，key 和value均为string ,查询10万数据，如何提速

追答

hashmap 查询效率仅与装填因子有关（在冲突解决方法确定的情况下）

冲突解决方法一般选取“平方探索法”或“拉链法”较好，最好不要使用“线性探索法”

装填因子小于0.5吧，越小越好，但是会占用很多存储空间

追问

c++有3个不同的list， 用多线程，每个线程查询一个list，查到需要的值就返回，怎么编写，在线等！

追答

多线程不能提高查询效率，没必要的

追问

将一个list，拆成3个，多线程分别同时查这三个，查到退出，难道不比只查这三个合成的大list快吗？

追答

在数据无序的情况下，不会快的

由于调度线程需要时间，甚至还会慢一下

多线程不能提高效率，多核并行计算可以，但是很复杂

Answer 2

如果用唯一标示来访问，则是用hashMap最快。如果需要遍历，或者根据某一个数据进行查找，则排序过后的list查找比较快