Java中集中常见的数据结构(转自CSDN,整理编写)

2018/08/08 12:50
阅读数 10

关于数据结构

java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系(继承关系)有:

Collection—->Collections
Collection—->List—–>(Vector \ ArrayList \ LinkedList)
Collection—->Set—–>(HashSet \ LinkedHashSet \ SortedSet)
Map—–>SortedMap——>TreeMap
Map—–>HashMap

Collection

1.Collections(操作集合的工具类)

对于集合类的操作提供了很多方法,如求两个集合的差集,并集,拷贝,排序等.
由于大部分的集合接口实现类都是不同步的,可以使用Collections,synchronized方法创建同步的集合类对象.

2.List(列表)

List是有序的Collection,使用此接口能够精确地控制每一个元素插入的位置.用户能够使用索引(元素在List中的位置,类似数组的下标)来访问List中的元素,这类似于Java的数组.

(1)Vector

线性表,使用Object数组作为容器去存储数据的.基于数组(Array)的List,其实就是封装了数组所不具备的一些功能,难以避免数组的限制,性能也不可能超越数组.所以,在可能的情况下,我们要多使用数组.另外很重要的一点是Vector是线程同步的(synchronized)的,这是Vector与ArrayList的一个重要区别.

(2)ArrayList

同Vector一样是基于数组的线性链表,但是不同的是ArrayList是非线程安全的,不同步.所以在性能上要比Vector好一些,但是在多线程的环境要注意设置线程同步问题.

(3)LinkedList

LinkedList不用于前面两种List,不基于数组,不受数组性能限制.
它每个节点(Node)都包含两个方面的内容:
1.节点本身的数据(data)
2.下一个节点的信息(nextNode)
所以当对LinkedList做天剑,删除操作的时候不用像基于数组的ArrayList一样,必须进行大量的数据移动.只要改nextNode的相关信息就可以实现,这是LinkedList优势.

3.List总结

  • 所有的List中只能容纳单个不同类型的对象组成的表,而不是Key-Value键值对
  • 所有的List中可以有相同的元素,例如Vector中[tom,tom,koo,koo]
  • 所有的List中可以有null元素,例如[tom,null,1]
    基于Array的List(Vector和ArrayList)适合查询,而LinkedList适合添加,删除操作.

4.Set(接口)

Set是不包含重复元素的Collection

(1)HashSet

虽然Set同List都实现了Collection接口,但是它们的实现方式却大不相同,List基本上是基于Array,而Set是基于HashMap
这个是Set和List的根本区别.HashSet的存储方式是把HashMap的Key作为Set的对应存储项.使用hashcode和equals方法进行判断元素是否重复.
当你试图把对象加入HashSet时,HashSet会使用对象的hashCode来判断对象加入的位置.同时也会与其他已经加入的对象的hashCode进行比较,如果没有相等的hashCode,HashSet就会假设对象没有重复出现.
简单一句话,如果对象的hashCode值是不同的,那么HashSet会认为对象是不可能相等的

(2)LinkedHashSet

HashSet的一个子类,一个链表.会保存插入的顺序

(3)SortedSet

有序的Set,通过SortedMap来实现的.

4,Set总结

  • Set实现的基础是Map(HashMap)
  • Set中的元素是不重复的,如果使用add(Object object)方法添加已存在的对象,则会覆盖之前的对象.

5.Map

Map 是一种把键对象和值对象进行关联的容器,而一个值对象又可以是一个Map,依次类推,这样就可形成一个多级映射。对于键对象来说,像Set一样,一个 Map容器中的键对象不允许重复,这是为了保持查找结果的一致性;如果有两个键对象一样,那你想得到那个键对象所对应的值对象时就有问题了,可能你得到的并不是你想的那个值对象,结果会造成混乱,所以键的唯一性很重要,也是符合集合的性质的。当然在使用过程中,某个键所对应的值对象可能会发生变化,这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求,你可以将任意多个键都映射到一个值对象上,这不会发生任何问题(不过对你的使用却可能会造成不便,你不知道你得到的到底是那一个键所对应的值对象)。

(1)HashMap

(2)TreeMap

TreeMap是按键顺序存放的,因此它便有一些扩展的方法,比如firstKey(),lastKey()等,你还可以从TreeMap中指定一个范围以取得其子Map.
键和值的关联很简单,用put(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

6.总结数据结构

一、几个常用类的区别
1.ArrayList: 元素单个,效率高,多用于查询
2.Vector: 元素单个,线程安全,多用于查询
3.LinkedList:元素单个,多用于插入和删除
4.HashMap: 元素成对,元素可为空
5.HashTable: 元素成对,线程安全,元素不可为空


二、Vector、ArrayList和LinkedList
大多数情况下,从性能上来说ArrayList最好,但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现,但是它们三个性能都比不上数组,另外Vector是线程同步的。所以:
如果能用数组的时候(元素类型固定,数组长度固定),请尽量使用数组来代替List;
如果没有频繁的删除插入操作,又不用考虑多线程问题,优先选择ArrayList;
如果在多线程条件下使用,可以考虑Vector;
如果需要频繁地删除插入,LinkedList就有了用武之地;
如果你什么都不知道,用ArrayList没错。

看到hash,就要想到hashCode,equals.
看到tree,就要想到两个接口。Comparable,Comparator。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部