想不明白hash查找为什么快？？hash函数不也要时间吗
对比map和hash_map, 查找：
map对数时间。在查找的时候做的是工作应该是对比和迭代。百万数据也才几次的对比，也就是才10几次的运算。
hash_map接近常数时间？？在查找时做的工作应该是求出下标值，但我发现很多hash函数在求下标的时候做的工作挺多的
啊！！加减乘除移位赋值，有时还得解决冲突。。。这么看的话很怀疑在hash还没求出下标值map就已经找到的。
不知道以上想法有什么错的求解啊！！
[解决办法]
/*
These functions are based on Peter J. Weinberger's hash function
(from the Dragon Book). The constant 24 in the original function
was replaced with 23 to produce fewer collisions on input such as
"a", "aa", "aaa", "aaaa", ...
*/
static uint hash(const uchar *p, int n)
{
uint h = 0;
uint g;
while (n--) {
h = (h << 4) + *p++;
if ((g = (h & 0xf0000000)) != 0)
h ^= g >> 23;
h &= ~g;
}
return h;
}
以上是一个hash函数，hash函数本身的复杂度是o(n)的，比如计算string a的hash值，复杂度和比较string a == b差不多，加减乘除对计算机来说还是很快的，想想指令系统里的那些指令，hash函数的冲突概率还是很小的(与hash函数设计有关)。
[解决办法]
hash_map的查找，时间不随数据规模扩大而变化。
而map的查找，会随着时间复杂度增长越来越慢。另外要考虑map的key是什么形式的，比较key的复杂度如何。
当然是有个临界值的，例如100个数据，或许map快，1亿的数据，hash_map的优势就显示出来了。
从计算机结构上看，hash_map平均可以一次计算（虽然计算指令较多，但是都在cpu）到内存地址。而map需要不停地提取不同位置的节点进行比较（假设内存比较分散，节点没有在缓存里），那么取一次内存至少也要几百的cpu周期。取多了速度自然就慢了。
