java集合 链表和hash表问题

Jordan裔 发布于 2017/02/25 12:05
阅读 186
收藏 1

刚刚看了java集合 有些不懂的地方 
链表为什么有利于增删 
hash表为什么有利于改查

加载中
0
蓝水晶飞机
蓝水晶飞机

链表:

Node1.next->Node2.next->null

删除Node2:Node1.next=Node2.next,Node2.next=null,回收掉Node2!

对比数组:

Node[] array = new Node[1024];

int deleteIndex = 1000;

Node[] newArray = new Node[array.length - 1];        // 重新分配内存,消耗大

Systen.arraycopy(array, 0, newArray, 0, deleteIndex); // 拷贝删除的元素之前的元素0-999,循环一次

System.arraycopy(array, 0, newArray, deleteIndex+1, array.length); // 拷贝删除的元素之后的元素1001-1024,再循环一次

array = newArray;

上面说的没有参考JDK,只是自己想的。

哈希

哈希算法,根据对象的哈希值按桶存放,用哈希来快速定位到对象的位置,数据量大的时候比硬性遍历要快速,相当于数据库建立了聚集索引(又比如新华字典索引)吧!

哈希算法比较复杂,没有深入研究过,你可以去研究下。

蓝水晶飞机
蓝水晶飞机
第二个arraycopy的第二参数0应该是deleteIndex+1
0
王老思
王老思
链表不用管序号,增删直接,所以。。。hash函数可以根据键确定键值对在hash表中位置的地址,所以。。。
0
mn
mn

我发方块接啊龙卷风

0
中山野鬼
中山野鬼

哈,这个和java没关系。这是基础知识。本科老师应该教的。关于第一个问题是有序集合中,存储与逻辑的问题。如果在一个连续存储空间我们存放集合中的元素(这是抽象的说法,讲人话就是数组中的各个单元),必然这些元素之间有针对存储的逻辑关系。这些逻辑是和存储位置相关的。谁在前,谁在后。而实际应用中,很多集合的元素之间是有逻辑关系的,而这些逻辑关系和存储位置之间的逻辑关系无关。比如,线性序列(前面的是小值,后面的大值)。

我们存在两种做法,1、让存储位置之间逻辑和有序集合中元素之间的关联逻辑对应。这种做法有各种不足,比如,你删除掉一个元素后,存储位置后续的数据要依次填到前面的存储空间中,才能保证存储位置的逻辑和集合中元素之间的逻辑一一对应。更不幸的是,线性的存储位置的逻辑无法对应非线性的,例如树,图等元素之间的逻辑关系。

那么解决的方案就是第二种做法,索引。这个索引是用来描述元素之间的关系,此时集合中,元素之间的关系与存储位置关系就没有联系了。带来的好处就是,当你删除一个元素时,虽然要调整元素之间的关系,但是只需要调整局部即可,同时不需要改变其他元素的实际存储位置。

如果这个索引直接是地址,那么就是所谓的指针化链表(但我仍然是反指针派-不怕被人喷,针对64位系统,谁用指针做索引谁sb哈)。此时你会发现,这些索引是元素对元素的。例如这个顶点存在一个边,指向另一个顶点。或者这个元素存在一个索引指向下一个元素。这种方式已经能解决对集合所有元素的遍历问题。但不能有效解决集合中元素的快速查询。

要想实现快速查询,需要两个不同角度来改善,其一是集合的分类,其二是元素与元素的快速比较。快速比较不是说两个元素的内容是否一致的对比,而是一个元素,与另一个集合中所有元素依次对比,找到和自己内容一致的元素。

如果我们的元素的内容,是可以线性排序的,总能用某种方式确定谁大谁小,那么就不用一一比较了。我们可以用各种快速查询方法。因为你发现一个元素比你要找的元素小,则所有小于这个元素的其他元素是没有再比较的必要。此时一个简单的实现方式,就是我们将元素的内容,想办法投影到一个线性空间中,让不同元素的内容,大概率下对应不同的值。此时,你要查询某个元素内容在集合中是否存在,则可以通过映射后的值进行查询,而此时的查询可以用各种快速算法 。hash来映射,有个好处就是散列性比较好(其实也要看函数怎么构造),所以用它来作为映射投影。

散列性好的另一个优势就是,基于hash值分类,此时不同子类的数据相对均衡,作为分类查找会更有优势(压根没有工程道理,心理作用,哈,实际工程上散列性好不好,需要依据给入数据的先验分布概率来判断)。

0
notreami
notreami

突然明白为啥那些研究生,博士生要去研究机器学习,人工智能了,这特么是为了提高技术壁垒。比如上来就一个神经网络啥的,瞬间晕菜一群人

返回顶部
顶部