跳转至

哈希和映射

算法速度

大O表示法：

哈希：O(1) > 二叉树：O(logN) > 线性查找：O(N) > 冒泡排序：O(N^2)

1、线性映射

vector动态数组，数组里面保存一对一对的数据（键值）。

数组只能线性查找，100万个数平均要找50万次。数据越多，查找次数就会越多。

这是线性数组的缺点，所以不用，只是为了学习使用。

2、二叉树（红黑树）映射tree_map

#include <map>//映射（也叫字典），系统做好的二叉树映射，速度比线性映射快。

void test()
{
    //二叉树（红黑树）映射
    //保存每个学生的成绩
    map<string, int> m;//m是二叉树映射
    m["Bill"] = 98;
    m["Tom"] = 67;
    m["Mary"] = 100;
    //...继续保存，保存了很多，100万个
    cout << m["Tom"] << endl;
}

一对一对的就叫映射，Bill是98 Tom是67 Mary是100。

二叉树查找是向左向右根据大小查找，100万个数据找20次就找完了。10亿个数据找30次。

比二叉树查找更快的是哈希，哈希可以一下子就找到。更快。

3、哈希映射HashMap

哈希也叫散列，在所有数据结构中，哈希映射：用的最多的，因为速度最快。

原理：

存的时候：把key通过哈希函数变成下标，然后放到数组里。

取的时候：根据key通过哈希函数找到这个数组的下标，计算位置拿数据，检查key是不是要找的，是的话就返回找到所找的值，不是就返回Value默认值。

放的时候用了哈希放进去，取的时候又用了哈希取出来。只要设计的哈希函数的速度非常快，哈希就会很快。

哈希函数（位置的映射）

  1. 把key转型成字符。对里面的每一个字符都用它的ASCII码。
  2. 变成哈希值之后，哈希值可能会很大，数组容量没那么大，可以用哈希值除以容量取余数，这样就比较小了。

哈希值对哈希表的数组长度进行求模运算。

或者：

index = hash & (length-1)

哈希表的长度是2的整数次方（0、1、2、4、8、16、32、64、...），减1之后的二进制均变成了1，比如长度16，减1变成15，也就是二进制1111。再进行与运算，相当于去了哈希值的地位，直接映射到对应的数组位置，与运算比取模运算要快不少。

C++国际标准没有哈希映射，因为出来的比较晚，哈希映射<hash_map>是微软做的。

哈希

  • 优点

速度快，速度是恒定的。速度和数据多少没关系，利用下标进行操作。

  • 缺点

不能排序。每次哈希都变成一个下标，像随机的，所以不能排序。

不需要排序的时候使用哈希映射hash_map。如果既要哈希又要排序，可以使用二叉树映射tree_map，二叉树映射是排序的，小的在左边大的在右边。

哈希除了可以做映射map，还可以做哈希集set。

哈希冲突

取得的下标一样时，相同下标的数据对应的一个链表。如果链表数据多时，使用树，加快查找速度。