跳转至

哈希和映射

算法速度

大O表示法：

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

1、线性映射

只是为了学习使用

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

  • 两个size大小
  • 限定的最大的容量
  • 实际的大小
  • put 往数组里放数据
  • get 取数据 从数组里取出来 找到了就返回value，没找到就返回Value的0值。

数组只能线性查找，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默认值。

不同的key都通过哈希函数变成下标，有了数组的下标，就可以通过数组下标快速的找到。

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

哈希函数：

哈希也叫散列。

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

这是自己写的哈希映射，实际应用时可以使用C++做好的哈希映射，C++国际标准没有哈希映射。因为出来的比较晚。哈希映射是微软做的。

放进入数据多少和读数据取数据没什么影响。直接使用哈希，利用下标进行操作。

哈希

  • 优点

速度快。不会因数据多少而影响，速度是恒定的。速度和数据多少没关系。

  • 缺点

不能排序。每次哈希都变成一个下标，把很多数据放到哈希里，看起来像随机的，所以不能排序。

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

不需要排序的时候使用哈希映射hash_map，需要排序的时候使用二叉树映射tree_map。使用的时候根据不同的特点选择不同的数据结构。

二叉树映射也很快O(logN)，只是比哈希映射慢一点，哈希映射O(1)。

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

哈希冲突

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