JAVA中常用的数据结构（java.util. 中）
 
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, theLinkedList 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表示。 

 

数据结构大致包含以下几种存储结构：
 线性表，还可细分为顺序表、链表、栈和队列；
 树结构，包括普通树，二叉树，线索二叉树等；
 图存储结构；
 线性表
 线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
 
例如，存储类似 {1,3,5,7,9} 这样的数据时，各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），因此可以使用线性表存储。
 
线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。
 顺序表
 顺序表，简单地理解，就是常用的数组，只是换了个名字而已，例如使用顺序表存储 {1,3,5,7,9}，如图 1 所示：
 
顺序表结构
 图 1 顺序表结构
 由于顺序表结构的底层实现借助的就是数组，因此对于初学者来说，可以把顺序表完全等价为数组，但实则不是这样。数据结构是研究数据存储方式的一门学科，它囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。
 
 顺序表结构
 链表
 我们知道，使用顺序表（底层实现靠数组）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的，如图 1 所示。
 
链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。
 
为了给各个数据块建立“依次排列”的关系，链表给各数据块增设一个指针，每个数据块的指针都指向下一个数据块（最后一个数据块的指针指向 NULL），就如同一个个小学生都伸手去拉住下一个小学生的手，这样，看似毫无关系的数据块就建立了“依次排列”的关系，也就形成了链表，如图 2 所示：
 
链表结构
 图 2 链表结构
 
 
栈和队列
 栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。
 
栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。
 
栈结构示意图
 图 3 栈结构示意图
 
 
栈结构如图 3 所示，像一个木桶，栈中含有 3 个元素，分别是 A、B 和 C，从在栈中的状态可以看出 A 最先进的栈，然后 B 进栈，最后 C 进栈。根据“先进后出”的原则，3 个元素出栈的顺序应该是：C 最先出栈，然后 B 出栈，最后才是 A 出栈。
 
队列中的元素只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。
 
队列结构示意图
 图 4 队列结构示意图
 
队列结构如图 4 所示，队列中有 3 个元素，分别是 A、B 和 C，从在队列中的状态可以看出是 A 先进队列，然后 B 进，最后 C 进。根据“先进先出”的原则，3 个元素出队列的顺序应该是 A 最先出队列，然后 B 出，最后 C 出。
 树存储结构
 树存储结构适合存储具有“一对多”关系的数据。
 
树存储结构示意图
 图 5 树存储结构示意图
 
 
如图 5 所示，其中张平只有一个父亲，但他却有两（多）个孩子，这就是“一对多”的关系，满足这种关系的数据可以使用树存储结构。
 图存储结构
 图存储结构适合存储具有“多对多”关系的数据。
 
图存储结构示意图
 图 6 图存储结构示意图
 
如图 6 所示，从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，这就是“多对多”的关系，满足这种关系的数据可以使用图存储结构。

数据结构在实际应用中非常常见，现在各种算法基本都牵涉到数据结构，因此，掌握数据结构算是软件工程师的必备技能。
 
一、什么是数据结构
 
数据结构，直白地理解，就是研究数据的存储方式。
 
我们知道，数据存储只有一个目的，即为了方便后期对数据的再利用，就如同我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的加和值，无缘由的数据存储行为是对存储空间的不负责任。
 
因此，数据在计算机存储空间的存放，决不是胡乱的，这就要求我们选择一种好的方式来存储数据，而这也是数据结构的核心内容。
 
数据存储
 
一直以来大家面对的数据存储，都是类似存储 1、 2、{a,b,c}、 这样的问题，解决方式无疑是用变量或者数组对数据进行存储，即：
 
int a=1;int b=2;char str[3]={'a','b','c'};char *data="http://www.strongerhuang.com";
 
但是，如果要存储这样一组数据：{张亮，张平，张华，张群，张晶，张磊}，数据之间具有这样的关系：张亮是张平、张华和张群的父亲，同时张平还是张晶和张磊的父亲，数据之间的关系如图 1 所示：
 

 对于存储之间具有复杂关系的数据，如果还是用变量或数组来存储（比如用数组存储 {“张亮”,“张平”,“张华”,“张群”,“张晶”,“张磊”} ），数据存储是没有问题，但是无法体现数据之间的逻辑关系，后期根本无法使用，显然不明智。
 
针对此类数据，数据结构中提供有专门的树结构来存储这类数据。
 
再比如，导航无疑是出游旅行的必备神器，在我们程序员眼中，无论是哪款导航软件，其导航功能的实现都需要大量地图数据的支持。很明显，这些数据绝不是使用变量或数组进行存储的，那样对于数据的使用简直是个悲剧。
 
