java 中几种常用数据结构及原理实现与算法的基础总结

java中有几种常用的数据结构，主要分为Collection和map两个主要接口（接口只提供方法，并不提供实现），而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系（继承关系）有：  （----详细参见java api文档！）

Collection---->Collections                                                                                                          Map----->SortedMap------>TreeMap

Collection---->List----->(Vector \ ArryList \ LinkedList)                                                          Map------>HashMap

Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)

 

 

--------------Collection----------------

1、Collections

    API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.

The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null. 

2、List

    API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.

The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null. 

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下 >标）来访问List中的元素，这类似于Java的数组。

3、Vector

     API----The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of aVector can grow or shrink as needed to accommodate adding and removing items after theVector has been created. 

基于数组（Array）的List，其实就是封装了数组所不具备的一些功能方便我们使用，所以它难易避免数组的限制，同时性能也不可能超越数组。所以，在可能的情况下，我们要多运用数组。另外很重要的一点就是Vector是线程同步的(sychronized)的，这也是Vector和ArrayList 的一个的重要区别。 

 

4、ArrayList

     API----Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

 

同Vector一样是一个基于数组上的链表，但是不同的是ArrayList不是同步的。所以在性能上要比Vector好一些，但是当运行到多线程环境中时，可需要自己在管理线程的同步问题。

 

5、LinkedList

     API----Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue. 

 

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

List总结：

 

 

• 所有的List中只能容纳单个不同类型的对象组成的表，而不是Key－Value键值对。例如：[ tom,1,c ]

• 所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]

• 所有的List中可以有null元素，例如[ tom,null,1 ]

     基于Array的List（Vector，ArrayList）适合查询，而LinkedList 适合添加，删除操作

 

6、Set(接口)

     API-----A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.  Set是不包含重复元素的Collection

7、HashSet

   API-----This class implements theSet interface, backed by a hash table (actually aHashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits thenull element. 

虽然Set同List都实现了Collection接口，但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是Set则是在 HashMap的基础上来实现的，这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。看看 HashSet的add（Object obj）方法的实现就可以一目了然了。

8、LinkedHashSet

    API----Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (includingnull). In addition to implementing theList interface, the LinkedList class provides uniformly named methods toget, remove andinsert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack,queue, ordouble-ended queue.  HashSet的一个子类，一个链表。

9、SortedSet

   API---ASet that further provides atotal ordering on its elements. The elements are ordered using theirnatural ordering, or by aComparator typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order. Several additional operations are provided to take advantage of the ordering. (This interface is the set analogue ofSortedMap.)  

有序的Set，通过SortedMap来实现的。

Set总结：

（1）Set实现的基础是Map（HashMap）（2）Set中的元素是不能重复的，如果使用add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象

-------------Map-----------------

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

1、HashMap

   API----Hash table based implementation of theMap interface. This implementation provides all of the optional map operations, and permitsnull values and the null key. (The HashMap class is roughly equivalent toHashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.  

2、TreeMap

   API----A Red-Black tree basedNavigableMap implementation. The map is sorted according to thenatural ordering of its keys, or by aComparator provided at map creation time, depending on which constructor is used.  TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。 
键和值的关联很简单，用put(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。 

------------说明-----------

一、几个常用类的区别 
1．ArrayList: 元素单个，效率高，多用于查询 
2．Vector: 元素单个，线程安全，多用于查询 
3．LinkedList:元素单个，多用于插入和删除 
4．HashMap: 元素成对，元素可为空 
5．HashTable: 元素成对，线程安全，元素不可为空 
二、Vector、ArrayList和LinkedList 
大多数情况下，从性能上来说ArrayList最好，但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现，但是它们三个性能都比不上数组，另外Vector是线程同步的。所以： 
如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替List； 
如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择ArrayList； 
如果在多线程条件下使用，可以考虑Vector； 
如果需要频繁地删除插入，LinkedList就有了用武之地； 
如果你什么都不知道，用ArrayList没错。 
三、Collections和Arrays 
在 Java集合类框架里有两个类叫做Collections（注意，不是Collection！）和Arrays，这是JCF里面功能强大的工具，但初学者往往会忽视。按JCF文档的说法，这两个类提供了封装器实现（Wrapper Implementations）、数据结构算法和数组相关的应用。 
想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧，Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作： 
binarySearch：折半查找。 
sort：排序，这里是一种类似于快速排序的方法，效率仍然是O(n * log n)，但却是一种稳定的排序方法。 
reverse：将线性表进行逆序操作，这个可是从前数据结构的经典考题哦！ 
rotate：以某个元素为轴心将线性表“旋转”。 
swap：交换一个线性表中两个元素的位置。 
…… 
Collections还有一个重要功能就是“封装器”（Wrapper），它提供了一些方法可以把一个集合转换成一个特殊的集合，如下： 
unmodifiableXXX：转换成只读集合，这里XXX代表六种基本集合接口：Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作，将会抛出UnsupportedOperationException异常。 
synchronizedXXX：转换成同步集合。 
singleton：创建一个仅有一个元素的集合，这里singleton生成的是单元素Set， 
singletonList和singletonMap分别生成单元素的List和Map。 
空集：由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。 

 

java 中几种常用数据结构及原理实现与算法的基础总结java 中几种常用数据结构及原理实现与算法的基础总结java 中几种常用数据结构及原理实现与算法的基础总结java 中几种常用数据结构及原理实现与算法的基础总结java 中几种常用数据结构及原理实现与算法的基础总结java 中几种常用数据结构及原理实现与算法的基础总结java 中几种常用数据结构及原理实现与算法的基础总结java 中几种常用数据结构及原理实现与算法的基础总结