哈希表的实现 何为哈希表 简单来说,哈希表是一种存储结构,它存储的数据是 key:value 类型的。通过空间换时间的方法来加快查询速度,具体思想是如下: 使用一个较大的一维数组存储value,这个数组为Array 实现一个哈希函数,使得hash(key)的值在上一步的一维数组下标范围内 如此,对于任意的key:value,使用hash(key),之后就可以知道value在数组中存储的下标,存取速度快过线性查找Array[hash(key)] 哈希表的注意要点 哈希函数的选取 由于我们期望,两个不同的key,hash(key)之后的结果尽量不相同,这样才能使得哈希表存储空间的利用率提高,另一点,哈希表的空间换时间的主要原因就是他使用了哈希函数来确定value在数组中的下标而非普通的线性查找。那么,基于以上两点,哈希函数的选取就有以下条件: hash函数运行速度不能过慢 对于不同的key(即便两个key只是字母顺序不一致),哈希函数须尽量保证hash(key)的值不一致 处理哈希碰撞 由于是无论k 继续阅读 >>


李余通 18/10/09 20:17:14
根据我上一片博客的介绍–c++函数模板初探 我们可以用模板实现很多函数,也对c++函数模板有了初步的了解。 但是加入有下面这个情况: template <class T1, class T2> void ft (T1 &x, T2 &y) { ... ?type? xpy = x+; ... } 在这种情况下xpy应该是什么类型呢?由于不知道ft()将如何使用,因此无法预知这一点。正确的类型可能是T1、T2或者其他类型。假如又出现了重载运算符,这会让问题更加的复杂。 于是为了解决这个问题,c++11新增了关键字 decltype。 我们可以这样使用: int x; decltype(x) y;//y的类型和x类型一致 除了上述这样写,我们也可以这样写: decltype(x+y) xpy; xpy = x+y; 通过这个关键字,我们可以把前面的代码修改成这样: template <class T1, class T2> void ft(T1 x, T 继续阅读 >>


陈苏扬 18/10/04 07:40:50
注:本篇博客主要内容来源于网络,侵删~ 引言 我们假设你已经熟练掌握了CAS,原子变量类等的相关概念。这篇博客中,我们主要讨论原子变量类的使用。 原子变量类 原子变量类共12个,分4组: 计数器:AtomicInteger,AtomicLong,AtomicBoolean,AtomicReference。 域更新器:AtomicIntegerFieldUpdater,AtomicLongFieldUpdater,AtomicReferenceFieldUpdater。 数组:AtomicIntegerArray,AtomicLongArray,AtomicReferenceArray。 复合变量:AtomicMarkableReference,AtomicStampedReference。 在每组中我会选择其中一个较有代表性的进行分析与举例。 AtomicReference 使用说明 AtomicReference的作用是对"对象"进行原子操作。 源码分析 public class AtomicR 继续阅读 >>


董恒毅 18/10/03 13:51:16
C++之所以强大,其中肯定少不了模板的功劳。使用好模板也可以为以后的编程省去很多的功夫。 函数模板是通用的函数描述,也就是说,它们使用泛型来定义函数,其中泛型可用具体的类型(如int或double) 替换。通过将类型作为参数传递给模板,可使编译器生成该类型的函数。由于模板允许以泛型的方式编写程序,因此有时也被称为通用编程。由于类型使用参数表示的,因此模板特性有时也被成为参数化类型(parameterized types) (C++ Primer Plus 第六版中文 P281) 以上就是一个函数模板的定义。 首先如果没有函数模板, 试想如果需要一个函数来交换两个数字的值,这个时候由于不知道两个数字的类型,你需要使用函数重载来写很多个类型的函数,如 void Swap(int &, int &); void Swap(double &, double &); void Swap(char &, char &); void Swap(short &am 继续阅读 >>


陈苏扬 18/10/03 10:10:56
1