导读

为什么要学习数据结构？

数据结构是关于如何组织（存储）数据的！编程实践中经常涉及到组织（存储）数据，所以要学习数据结构。

那么为啥还要学习抽象数据类型（Abstract Data Type，ADT）呢？

ADT描述了数据集、指明了在数据集上可能执行的操作。ADT是一种规范，它和具体的编程语言无关。尽管Java API提供多种数据结构，但是如果遇到不适用的情形，就需要针对这种情形定义ADT，然后使用Java实现它。况且如果不深入全面地掌握数据结构这方面的知识，就无法理解和合理的使用Java API提供的数据结构。

数据结构和ADT是什么关系呢？

ADT是一个规范，用于一组值以及对这组值执行的操作。而数据结构是使用编程语言对ADT的实现。

那么如何描述ADT呢？

我们仅描述数据和操作，不指明如何保存数据以及如何实现操作，会考虑一些实现的细节，但与具体编程语言无关。

我们借助UML以及对他们的说明来描述ADT。还可以使用伪代码，不过UML足以说明问题。

设计ADT的步骤是什么呢？

确定行为，然后指定数据和操作，并且考虑特殊情况。

ADT Dictionary（字典）简介

生活中有许多字典或词典。从小学起我们开始学习查阅新华字典，到了高年级我们开始翻阅英汉词典，慢慢的我们开始使用辞海，再往后，我们又或多或少的接触了一些专业词典，字典伴随了我们一生。我们给字典或词典下个通俗的定义，它是一类带有目录的，为字或词给出释义，有可能还提供例句的工具书。

数据结构中的字典与之相是，也是有“目录”，我们称之为键。

我们根据目录在字典或词典中查字或词的释义，同样地，我们也根据键查找键对应的值。

字典（dictionary）又被称为映射（map）、表（table）、关联数组（asociative array） 。

ADT Dictionary（字典）的规格说明

ADT Dictionary（字典）操作细节阐述

ADT Dictionary的键不能为null，值可以为null，null表示什么都没有，如果让一个键是null，将是矛盾的。其实，值为null也不是一个好的策略。键存在而值不存在，这种表达在现实生活种代表了一种错误，譬如，你在字典的目录中找到了一个字的索引，按照索引的指示却无法找到对应的词条，那么一定是字典印刷错误。

ADT Dictionary可以有重复的键和值，但是如果你在规格说明中要求字典的键是不可以重复的，这也是合理的，那么针对这两种情况就要分别加以说明。

键不能重复

如果要求键不能重复，那么add方法的前置条件还要加一条：当插入键已存在于字典中，那么插入操作无效。或者你也可以抛出异常，说明键已存在，不过抛出异常似乎不是一种好策略，当键重复时，我们只需让插入操作不生效便可，如果此时抛出异常，客户端还要处理这种异常，而客户端完全不必处理这种异常。

键可重复

对于键可重复的词典来说，getValue方法根据键找到的值可能不止一个，那么上面列举的getValue方法就不合适了，因为上面列举的getValue方法返回一个值，而在键可重复的情形下应该返回一个集合。

设计模式:迭代器模式

getKeyIterator和getValueIterator都返回迭代器，这两个方法也可以返回键或值数组，然后用数组下标访问，那么迭代器优势在哪呢？

首先简要阐述一下迭代器模式（以下概念来自于《设计模式：可复用面向对象软件的基础》）。

1 定义

提供一种方法顺序访问一个聚合对象中的各个元素，而又不需暴露该对象的内部表示。

2 适用性

1）访问一个聚合对象的内容而无需暴露它的内部表示。

2）支持对聚合对象的多种遍历。

3）为遍历不同的聚合结构提供一个统一的接口（即，支持多态迭代）。

3 结构

说明：

1）Iterator：迭代器定义访问和遍历元素的接口。

First使迭代器指向聚合的第一个元素。

Next使迭代器指向当前元素的下一个元素

IsDone检查当前元素的索引是否超出聚合的范围

CurrentItem返回当前索引对应的元素

2）ConcreteIterator：具体迭代器实现迭代器接口。对该聚合遍历时跟踪当前位置。

3）Aggregate：聚合定义创建相应迭代器对象的接口。

4）ConcreteAggregate：具体聚合实现创建相应迭代器的接口，该操作返回ConcreteIterator的一个适当的实例。

迭代器模式的适用性也是他的效果或重要的作用。这样看来迭代器比起Java提供的其他几种实现迭代的语法要更有优势。

ADT Dictionary（字典）转换为接口

转换的过程中使用了迭代器，我们看一下Java定义的迭代器接口，与上面迭代器模式中的接口稍有不同。先不看其定义的默认方法，hasNext相当于上面模式中的IsDone，而Iterator接口中没有定义First方法。

interface Iterator{

boolean hasNext();

E next();

default void remove(){

throw new UnsupportedOerationException();

}

default void forEachRemaining(Consumer super E> action) {

Objects.requireNonNull(action);

while (hasNext())

action.accept(next());

}

}