17611538698
webmaster@21cto.com

常用数据结构及复杂度

资讯 0 28539 2017-04-27 12:01:12
[h1]常用数据结构的时间复杂度[/h1]





Data Structure



Add



Find



Delete



GetByIndex











 Array (T[])

O(n)






O(n)






O(n)






O(1)










 Linked list (LinkedList<T>)

O(1)






O(n)






O(n)






O(n)










 Resizable array list (List<T>)

O(1)






O(n)






O(n)






O(1)










 Stack (Stack<T>)

O(1)






-






O(1)






-










 Queue (Queue<T>)

O(1)






-






O(1)






-










 Hash table (Dictionary<K,T>)

O(1)






O(1)






O(1)






-











 Tree-based dictionary

 (SortedDictionary<K,T>)






  O(log n)  






  O(log n)  






  O(log n)  






-











 Hash table based set

 (HashSet<T>)




O(1)






O(1)






O(1)






-











 Tree based set

 (SortedSet<T>)




O(log n)






O(log n)






O(log n)






-





















[h1]如何选择数据结构[/h1]
Array (T[])

  • [list]当元素的数量是固定的,并且需要使用下标时。





[/list]
Linked list (LinkedList<T>)

  • [list]当元素需要能够在列表的两端添加时。否则使用 List<T>。





[/list]
Resizable array list (List<T>)

  • [list]当元素的数量不是固定的,并且需要使用下标时。





[/list]
Stack (Stack<T>)

  • [list]当需要实现 LIFO(Last In First Out)时。





[/list]
Queue (Queue<T>)

  • [list]当需要实现 FIFO(First In First Out)时。





[/list]
Hash table (Dictionary<K,T>)

  • [list]当需要使用键值对(Key-Value)来快速添加和查找,并且元素没有特定的顺序时。





[/list]
Tree-based dictionary (SortedDictionary<K,T>)

  • [list]当需要使用价值对(Key-Value)来快速添加和查找,并且元素根据 Key 来排序时。





[/list]
Hash table based set (HashSet<T>)

  • [list]当需要保存一组唯一的值,并且元素没有特定顺序时。





[/list]
Tree based set (SortedSet<T>)

  • [list]当需要保存一组唯一的值,并且元素需要排序时。





[/list]
时间复杂度为 O(1),因此对数组的访问时间是恒定的。也就是说,与数组中包含的元素数量没有直接关系,访问一个元素的时间是相同的。

[b]

1 List<int> powersOf2 = new List<int>();
2
3 powersOf2.Add(1);
4 powersOf2.Add(2);
5
6 powersOf2[1] = 10;
7
8 int sum = powersOf2[1] + powersOf2[2];


List<T> 的渐进运行时(Asymptotic Running Time)复杂度与 Array 是相同的。

[b]LinkedList<T> 类,该类实现了双向链表(doubly-linked list)功能,也就是节点同时持有其左右节点的引用。而对于删除操作,如果使用 Remove(T),则运算复杂度为 O(n),其中 n 为链表的长度。而如果使用 Remove(LinkedListNode<T>), 则运算复杂度为 O(1)。

[b]复杂度为 O(1)。如果容量需要被扩展,则 Push 操作的复杂度变为 O(n)。Pop 操作的复杂度始终为 O(1)。

[b]查询渐进时间降低到 O(log(n))。但理想情况下,我们更希望查询渐进时间为 O(1)。

一种方案是建立一个大数组,范围从 000-00-0000 到 999-99-9999 。




这种方案的缺点是浪费空间。如果我们仅需要存储 1000 个员工的信息,那么仅利用了 0.0001% 的空间。

第二种方案就是用[b]哈希函数(Hash Function)
压缩序列。

我们选择使用社保号的后四位作为索引,以减少区间的跨度。这样范围将从 0000 到 9999。




在数学上,将这种从 9 位数转换为 4 位数的方式称为哈希转换(Hashing)。可以将一个数组的索引空间(indexers space)压缩至相应的哈希表(Hash Table)。

在上面的例子中,哈希函数的输入为 9 位数的社保号,输出结果为后 4 位。


H(x) = last four digits of x




上图中也说明在哈希函数计算中常见的一种行为:哈希冲突(Hash Collisions)。即有可能两个社保号的后 4 位均为 0000。

当要添加新元素到 Hashtable 中时,哈希冲突是导致操作被破坏的一个因素。如果没有冲突发生,则元素被成功插入。如果发生了冲突,则需要判断冲突的原因。因此,哈希冲突提高了操作的代价,Hashtable 的设计目标就是要尽可能减低冲突的发生

处理哈希冲突的方式有两种:避免和解决,即冲突避免机制(Collision Avoidance)和冲突解决机制(Collision Resolution)。

避免哈希冲突的一个方法就是选择合适的哈希函数。哈希函数中的冲突发生的几率与数据的分布有关。例如,如果社保号的后 4 位是随即分布的,则使用后 4 位数字比较合适。但如果后 4 位是以员工的出生年份来分配的,则显然出生年份不是均匀分布的,则选择后 4 位会造成大量的冲突。我们将这种选择合适的哈希函数的方法称为冲突避免机制(Collision Avoidance)。

