- 浏览: 318962 次
- 性别:
- 来自: 西宁
文章分类
- 全部博客 (120)
- Java Thought (29)
- Java Pattern (4)
- Data Base (7)
- Algorithm Design (33)
- Linux (0)
- Mysql (2)
- Oracle (0)
- ConstructionDesign-架构 (5)
- Spring Platform (0)
- Tomcat (1)
- JavaScript (7)
- Web System (3)
- MS SQLServer (1)
- 软件哲学 (6)
- View (3)
- Java GUI (4)
- CSSDIV (7)
- CloudComputing (0)
- WebService (0)
- SystemOrProject (2)
- SOA (0)
- 互转共享 (3)
- 偶尔java习题 (0)
- Thinks with does (1)
最新评论
-
sassds:
佩服啊 高手
分享一款js特效 -
bhjackson:
学习啦,能否详细介绍下回溯的过程?O(∩_∩)O谢谢
分享回溯法- 找n个数中r个数的组合 -
zk7019311:
了解了解。。。。。
业务层代码复用的一点建议 -
lijie1819:
看到LZ的设计思想,感觉和抽象工厂模式有点相像。
业务层代码复用的一点建议 -
wjjcml1982:
酷毙了!楼主太强悍了!
分享一款js特效
1. 散列
散列有两种形式。一种是开散列(或外部散列),它将字典元素存放在一个潜无穷的空间里,因此它能处理任意大小的集合。
另一种是闭散列(或内部散列), 它使用一个固定大小的存储空间,因此它能处理的集合的大小不能超过它的存储空间的大小。
2. 开散列
(1)下图是一个开散列表,它表示了开散列的基本数据结构。
(2) 基本思想
开散列的基本思想是将集合的元素(可能有无穷多个)划分成有穷多个类。例如,划分为0、1、2、....、B-1这B个类。用散列函数h将集合中的每个元素x映射到0、1、2、....、B-1之一,h(x)的值就是x所属的类。h(x)称为x的散列值。上面所说的每一个类称为一个桶,并且称x属于桶h(x).
我们用一个链接表表示一个桶。x是将第i个链接表中的元素当且仅当h(x)=i,即x属于第i个桶。B个桶(链接表)的桶(表)头存放于桶(表)头数组中。
用散列表来存储集合中的元素时,总希望将集合中的元素均匀地散列到每一个桶中,使得当集合中含有n个元素时,每个桶中平均有n/B个元素。如果我们能估计出n,并选择B与n差不多大小时,则每个桶中平均只有一两个元素。这样,字典的每个运算所需要的平均时间就是一个与n和B无关的小常数。由此可以看出,开散列表是将数组和链接表结合在一起的一种数据结构,并希望能利用它们各自的优点且克服它们各自的缺点。因此,如何选择随机的散列函数,使它能将集合中的元素均匀地散列到各个桶中是散列技术的一个关键。
(3) 求余运算。
如果x是不是数值型,将字符串x中的每个字符转换成一个整数,然后将字符串每个字符所对应的整数相加,用和除以B的余数作为h(x)的值,显然这个余数是0、1、2、....、B-1之一。
3. 模拟代码:
--------------
呵呵 算法是计算机科学的灵魂 基础更为重要
你能给出闭散列的代码吗?在30分钟内
散列有两种形式。一种是开散列(或外部散列),它将字典元素存放在一个潜无穷的空间里,因此它能处理任意大小的集合。
另一种是闭散列(或内部散列), 它使用一个固定大小的存储空间,因此它能处理的集合的大小不能超过它的存储空间的大小。
2. 开散列
(1)下图是一个开散列表,它表示了开散列的基本数据结构。
(2) 基本思想
开散列的基本思想是将集合的元素(可能有无穷多个)划分成有穷多个类。例如,划分为0、1、2、....、B-1这B个类。用散列函数h将集合中的每个元素x映射到0、1、2、....、B-1之一,h(x)的值就是x所属的类。h(x)称为x的散列值。上面所说的每一个类称为一个桶,并且称x属于桶h(x).
我们用一个链接表表示一个桶。x是将第i个链接表中的元素当且仅当h(x)=i,即x属于第i个桶。B个桶(链接表)的桶(表)头存放于桶(表)头数组中。
用散列表来存储集合中的元素时,总希望将集合中的元素均匀地散列到每一个桶中,使得当集合中含有n个元素时,每个桶中平均有n/B个元素。如果我们能估计出n,并选择B与n差不多大小时,则每个桶中平均只有一两个元素。这样,字典的每个运算所需要的平均时间就是一个与n和B无关的小常数。由此可以看出,开散列表是将数组和链接表结合在一起的一种数据结构,并希望能利用它们各自的优点且克服它们各自的缺点。因此,如何选择随机的散列函数,使它能将集合中的元素均匀地散列到各个桶中是散列技术的一个关键。
(3) 求余运算。
如果x是不是数值型,将字符串x中的每个字符转换成一个整数,然后将字符串每个字符所对应的整数相加,用和除以B的余数作为h(x)的值,显然这个余数是0、1、2、....、B-1之一。
3. 模拟代码:
package boke.dictionary; /** * 开散列的简单模拟(一): 桶元素 * * @since jdk1.6 * @author 毛正吉 * @version 1.0 * @date 2010.05.25 * */ public class Node { public int iData; public Node next; public Node(int i) { iData = i; } } ----------------------------------------------- package boke.dictionary; /** * 开散列的简单模拟(一): 作为简单模拟,元素选取整型 * * @since jdk1.6 * @author 毛正吉 * @version 1.0 * @date 2010.05.25 * */ public class Hash { /** * @param args */ public static void main(String[] args) { Hash hh = new Hash(1000); for (int i = 0; i <= 100; i++) { hh.insert(i); } System.out.println(hh.find(10)); System.out.println(hh.find(50)); System.out.println(hh.find(90)); System.out.println(hh.find(1000)); hh.insert(1000); System.out.println(hh.find(1000)); hh.delete(10); System.out.println(hh.find(10)); hh.insert(0); System.out.println(hh.find(0)); } private Node[] bucket; // 桶 private int maxSize; // 桶的个数 /** * 构造方法 * * @param maxSize */ public Hash(int maxSize) { this.maxSize = maxSize; bucket = new Node[maxSize]; makeNULL(); } /** * 字典初始化 */ public void makeNULL() { for (int i = 0; i < maxSize - 1; i++) { bucket[i] = null; } } /** * 查找x是否在字典中 * * @param x * @return */ public boolean find(int x) { int mod = x % maxSize; Node current = bucket[mod]; while (current != null) { if (current.iData == x) { return true; } else { current = current.next; } } return false; } /** * 插入x到hash字典中 * * @param x */ public void insert(int x) { if (!find(x)) { Node node = new Node(x); int mod = x % maxSize; Node old = bucket[mod]; bucket[mod] = node; bucket[mod].next = old; } else { System.out.println("该值已存在,不能重复插入!"); } } /** * 从hash字典中删除x * * @param x */ public void delete(int x) { int mod = x % maxSize; if (bucket[mod] != null) { if (bucket[mod].iData == x) { bucket[mod] = bucket[mod].next; } else { Node current = bucket[mod]; while (current.next != null) { if (current.next.iData == x) { current.next = current.next.next; } else { current = current.next; } } } } } }
评论
4 楼
maozj
2010-06-28
wese345 写道
大学时,数据结构对我来所简直是噩梦啊,呵呵
--------------
呵呵 算法是计算机科学的灵魂 基础更为重要
3 楼
wese345
2010-06-28
大学时,数据结构对我来所简直是噩梦啊,呵呵
2 楼
maozj
2010-06-28
mccxj 写道
最基本的数据结构,没看到什么亮点
你能给出闭散列的代码吗?在30分钟内
1 楼
mccxj
2010-06-28
最基本的数据结构,没看到什么亮点
发表评论
-
递归和动态规划构造两个字符序列的最长公共字符子序列
2010-06-28 08:28 4460应je朋友要求,所以翻开以前的算法题目,整理了以下,给 ... -
最大公约数的应用 - 分享
2010-06-25 08:08 17811.先看一家大公司笔试题 数组中有n个数据,要将它们顺 ... -
信息数字化解逻辑题分享
2010-06-21 08:09 12201. 前提条件: 将逻辑题目中的信息用数字化描述。 ... -
递归算法分析-分享
2010-06-19 16:09 15241. 深入认识递归 (1) 递 ... -
非递归算法分析实例分享
2010-06-18 15:47 10121 仅仅依赖于问题规模的时间复杂度 (1) 例1: 交换i和 ... -
NP完全性问题
2010-06-18 14:02 6966在学习算法设计与分析时,经常会提到NP完全性问题,到底 ... -
算法分析精述分享
2010-06-18 12:03 8201. 算法分析的评价体系 评价算法的三条主要标准是: ... -
贪婪策略算法的总结分享
2010-06-11 08:30 59711. 贪婪算法描述 贪婪算法又叫登山法,它的根本思想是 ... -
带权有向图 - 边上权值非负情形的单源最短路径问题
2010-06-07 08:57 26341. 问题描述: 给定 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)四
2010-06-07 08:54 132221. 工作分配问题。 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)三
2010-06-07 08:53 105017. 字符统计问题。 编写一个算法,统计在一个输入 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)二
2010-06-07 08:47 13248. 数字迷问题。 A B C ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)一
2010-06-07 08:38 11321. 线程问题。 设计4个线程,其中两个线程每次对j增加 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)
2010-06-07 08:37 18351. 线程问题。 设计 ... -
Java快速排序算法整理(二)
2010-05-31 14:04 1008package boke.sort; /** * 快 ... -
Java快速排序算法整理(一)
2010-05-31 13:39 629package boke.sort; /** * 快 ... -
Java最小堆实现
2010-05-31 08:29 58041.堆结点 package boke.heap1; /* ... -
Java插入排序代码整理
2010-05-28 14:44 1212package boke.sort; /** * 插 ... -
Java选择排序代码整理
2010-05-28 14:37 1478package boke.sort; /** * 选 ... -
Java冒泡排序代码整理
2010-05-28 14:26 1929Java冒泡排序代码整理: package boke.sor ...
相关推荐
1,散列星空:不同大小的星体被中心黑洞吸引,形成一个小型的星系。在此过程中会出现双星、聚星、星团等现象。黄道视角定位在随机星体上。 2,太阳系(可操控):模拟太阳系六大行星(只到土星轨道)和众多小行星的...
也许有一天,mocki会长大,接受方便的选项,例如仅提供操作的路由散列... 或者可能只是保留一个乐于遵循简单约定的小脚本。 mocki比的凉爽度少1/1000,但是我想要坚持不懈并学习一些东西。 用法 为集合创建目录以...
其中关于HASH这一块就比较多的问题,列如我们能够用常用的gsechash、gethashes等工具抓到windows的HASH散列值的话。也经常会有破解不了。 原因有二: 一、你的彩虹表字典进行暴力破解时字典内容不够强大;现如今...
unordered_map和unordered_set的模拟实现 (一)哈希表的特性及概念 定义: 哈希表(Hash table,也叫散列表),是根据关键字值(key,value...也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储
计算机和网络技术的发展将人类带入信息化社会,随之而来的是倍受关注的信息安全问题。...然后通过使用Windows和Java安全的相关内容实现数字签名在单机上的模拟来更加深刻地了解其过程。最后是对本论文的总结。
许多简单和重要的运算法则和技术已添加到前一版本中,精确的初步计算部分已经修改,以适应当前趋势。 第2卷对半数值算法领域做了全面介绍,分"随机数"和"算术"两章。本卷总结了主要算法范例及这些算法的基本理论,...
OOP引入封装、继承和多态性等概念来建立一种对象层次结构,用以模拟公共行为的一个集合。当我们需要为分散的对象引入公共行为的时候,OOP则显得无能为力。也就是说,OOP允许你定义从上到下的关系,但并不适合定义从...
散列5.1 一般想法5.2 散列函数5.3 分离链接法5.4 开放定址法5.4.1 线性探测法5.4.2 平方探测法5.4.3 双散列5.5 再散列5.6 可扩散列总结练习参考文献第6章 优先队列(堆)6.1 模型6.2 一些简单的实现6.3 二叉堆6.3.1 ...
资格赛# 标题解时间空间困难标签注意一个O(NlogN) O(logN) 简单模拟乙上) O(1) 简单数学分析CO(N * J) 上) 中整rick数学d行) O(1) 硬逻辑,数学归纳第一轮# 标题解时间空间困难标签注意一个O(长) O...
参考文献 第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题 6.4.2 事件模拟 ...
散列5.1 一般想法5.2 散列函数5.3 分离链接法5.4 不用链表的散列表5.4.1 线性探测法5.4.2 平方探测法5.4.3 双散列5.5 再散列5.6 标准库中的散列表5.7 可扩散列小结练习参考文献第6章 优先队列(堆)6.1 模型6.2 ...
2.4 运行时间计算 2.4.1 一个简单的例子 2.4.2 一般法则 2.4.3 最大子序列和问题的求解 2.4.4 运行时间中的对数 2.4.5 检验你的分析 2.4.6 分析结果的准确性 小结 练习 参考文献第3章 表、栈和队列...
2.4 运行时间计算 2.4.1 一个简单的例子 2.4.2 一般法则 2.4.3 最大子序列和问题的求解 2.4.4 运行时间中的对数 2.4.5 检验你的分析 2.4.6 分析结果的准确性 小结 练习 参考文献第3章 表、栈和队列...
4.5.1 一个简单的想法(不能直接使用) 4.5.2 伸展 4.6 树的遍历 4.7 B树 4.8 标准库中的set和map 4.8.1 set 4.8.2 map 4.8.3 set和map的实现 4.8.4 使用几个map的例子 ...
散列5.1 一般想法5.2 散列函数5.3 分离链接法5.4 不用链表的散列表5.4.1 线性探测法5.4.2 平方探测法5.4.3 双散列5.5 再散列5.6 标准库中的散列表5.7 可扩散列小结练习参考文献第6章 优先队列(堆)6.1 模型6.2 一些...
散列5.1 一般想法5.2 散列函数5.3 分离链接法5.4 不用链表的散列表5.4.1 线性探测法5.4.2 平方探测法5.4.3 双散列5.5 再散列5.6 标准库中的散列表5.7 可扩散列小结练习参考文献第6章 优先队列(堆)6.1 模型6.2 一些...
4.5.1 一个简单的想法(不能直接使用) 4.5.2 展开 4.6 树的遍历 4.7 B树 4.8 标准库中的集合与映射 4.8.1 关于Set接口 4.8.2 关于Map接口 4.8.3 TreeSet类和TreeMap类的实现 4.8.4 使用多个映射的例 小结 练习 参考...
许多简单和重要的运算法则和技术已添加到前一版本中,精确的初步计算部分已经修改,以适应当前趋势。 第2卷对半数值算法领域做了全面介绍,分“随机数”和“算术”两章。本卷总结了主要算法范例及这些算法的基本理论...