A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© HM赵磊 中级黑马   /  2013-3-13 10:44  /  1416 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 csatshell 于 2013-3-16 10:25 编辑

最近看了集合框架,里面的集合子类对象涉及到了底层的数据结构,例如List涉及到了线性表  HashSet涉及到了哈希表,TreeSet涉及到了二叉树等.大家谁对线性表,树,图等数据结构了解的多,可以说说他们的特点,什么时候应用等等。

点评

如果问题未解决,请继续追问回复者,如果问题已解决,请尽快修改分类为已解决,否则将扣除相应技术分,谢谢  发表于 2013-3-16 07:15
如果问题已经解决了,请将分类改为已解决,谢谢  发表于 2013-3-15 08:27

评分

参与人数 1技术分 +1 收起 理由
猫腻 + 1

查看全部评分

4 个回复

倒序浏览
我随便说说吧,我不是计算机专业的,c语言看过点,数据结构压根没看,这是我的理解,既然是用到了集合,首先你要确定你往集合里面添加元素时,是希望元素在集合里面是有序排列还是无序排列,这个顺序是你往集合里面扔元素的顺序,如果你想有序排列的话就要考虑使用实现了list接口的对象,主要的两个是ArrayList和LinkedList,前者是利用数组数据结构存放数据,该数据结构的好处是拿到数据比较快,数据存放在内存中是一条一条的,你想拿到第几个元素,可以用元素的下标值乘以元素的字节数直接定位过去,读取数据相当快,相反,删除数据就比较慢了,删除指定下标的数据后,还要把后面的元素每一个都要向前移一个元素的字节数。如果是使用LinkedList这个链表集合,和ArrayList相反是典型的改快读慢,因为他在内存中存储数据不是连续的,每一个元素中不止保留了该元素,还有下一个元素的地址,第一个元素指向第二个元素,第二个元素指向第三个元素。。。。。。 你想拿到指定下标的元素,没办法像ArrayList直接定位,因为不知道他的地址,例如你如果想拿到第三个元素,只能先找到第一个元素,然后利用第一个元素中的指针找到第二个元素,之后再找第三个元素,够麻烦吧,删除数据就比较快了,想删除第三个元素直接将第二个元素本来指向第三个元素的指针指向第四个元素就可以了,这样原来的第三个元素对象失去引用就成垃圾对象了,看具体的业务逻辑吧,读取数据多的时候就使用ArrayList,删除多的话就使用LinkedList,接下来是实现了
Set的集合了,主要有TreeSet和HashSet,他们都是无序排列,且元素不准重复的,TreeSet底层是用红黑树数据结构说是无序其实是按特定的顺序(从小到大或从大到小)排列的,类似于二分查找,效率相对于传统的方法要高效太多了,hash表没有研究过,这里就不加描述了

评分

参与人数 1技术分 +1 收起 理由
猫腻 + 1

查看全部评分

回复 使用道具 举报
我也是刚学,说说自己的见解不要见笑。。

首先考虑List和Set的选择,简单说来最关键的因素就是List中元素是可以重复的,而Set是不能重复的。
其次,List适合经常性的追加和删除数据,缺点就是随机取数效率低。而Set就适合经常地随机储存,插入和删除数据,但他的缺点就是在遍历时效率较低。

接下来应该可以考虑他们实现类的选择了:
List的实现类:
    ArryList是靠数组来实现的,他具有能够快速访问的特点,他适用于存在大量随机访问的情况。
   LinkedList是靠双向链表实现的,所以插入和删除操作相对代价要低,如果需要大量插入删除操作就可以用他。
再来看Set的实现类:
   HashSet底层是依靠一个Hash表,他的特点就是查询速度非常快,存储效率高,需要重写hashCode()方法。
   TreeSet底层则是平衡二叉树实现,而且元素必须实现Comparable接口,所以他的特点就是能输出有序的元素序列。
   简单来说,HashSet读写高效但不排序,TreeSet效率没HashSet高,但可以排序。

纯属个人理解。。希望别的同学也参加讨论,指出错误。。

评分

参与人数 1技术分 +1 收起 理由
贾文泽 + 1 赞一个!

查看全部评分

回复 使用道具 举报
上面应经回答的不错了,好像有点脱离你的问题,你关注的是数据结构的线性表,树,和图
线性表就是一个由n个数据元素的有限序列。特点就是:1.存在唯一的第一个元素 2、存在唯一的一个最后一个元素 3、除去第一个元素,每个元素存在唯一的前驱4、除了最后一个每个元素存在唯一的后继
树:n个结点的有限集。特点:在任意一个非空树中有且仅有特定的根结点,有多个结点时,可以分为多个互不相交的子集
图:数据元素之间可以有多重关系。
回复 使用道具 举报
对头 !想知道的就是你说的那些东东,你能说详细一点不

EE.jpg (28.04 KB, 下载次数: 4)

EE.jpg

评分

参与人数 1技术分 +1 收起 理由
猫腻 + 1 再送1分 结贴

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马