容器 集合 数据结构

 

http://www.open-open.com/lib/view/open1474167415464.html

 

 

 

基本容器：

集合：

1.set：元素之间没有关系，确定性，不重复性，无序性。

 

线性结构：

1.线性表：一个元素接着一个元素，随意位置可以插入删除。

2.队：先进先出，只准在尾部插入，在头部读出。

3.栈：后进先出，只准在一端插入和删除。

 

树状结构：

1.树：子节点只有一个父节点，父节点可以有多个子节点。

2.二叉树：每个节点至多有两个子节点的树。

 

网状结构：

1.图：节点之间可以任意连接。

 

其他容器或复合容器：

hash表：利用hash函数根据值查找该值所在的地址（值和地址有一个函数关系，存储地址=f(元素值)，例如：存储地址=元素值的平方），若值的地址冲突，可以用解决冲突的方法，例如：可以用链表的形式挂一个地址。

索引表：在一个有顺序的线性表上抽取一些值组成索引表（索引表的值也是有序的）方便查找。

Map：主要用来存键值对。键是一个列表来存储，对应值用另外一个列表来存。通过键的地址能找到值的地址。（例如：两个同样大小的数组，一个存键一个存值，键和值的下标相同）

 

容器的存储方式：

顺序存储：（地址空间连续）（读取指定位置的元素方便，插入和删除需要依次移动元素麻烦），

链式存储：（前个元素有指针指向下个元素）（读取指定位置的元素需要从头依次查找麻烦，插入和删除只需移动指针方便。）。

-------------------------------------------------------------------------------------------------------------------------------------

1.1

 1.2

 

 

1.集合set

HashSet：Hash表存储set，元素不能重复。

-------------------------------------------

TreeSet：元素是排序，默认是自然顺序。也可自己传Comparator

-------------------------------------------

LinkedHashSet：元素有插入的顺序。

------------------------------------------------------------------------------------

 

2.list，queue，stack（线性表，队，栈）

lis（线性表）t：

Arraylist：是线性存储，就是用数组实现的，它会动态增加他的50%容量。善于查找。

LinkedList：是链式存储，善于增加删除。使用时LIst list=new LinkedList();

--

vector：和ArrayList基本一样，它会动态增加他的翻倍容量，也可设置增长因子，只是它是线性安全的。

--

并发包的：

------------------------------------------------------------------------------------

queue（队）：

LinkedList：它实现Queue接口。使用时：Queue queue = new LinkedList();

--

并发包的：

-------------------------------------------

PriorityQueue:带有先级的队列，每次从队列中取出的是具有最高优先权的元素。构造时需要传Comparator，如果没有数字默认是小的在队列头，字符串则按字典序排列。

------------------------------------------------------------------------------------

 栈：

--

stack：线性安全的栈。数组现实的。

------------------------------------------------------------------------------------

deque（双端队列）：技能实现队的功能又能显示栈的功能。：

ArrayDeque:是线性存储，就是用数组实现的双端队列。

LinkedList：它实现Deque接口。使用时：Deque deque= new LinkedList();

--

并发包的： 

------------------------------------------------------------------------------------

 

3.map

HashMap：用哈希表的方法存储键值对。允许key为null

--

HashTable：和nashmap相似，只是它是线程安全的。不允许key为null

-------------------------------------------

TreeMap：是排序的容器，用iterator输出是排序好的，默认是按自然顺序，也可构造时传Comparator自定义顺序，键底层是二叉树数据结构。

-------------------------------------------

LinkedHashMap：能保持插入的顺序。在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。实体虽然是以Hash的顺序存放在Hash表中，但是实体之间却用链表的形式保持了存入的先后关系。

 

-------------------------------------------------------------------------------------------------------------------------------------

ComParable是比较接口compareTo(T another);是需要比较的类自身实现。类自身实现。

ComParator也是比较接口compare(T lhs, T rhs);是可以传一个类的两个实例进行比较。类外实现

 

Collections：集合类的，排序或其他功能工具。

Arrays：普通数组（int[] a）的,排序或其他功能的工具。