prince的文章

引入 什么情况下需要布隆过滤器？我们先来看几个比较常见的例子： 字处理软件中，需要检查一个英语单词是否拼写正确 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里，一个网址是否被访问过 yahoo, gmail等邮箱垃圾邮件过滤...

赞(0)prince数据结构与算法-基础（四） 阅读(181)

Trie，又经常叫前缀树，字典树等等。它有很多变种，如后缀树，Radix Tree/Trie，PATRICIA tree，以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。 Trie树是一种非常重要的数据结构...

赞(0)prince数据结构与算法-基础（四） 阅读(160)

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）...

赞(0)prince数据结构与算法-基础（四） 阅读(169)

排序 排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。 排序的主要目的就是实现快速查找。 排序分类 增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排...

赞(0)prince数据结构与算法-基础（四） 阅读(197)

哈希表的概念 哈希表（Hash Table）是一种特殊的数据结构，它最大的特点就是可以快速实现查找、插入和删除。 我们知道，数组的最大特点就是：寻址容易，插入和删除困难；而链表正好相反，寻址困难，而插入和删除操作容易。那么如果能够结合两者的...

赞(0)prince数据结构与算法-基础（四） 阅读(175)

B树 B-树，就是B树，B树的原英文名是B-tree,所以很多翻译为B-树,就会很多人误以为B-树是一种树、B树是另外一种树。其实，B-tree就是B树。 B-树的定义 B树（B-tree）是一种树状数据结构，是一种平衡的多路查找树，能够用...

赞(0)prince数据结构与算法-基础（四） 阅读(191)

我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化...

赞(0)prince数据结构与算法-基础（四） 阅读(179)

二叉排序树（Binary Sort Tree）又称为二叉查找树（Binary Search Tree）、二叉搜索树。 它是特殊的二叉树： 对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。...

赞(0)prince数据结构与算法-基础（四） 阅读(186)

查找 基本概念 查找就是在数据集中找出一个“特定元素”。 查找表是由同一类型的数据元素(或记录)构成的集合。 查找表是一种以集合为逻辑结构、以查找为核心的数据结构。 关键字 有时候我们需要指定某数据项的值来查找，这就用到了关键字。 关键字是...

赞(0)prince数据结构与算法-基础（四） 阅读(164)

最短路径 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小，例...

赞(0)prince数据结构与算法-基础（四） 阅读(178)