Archive

Posts Tagged ‘数据结构’

算法基础–哈希表(hash table)

August 14th, 2009 2 comments

哈希表(hash table)是比较常用的数据结构,它能提供接近常量时间复杂度的数据插入和查找性能。哈希表的本质是利用一个哈希函数(hash function)将一个较大的取值范围映射到一个较小的取值范围,从而一方面节省了存储空间,另一方面又没有失去随机存取的性能。

举个简单的例子,比如我们手里有全班30个学生每个人的生日的数据表格,我要求快速的找出某一天有没有人,有哪些人过生日。最容易(或者说最笨)的算法是在表格里挨个查找,看谁的生日和指定的日期一致,显然这种算法是线性时间复杂度的,换句话说平均所需要的时间和全班人数成正比。

如果想快一点怎么办呢?可以事先把所有同学的名字填到一张有365个格子的大表里,每格代表一年中的一天,这样要知道某一天谁生日只要找到对应的格子,那天过生日的同学名字就在里面了。这个算法是常量复杂度的,就是说不管全班有多少人,我都能在几乎同样的时间里找到指定日期生日的人。

Read more…

Categories: 程序/算法 Tags: ,

HeapAlloc内部算法

December 23rd, 2005 1 comment

大家都知道在VC中使用new操作符时(如果没有重载的话),其内部实际上调用了标准的malloc,而根据工程设置中选择的运行库的不同(是否多线程,是否调试,是否Dll等)调用了不同的malloc版本,多线程版malloc内部使用了Win32的关键区,而调试版会额外多申请一些内存用来保存调试信息,这些直接看VC附带的crt源码就可以看到。所有版本的malloc的共同点是最后都调用了Win32的API函数HeapAlloc。

关于HeapAlloc的算法记得很多年前一个后来去了微软的大牛给我讲过,但当时我还是个菜鸟(现在没那么菜了)没记住,于是决定自己研究一下。方法是用HeapCreate自己建一个堆,用HeapAlloc从里面申请内存,同时用VC的内存查看盯着heap所在内存区看,观察Alloc和Free的时候内存都发生了哪些变化。其间从网上找到的这篇文档帮助比较大,节省了不少时间。

Heap头的结构基本没搞明白(也不需要太关心),只知道在偏移地址0x28的位置记录的是剩余空间大小(单位是8字节),然后从0x178开始是一个free list 表(数组),一共128个单元,每个单元的数组下标代表这个链上每个节点(free chunk)是多大(包括chunk header所占空间,单位是8字节)。所以记录的是0~1024(128×8)大小的free chunk链,每个单元是一个循环链表,Flink和Plink指针共占用8个字节。第0号单元比较特殊,它维护的是大小>=1k的chunk的list,按chunk大小升序排列。 Read more…

Categories: 程序/算法 Tags: ,