Posted by & filed under Uncategorized.

About HuangWencong

Wencong Huang has written 8 post in this blog.

map的定义:Map提供一对一<key,value>的数据处理能力,在我们处理一对一数据的时候,在编程上提供快速通道。

实现关键:快速查找的问题,即根据所给的key,在内存中找到其对应的value.

在具体讨论前引入查找速度的评价指标:渐进时间复杂度,表示为O();

由于程序的具体执行时间难以准确估计,引入渐进时间复杂度这个概念,如下面的程序:

for(int i=0;i<N;i++)

{

a++;b++;

}c++;

程序主要部分一共执行了2*N+1次,取其幂,得起渐进时间复杂度为O(N);

同理,以下程序

for(int i=0;i<N;i++)

for(int j=0;j<N;j++)

a++;

主要部分执行了N*N次,渐进时间复杂度就为O(N^2);

渐进时间复杂度的大小比较为:

O(1)<O(logN)<O(N)<O(N*logN)<O(N^2)<O(N^3);

接着我们来讨论快速查找的几个算法:

1)我们首先用数组来存储map,接着讨论如何在数组的前提下进行查找:

1。数组为无序的,我们最直观的方法便是一个个查看过去,确认是否是我们要找的东西,不是则查看下一个,是则结束查找。

渐进时间复杂度为O(N);

2。数组为有序的,可以有二分查找,斐波那契查找等,其基本的思想是相同的,我们以二分查找为例,每次对比数组的中位数,查找数大于中位数,则在后一半数组中继续,否则在前一半查找,直到数组大小为1时,判断是否为所要找的元素。

渐进时间复杂度可以估算为O(logN);<O(N);

不过这里假设的前提是数组有序,而最快的排序快速排序法的时间复杂度为O(N*logN)〉O(N);所以如果在一个无序的数组里先排序,再二分的话,速度还不如直接查找。

2。hash表,也叫散列表

hash数组即以一个hash函数,为每个value计算一个唯一的地址值,查找只要通过计算hash函数,就能直接找到所在地址。

一个简单的hash数组如下:

<key,value><3,value1><6,value2><9,value3><12,value4>

观察到每个key都是3的倍数,而且没有重复,我们定义一个hash函数f

int f(int key)

{

return key/3;

}

然后根据返回值,放在数组相应的1,2,3,4位置。

但是,像这种正好的情况是几乎不可能的,不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该hash来说称做同义词。

处理冲突有如下几种方法:

1. 开放寻址法:
2. 再散列法:
3. 链地址法(拉链法)
4. 建立一个公共溢出区

这里不做深入探讨。

 

hash表提供了一个渐进时间复杂度为O(1)的查找速度,查找的主要开销在hash函数的运算上面。不过好的hash函数是少之又少的,比较著名的有如下几个:

MD5 ,SHA—1等;这几个函数也作为数字签名,报文鉴别码,有广泛的运用。
但是如果作为自定义的map数据结构,引入MD5 等哈西函数,有杀鸡用牛刀的感觉,个人觉得在小数据的情况下,用MD5开销估计要多于查找所省去 的时间。

2)上面讨论了数组为结构进行快速查找的方法,但是我们忽略了存储空间,以及动态更新的开销。数组要预先定义,并且动态更新太麻烦。于是我们引入一个可以动态更新的数据结构,链表;

 

1。基于链表的直接查找

跟数组类似,我们从头到尾查看一遍,时间复杂度为O(N);

 

2。二叉搜索树

二叉搜索树是用二叉树来模拟数组二分查找的数据结构,其搜索,插入,删除的时间复杂度均为O(logN);
不过二叉搜索树会带来一个退化树,即左右子树不一样长,导致性能下降,我们又引入为防止退化树 的数据类型,平衡二叉树AVL 树

 

3。平衡二叉搜索树AVL

平衡二叉树通过有限步的操作,来保证左右子树高度差<=1,保证二叉树搜索的性能

 

4。红黑树AVL-

红黑树AVL-,是一种自平衡二叉查找树。
每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

 

性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 .每个叶节点是黑色的。
性质4 .每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。

操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,
它的统计性能要好于平衡二叉树。
大家有兴趣可以深入了解红黑树的具体实现
C++ 的STL 库就是运用红黑树来进行map操作。

One Response to “关于map”

  1. Sakya

    内容还可以,有一定深入性,但是文章标题不直观,建议博客标题能够说明文章的核心内容或者问题,另外格式上有些乱,这么多序号看不出明显的层次关系,给读者制造障碍。

    Reply

Leave a Reply

  • (will not be published)