针对此类数据，数据结构提供了图存储结构，专门用于存储这类数据。
 
其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C语言C++交流群1075673198，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。
 
二、数据结构存储分类
 
大致包含以下几种存储结构：
 
 
线性表，还可细分为顺序表、链表、栈和队列；
 
 
树结构，包括普通树，二叉树，线索二叉树等；
 
 
图存储结构；
 
 
三、线性表
 
线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
 
 
例如，存储类似 {1,3,5,7,9} 这样的数据时，各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），因此可以使用线性表存储。
 
线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。
 
其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C语言C++交流群1075673198，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。
 
1.顺序表
 
顺序表，简单地理解，就是常用的数组，只是换了个名字而已，例如使用顺序表存储 {1,3,5,7,9}，如图所示：
 
 
由于顺序表结构的底层实现借助的就是数组，因此对于初学者来说，可以把顺序表完全等价为数组，但实则不是这样。数据结构是研究数据存储方式的一门学科，它囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。
 
2.链表
 
我们知道，使用顺序表（底层实现靠数组）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的，如图 1 所示。
 
链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。
 
为了给各个数据块建立“依次排列”的关系，链表给各数据块增设一个指针，每个数据块的指针都指向下一个数据块（最后一个数据块的指针指向 NULL），就如同一个个小学生都伸手去拉住下一个小学生的手，这样，看似毫无关系的数据块就建立了“依次排列”的关系，也就形成了链表，如图所示：
 
 
3.栈和队列
 
栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。 栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。
 
 
栈结构如上图所示，像一个木桶，栈中含有 3 个元素，分别是 A、B 和 C，从在栈中的状态可以看出 A 最先进的栈，然后 B 进栈，最后 C 进栈。根据“先进后出”的原则，3 个元素出栈的顺序应该是：C 最先出栈，然后 B 出栈，最后才是 A 出栈。
 
队列中的元素只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。
 
 
队列结构如上图所示，队列中有 3 个元素，分别是 A、B 和 C，从在队列中的状态可以看出是 A 先进队列，然后 B 进，最后 C 进。根据“先进先出”的原则，3 个元素出队列的顺序应该是 A 最先出队列，然后 B 出，最后 C 出。
 
四、树存储结构
 
树存储结构适合存储具有“一对多”关系的数据。
 
 
如上图所示，其中张平只有一个父亲，但他却有两（多）个孩子，这就是“一对多”的关系，满足这种关系的数据可以使用树存储结构。
 
五、图存储结构
 
图存储结构适合存储具有“多对多”关系的数据。
 
 
如上所示，从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，这就是“多对多”的关系，满足这种关系的数据可以使用图存储结构。

本文目录：
 

 
 
数据结构分类
1、数组
2、栈
3、队列
4、链表
5、树
6、散列表
7、堆
8、图
 
 
 
数据结构分类
 
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 
 常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示： 
  
 每一种数据结构都有着独特的数据存储方式，下面为大家介绍它们的结构和优缺点。
 
1、数组
 
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。
 
int[] data = new int[100]；data[0]  = 1;
 
优点： 
 1、按照索引查询元素速度快 
 2、按照索引遍历数组方便
 
缺点： 
 1、数组的大小固定后就无法扩容了 
 2、数组只能存储一种类型的数据 
 3、添加，删除的操作慢，因为要移动其他的元素。
 
适用场景： 
 频繁查询，对存储空间要求不大，很少增加和删除的情况。
 
2、栈
 
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。 
  
 栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
 
3、队列
 
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下： 
  
 使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
 
4、链表
 
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 
  
 链表的优点： 
 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素； 
 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
 
缺点： 
 因为含有大量的指针域，占用空间较大； 
 查找元素需要遍历链表来查找，非常耗时。
 
适用场景： 
 数据量较小，需要频繁增加，删除操作的场景
 
5、树
 
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
 
每个节点有零个或多个子节点； 
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
 
在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。 
  
 二叉树是树的特殊一种，具有如下特点：
 
1、每个结点最多有两颗子树，结点的度最大为2。 
 2、左子树和右子树是有顺序的，次序不能颠倒。 
 3、即使某结点只有一个子树，也要区分左右子树。 
 
二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
 
扩展： 
 二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。
 
6、散列表
 
散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
 
记录的存储位置=f(key) 
 
这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
 
哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，其示例图如下： 
  
 从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。 
 
哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
 
7、堆
 
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
 
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
 
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
 
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 
 (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下： 
  
 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
 
8、图
 
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 
 
按照顶点指向的方向可分为无向图和有向图： 
  
  
 图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。