[深圳|结业弟子]JAVA-张鑫|2017年12月15日的日报-技能树.IT修真院

发表于： 2017-12-15 21:46:20

0 586

一.今天完成的主要事情

1.和小组成员讨论,解决了昨天遗留的问题

这个问题是关于如何实现学员端随机题目的问题,最后讨论出的方案是我们后端先从数据库中获取所有的id,组成一个List,然后对这个List进行乱序,最后再将这个IdList直接返回给app端,app端则每次截取相应的id访问接口,获取数据.

那么问题的关键就是将List中的所有数据乱序,需要花费多长时间,实现是否复杂?

张帆师兄在网上找了一个方案,用Collections接口中自带的 shuffle方法实现将一个list中的数据乱序.

然后由于张帆师兄没有时间,所以由我来写demo调研,demo代码如下

从输出的结果来看,一个由2000个元素的list,经过Collections接口的shuffle方法,成功的实现了乱序,而且记录消耗时间只用差不多3到4ms.完全不会成为性能的瓶颈.

这是输出结果

2.继续学习付老师的课程

学习了数据结构的Set,List,Map以及查找算法(Hash)一节

一.查找及顺序查找

查找的相关定义

查找有两个关键,一个是集合,确定范围,还一个是关键字,确定要找什么;查找表就是集合的具体数据结构,比如说一个数组,链表,树等.

静态查找:只在一个集合中查找特定的数据元素

动态查找:如果在查找的过程中插入查找表中不存在的元素或者删除表中已存在的数据元素.

顺序查找

顺序查找:从表中的一头开始查找,一个接一个查找,直到找到关键字,则查找成功,或者查到表中的最后一个元素都没有找到,则查找失败,时间复杂度为O(n).

顺序查找是最简单的查找方式,效率也不高

其他的查找方法:

当线性表有序的时候,可以用折半(二分)查找,其时间复杂度为O(logn).

分块查找:如分年级,分班,分专业之后再查找.

二.散列(Hash)表

个人理解:给定一个数据,对该数据的关键字进行Hash函数运算,得到该数据的Hash值,然后根据Hash值将数据存储在内存中的相应位置,查找时,可以直接定位到要查找的位置,通过这种方式,建立了关键字和存储地址之间的一种映射关系.

Hash表的查找的理想情况是记录和存储位置一一对应,通过记录的关键字能够直接找到记录的存储位置,所以Hash表这种数据结构使用非常广泛.

Hash函数冲突

Hash表在具体实现中会出现一种情况,即多个不同的记录通过哈希函数计算出来的存储位置相同,这时就产生了冲突,解决冲突的方式有两种,一是构造完美的哈希函数,不论什么记录通过该哈希函数都可以得到不同的位置,但这种理想情况在现实中几乎不可实现,所以在现实中,常用的解决方式是另外一种,允许冲突的存在,对于多条记录来说,先通过哈希表进行分类,然后再使用顺序存储,使得查找的性能在我们可接受的范围之内,针对这种情况,我们对一个良好的哈希函数的定义则是能够将给定的数据均匀的分布在所有的存储位置中.

常见Hash函数的构造方法

哈希表中常见处理冲突的方法

一是结合链表实现,即先对数据的关键字进行hash函数计算,计算得到之后如果发生冲突则生成一个链表,将新加的数据加到链表后面,查找时先计算哈希值,然后再遍历链表

二是当计算出来的值所在的位置已经有数据的时候,将该值顺序再进行移动,直到找到一个不冲突的位置,存放进去

三.Set,Map,List

Set,Map,List是java中常见的三个接口,其中List和Set接口共同继承了Collections接口.其中Set接口中的数据不允许重复,允许为空,但只有有一个元素为空,Map接口则是用键值对来存储数据;List接口则是相当于一个动态的数组,可以调整大小.

ArrayList和LinkedList的区别

这两个List的区别实际上就是顺序存储和链式存储之间的区别

ArrayList通过序号查找元素快,但是增加和删除元素效率比较低,尤其是当原来分配的空间用完,需要对数组进行扩容的时候会对整个数组进行复制,非常消耗内存,所以适用于遍历和查找元素时使用,不适合删除和增加元素操作比较多的情况使用.

LinkedList插入和删除时的速度会更快,因为链表中插入和删除的时候只需要更改指针的指向即可,但是通过下标进行遍历的时候速度会很慢,因为要先计算出该下标在整个链表的前半段还是后半段,然后顺序查找到元素,所以LinkedList适合插入和删除比较频繁,而随机查找比较少的情况.

HashSet和TreeSet之间的区别

HashSet的内部实现时通过散列表实现的,查找速度非常快,适合经常查找的场合,而且HashSet的性能通常比TreeSet的性能要快,但是由于TreeSet的内部实现是通过平衡二叉树实现的,所以天生已经排好序了,所以TreeSet适合需要有序的场景.当然,由于两者都实现了Set接口,所以HashSet和TreeSet之间的值都不能为空.