在处理冲突时,有很多策略可以实施,这些策略称为冲突解决机制(Collision Resolution)。其中一种方法就是将要插入的元素放到另外一个块空间中,因为相同的哈希位置已经被占用。

通常采用的冲突解决策略为开放寻址法(Open Addressing),所有的元素仍然都存放在哈希表内的数组中。

开放寻址法的最简单的一种实现就是线性探查(Linear Probing),步骤如下:

  1. 当插入新的元素时,使用哈希函数在哈希表中定位元素位置;
  2. 检查哈希表中该位置是否已经存在元素。如果该位置内容为空,则插入并返回,否则转向步骤 3。
  3. 如果该位置为 i,则检查 i+1 是否为空,如果已被占用,则检查 i+2,依此类推,直到找到一个内容为空的位置。

现在如果我们要将五个员工的信息插入到哈希表中:

  • Alice (333-33-1234)
  • Bob (444-44-1234)
  • Cal (555-55-1237)
  • Danny (000-00-1235)
  • Edward (111-00-1235)

则插入后的哈希表可能如下:




元素的插入过程:

  • Alice 的社保号被哈希为 1234,因此存放在位置 1234。
  • Bob 的社保号被哈希为 1234,但由于位置 1234 处已经存放 Alice 的信息,则检查下一个位置 1235,1235 为空,则 Bob 的信息就被放到 1235。
  • Cal 的社保号被哈希为 1237,1237 位置为空,所以 Cal 就放到 1237 处。
  • Danny 的社保号被哈希为 1235,1235 已被占用,则检查 1236 位置是否为空,1236 为空,所以 Danny 就被放到 1236。
  • Edward 的社保号被哈希为 1235,1235 已被占用,检查1236,也被占用,再检查1237,直到检查到 1238时,该位置为空,于是 Edward 被放到了1238 位置。

线性探查(Linear Probing)方式虽然简单,但并不是解决冲突的最好的策略,因为它会导致同类哈希的聚集(Primary Clustering)。这导致搜索哈希表时,冲突依然存在。例如上面例子中的哈希表,如果我们要访问 Edward 的信息,因为 Edward 的社保号 111-00-1235 哈希为 1235,然而我们在 1235 位置找到的是 Bob,所以再搜索 1236,找到的却是 Danny,以此类推直到找到 Edward。

一种改进的方式为二次探查(Quadratic Probing),即每次检查位置空间的步长为平方倍数。也就是说,如果位置 s 被占用,则首先检查 s + 12 处,然后检查s - 12,s + 22,s - 22,s + 32 依此类推,而不是象线性探查那样以 s + 1,s + 2 ... 方式增长。尽管如此,二次探查同样也会导致同类哈希聚集问题(Secondary Clustering)。

.NET 中的 Hashtable 类的实现,要求添加元素时不仅要提供元素(Item),还要为该元素提供一个键(Key)。例如,Key 为员工社保号,Item 为员工信息对象。可以通过 Key 作为索引来查找 Item。



1 Hashtable employees = new Hashtable();
2
3 // Add some values to the Hashtable, indexed by a string key
4 employees.Add("111-22-3333", "Scott");
5 employees.Add("222-33-4444", "Sam");
6 employees.Add("333-44-55555", "Jisun");
7
8 // Access a particular key
9 if (employees.ContainsKey("111-22-3333"))
10 {
11 string empName = (string)employees["111-22-3333"];
12 Console.WriteLine("Employee 111-22-3333's name is: " + empName);
13 }
14 else
15 Console.WriteLine("Employee 111-22-3333 is not in the hash table...");


Hashtable 类中的哈希函数比前面介绍的社保号的实现要更为复杂。哈希函数必须返回一个序数(Ordinal Value)。对于社保号的例子,通过截取后四位就可以实现。但实际上 Hashtable 类可以接受任意类型的值作为 Key,这都要归功于 GetHashCode 方法,一个定义在 System.Object 中的方法。GetHashCode 的默认实现将返回一个唯一的整数,并且保证在对象的生命周期内保持不变。

Hashtable 类中的哈希函数定义如下:


H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize

这里的 GetHash(key) 默认是调用 key 的 GetHashCode 方法以获取返回的哈希值。hashsize 指的是哈希表的长度。因为要进行求模,所以最后的结果 H(key) 的范围在 0 至 hashsize - 1 之间。

当在哈希表中添加或获取一个元素时,会发生哈希冲突。前面我们简单地介绍了两种冲突解决策略:

  • 线性探查(Linear Probing)
  • 二次探查(Quadratic Probing)

在 Hashtable 类中则使用的是一种完全不同的技术,称为二度哈希(rehashing)(有些资料中也将其称为双重哈希(double hashing))。

二度哈希的工作原理如下:

有一个包含一组哈希函数 H1...Hn 的集合。当需要从哈希表中添加或获取元素时,首先使用哈希函数 H1。如果导致冲突,则尝试使用 H2,以此类推,直到 Hn。所有的哈希函数都与 H1 十分相似,不同的是它们选用的乘法因子(multiplicative factor)。

