俗话说:“万变不离其宗”,程序亦是如此。
无论是
HashSet
、
HashMap
、
Hashtable
,还是
TreeSet
、
PriorityQueue
,都不离其原则。众所周知,衡量一个程序的好坏、数据结构好坏的重要指标是其空间复杂度和时间复杂度。
“鱼和熊掌不可兼得”,时间复杂度和空间复杂度也不能兼顾。比如数组,由于存储空间物理上不连续,其空间占用大;而链表,虽然占用空间较小,而且可以充分利用零散的存储空间,但它没有数组所拥有的下标,导致其时间复杂度较高。
万事万物都有其制约因素,所以也就没有完全意义上的完美,但我们可以寻求“相对的完美”。时间复杂度和空间复杂度势必有一方要被舍弃,但高速发展的社会不仅要求时间上的高效,也要求空间上的资源高效利用。看官(应该有)要问了,“那怎么办呀”?
我们聪明的老祖宗已经为我们埋下了伏笔。“中庸”的思想帮到了我们。既然各有优点,那何不有机的结合各种结构的优点,这样不就可以达到时间复杂度和空间复杂度的平衡点,也许会是黄金分割点。
TreeSet
就是个鲜明的例子,是
tree
结构和
Set
结构的有机结合,极大的提高了数据结构的“优雅”和“韵律”。
看到这,你也许以为,“有机结合各家所长”就是“宗”了。非也,宗者,乃假外物以为余是也。借助外力补足缺点才是王道。有机结合是通过结合利用其它结构补足自身补足。
除此之外,通过适当的转换,也可以达到优化结构的目的。高中物理书中写道:“力是改变物体状态的原因”。对于
IT
男男女女来说,我们想要改变现有对象的状态时,添加方法就是我们的“力”。你没有下标,增加了时间复杂度。
Ok
,我将你跟连续的下标联系起来不就行啦!以
hash
结构为例,基本思想就是通过
hash
函数(即我们的“力”),改变原有的数据结构特点,以补不足。显然,
HashSet
就是用
hash
函数构造的
Set
;
HashMap
就是用
hash
函数构造的
Map
……你若问我
hash
函数是什么?它是具体情况而定。
下面,以我自定义的
hash
结构为例。
构建一个简单的
hash
结构,流程如下:
1、
利用
hash
函数得到
hash
值,通常为键值或下标位置。
2、
将对应的属性值放入到对应键值或下标的相应位置。如选择的是键值对就放入集合内;如选择的是链表就放入节点,加在末尾如下图
1
。
3、
因为是通过函数计算,且键值和下标的本地
hashcode
值通过计算可能相同,就会产生冲突,链表可以加在末尾,但随冲突的增加,链表越来越长,采用
hash
结构的优势越来越弱,此时就要重构
hash
结构。是否需要重构根据具体情况而设定的峰值而定。如下图
2
,为
rehash
后的结果。
4、
于是出现了问题出现了,怎样重构更好呢?
hash
结构其实是通过
hash
函数对各个属性值的散列。既然是散列,就会有一个散列的程度问题。重构时,如能使当前结构内数据
rehash
后,其散列程度趋于
0
时,重构效果较好。统计学可以通过计算残差,判断之前的系统是否稳定,相信对于
hash
结构,同样适用。散列程度的值可以根据冲突数与总数据量之间的关系得到。如下图
3
。
图1:
图2:
图3:
我的代码示例如下:
Hashstructure
:
package hash;
import java.util.LinkedList;
public class HashStruct {
// 定义一个数组
private static int hashcode = 10;// hashcode值用于rehash时,重构hash结构
private static LinkedList[] hasharray;
private static int clashes;// 记录冲突数
private static int numbers;// 记录结构内成员数
// hash结构就是根据当前数值,通过hash函数,算得当前值应放入的hashstructure中的位置。
// 设计hash函数
public int hashFunction(int x) {
int hash = x % hashcode;// hashcode为构建的hash函数中的一个变量
return hash;
}
// 向hash结构中添加元素
public void add(int key) {
int index = this.hashFunction(key);
if (hasharray[index].size()>0) {
clashes++;
}
hasharray[index].add(key);
numbers++;
// 判断添加后冲突数是否超过峰值,如超过,重构hash结构
if (this.rank(clashes, numbers)) {
this.rehash(hasharray);
}
}
// 当冲突数超过峰值时,需要重建hash结构
public void rehash(LinkedList[] hasharray) {
hashcode += 5;
LinkedList[] hasharray2 = hasharray.clone();
hasharray = null;
this.init();
for (int i = 0; i < 10; i++) {
for (int j = 0; j < hasharray2[i].size(); j++) {
this.add(hasharray2[i].get(j).hashCode());
}
}
System.out.println("rehashed!");
}
// 峰值计算函数
public boolean rank(int clash, int numbers) {
boolean result = false;
double c=(double) clash / (double) numbers;
if (((double) clash / (double) numbers) >= 0.65) {
result = true;
}
return result;
}
// 遍历对应hash值下的元素
public void get() {
for (int i = 0; i < hasharray.length; i++) {
System.out.println("hasharray["+i+"]:"+hasharray[i]);
}
}
// 初始化hashstruct
public void init() {
hasharray = new LinkedList[hashcode];
clashes = 0;// 记录冲突数
numbers = 0;// 记录结构内成员数
for (int i = 0; i < hashcode; i++) {
hasharray[i] = new LinkedList<Integer>();
}
}
}
Test
:
package hash;
public class Test {
public static void main(String[] args) {
HashStruct hs = new HashStruct();
hs.init();
// 添加10个数
hs.add(10);
hs.add(12);
hs.add(22);
hs.add(25);
hs.add(15);
hs.add(35);
hs.add(27);
hs.add(37);
hs.add(47);
hs.add(17);
// 检查添加结果
hs.get();
//继续添加,验证rehash
for(int i=1;i<20;i++){
hs.add(i*7);
}
hs.get();
}
}
图4:
如上图
4
为输出结果。对比上图
1
和图
2
,达到了
rehash
的效果。(蓝色线上是初始构建
hash
结构的测试,下方是
rehash
测试。注意红色标记为初始时插入测试的数据。)
Array
AND LinkedList Hashstructure
雌雄双剑剑法演示完毕,请各位看官出招。
- 大小: 13 KB
- 大小: 16.7 KB
- 大小: 17.8 KB
- 大小: 13.8 KB
分享到:
相关推荐
数据结构课程设计, hash表,哈希表。
数据结构中hash函数的实现,自己写的,VC平台。
hash表线性探测再散列,c语言编写,可直接运行
数据结构(字符串匹配,hash,二叉树)训练 数据结构(字符串匹配,hash,二叉树)训练
数据结构第16次作业,hash表 Spellchecking Prerequisites, Goals, and Outcomes Prerequisites: Students should have mastered the following prerequisite skills. • Hash Tables - Understanding of the ...
树 树是⼀种数据结构,它是由n(n>=1)个有限节点组成⼀个具有层次关系的集合。把它叫做 "树" 是因为它看起来像⼀棵倒挂的树,也就 是说它是根朝上,⽽叶朝下的。它具有以下的特点: 每个节点有零个或多个⼦节点; ...
数据结构课程实验Hash表设计实验报告,严蔚敏C语言版。
并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则根据比较的结果确定下次查找的范围是在中间记录的前半部分还是后半部分,然后在新的查找范围内...
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
数据结构Hash表C语言实现
本文主要介绍Hash函数的设计优化,包括数字、字符串、排列等,并给出相关的代码。
java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法
基本数据结构 基本数据结构部分包括线性表、堆栈与队列、数组、字符串、整数集合类、树(包括AVL树、伸展树等)、图(包括网络流等问题的讨论)、散列(Hash)等 典型算法 典型算法部分主要介绍了若干典型算法的实现...
云计算中数据存储安全的变色龙Hash认证树优化审计.pdf
数据结构课程实验Hash表设计,严蔚敏C语言版。
试谈哈希树(HashTree)数据结构分析报告.doc
2.自己定义数据结构,写出程序:二叉树的前序遍历。 3.实现双向链表删除一个节点P,在节点P后插入一个节点,写出这两个函数。 4.下面哪种排序法对12354最快 a quick sort b.buble sort c.merge sort 5.哪种...
Map数据结构 数据结构 JavaScript 的对象(Object),本质上是键值对的集合(Hash 结构),但是传统上只能⽤字符串当作键。这给它的使⽤带来了很⼤的限 制。 为了解决这个问题,ES6 提供了 Map 数据结构。它类似于...
该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不通。...
数据结构:映射 数据结构:映射 我们通常所⽤的map其实就是⼀棵红⿊树,如果有平衡树问题能够⽤它来解决⼀定要⽤,不要⼿写了,因为红⿊树的效率是⾮常棒的 先看⼏个定义: map,int> m1; map,map,int> >m2; multiset...