通常,哈希函数 Hk 的定义如下:


Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

当使用二度哈希时,重要的是在执行了 hashsize 次探查后,哈希表中的每一个位置都有且只有一次被访问到。也就是说,对于给定的 key,对哈希表中的同一位置不会同时使用 Hi 和 Hj。在 Hashtable 类中使用二度哈希公式,其始终保持 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) 与 hashsize 互为素数(两数互为素数表示两者没有共同的质因子)。

二度哈希使用了 Θ(m2) 种探查序列,而线性探查(Linear Probing)和二次探查(Quadratic Probing)使用了Θ(m) 种探查序列,故二度哈希提供了更好的避免冲突的策略。

Hashtable 类中包含一个私有成员变量 loadFactor,loadFactor 指定了哈希表中元素数量与位置(slot)数量之间的最大比例。例如:如果 loadFactor 等于 0.5,则说明哈希表中只有一半的空间存放了元素值,其余一半都为空。

哈希表的构造函数允许用户指定 loadFactor 值,定义范围为 0.1 到 1.0。然而,不管你提供的值是多少,范围都不会超过 72%。即使你传递的值为 1.0,Hashtable 类的 loadFactor 值还是 0.72。微软认为loadFactor 的最佳值为 0.72,这平衡了速度与空间。因此虽然默认的 loadFactor 为 1.0,但系统内部却自动地将其改变为 0.72。所以,建议你使用缺省值1.0(但实际上是 0.72)。

向 Hashtable 中添加新元素时,需要检查以保证元素与空间大小的比例不会超过最大比例。如果超过了,哈希表空间将被扩充。步骤如下:

  • 哈希表的位置空间几乎被翻倍。准确地说,位置空间值从当前的素数值增加到下一个最大的素数值。
  • 因为二度哈希时,哈希表中的所有元素值将依赖于哈希表的位置空间值,所以表中所有值也需要重新二度哈希。

由此看出,对哈希表的扩充将是以性能损耗为代价。因此,我们应该预先估计哈希表中最有可能容纳的元素数量,在初始化哈希表时给予合适的值进行构造,以避免不必要的扩充。

Hashtable 类是一个类型松耦合的数据结构,开发人员可以指定任意的类型作为 Key 或 Item。当 .NET 引入泛型支持后,类型安全的 Dictionary<K,T> 类出现。Dictionary<K,T> 使用强类型来限制 Key 和 Item,当创建 Dictionary<K,T> 实例时,必须指定 Key 和 Item 的类型。


Dictionary<keyType, valueType> variableName = new Dictionary<keyType, valueType>();

如果继续使用上面描述的社保号和员工的示例,我们可以创建一个 Dictionary<K,T> 的实例:


Dictionary<int, Employee> employeeData = new Dictionary<int, Employee>();

这样我们就可以添加和删除员工信息了。


1 // Add some employees
2 employeeData.Add(455110189) = new Employee("Scott Mitchell");
3 employeeData.Add(455110191) = new Employee("Jisun Lee");
4
5 // See if employee with SSN 123-45-6789 works here
6 if (employeeData.ContainsKey(123456789))

Dictionary<K,T> 与 Hashtable 的不同之处还不止一处。除了支持强类型外,Dictionary<K,T> 还采用了不同的冲突解决策略(Collision Resolution Strategy),这种技术称为[b]链接技术(chaining)


前面使用的探查技术(probing),如果发生冲突,则将尝试列表中的下一个位置。如果使用二度哈希(rehashing),则将导致所有的哈希被重新计算。而链接技术(chaining)将采用额外的数据结构来处理冲突。Dictionary<K,T> 中的每个位置(slot)都映射到了一个链表。当冲突发生时,冲突的元素将被添加到桶(bucket)列表中。

下面的示意图中描述了 Dictionary<K,T> 中的每个桶(bucket)都包含了一个链表以存储相同哈希的元素。




上图中,该 Dictionary 包含了 8 个桶,也就是自顶向下的黄色背景的位置。一定数量的 Employee 对象已经被添加至 Dictionary 中。如果一个新的 Employee 要被添加至 Dictionary 中,将会被添加至其 Key 的哈希所对应的桶中。如果在相同位置已经有一个 Employee 存在了,则将会将新元素添加到列表的前面。

向 Dictionary 中添加元素的操作涉及到哈希计算和链表操作,但其仍为常量,渐进时间为 O(1)。

对 Dictionary 进行查询和删除操作时,其平均时间取决于 Dictionary 中元素的数量和桶(bucket)的数量。具体的说就是运行时间为 O(n/m),这里 n 为元素的总数量,m 是桶的数量。但 Dictionary 几乎总是被实现为 n = O(m),也就是说,元素的总数绝不会超过桶的总数,所以 O(n/m) 也变成了常量 O(1)。

参考资料


本篇文章《常用数据结构及复杂度》由 Dennis Gao 发表自博客园,任何未经作者同意的爬虫或人为转载均为耍流氓。

评论