数据结构之List，Map，Set

存储结构是计算机存储、组织数据的方式。

精心选择的数据结构可以带来更高的运行或存储效率，数据结构往往同高效的检索算法和索引技术有关。

 

arrayList：本质上是一个Object数组结构，默认容量为10；

vector：其实方法与ArrayLIst基本相同，只是方法中添加了synchronized修饰符，是线程安全的。效率比arrayList低。

（在1.7和1.7版本后，尽量不要使用vector，因为arrayList也可以线程安全（Collections.synchronizedList(list)）。在1.7版本后，ArrayList进行和更改，当ArrayList list=new ArrayList ()时，不会进行容量分配，只会定义变量，使用时在进行空间分配。而vector时直接分配默认为10的容量，并进行空间分配）

LinkedList：LinkedList是一个链表的结构，LinkedList中有三个重要的变量。

Node First；//LinkedList的头节点

Node Last：//LinkedList的尾节点

Integer size；//LinkedList的数组长度

其中Node是LinkedList的子类 重要变量包括

Node previos；//当前节点的上一个节点

Node next；//当前节点的下一个节点

Object[] elements;//当前节点的值

ArrayList和LinkedList的区别：

添加操作：添加时，判断size与数组的容量，如果未满，将在数组中添加，size++。如果满了，重新建立数组，然后将之前的数组复制进来，再进行添加，size++。LinkedList没有容量的概念，所以当添加的时候，涉及不到扩容。LinkedList胜。

插入/删除操作：当插入操作的时候，ArrayList会将插入节点之后的每个节点都往后移动，很费时间。当LinkedList进行插入时，找到这个只需要改变前节点的next，和后节点的previos即可。LinkedList性能高

查询和修改操作：LinkedList是链表，所以遍历的能力不是很优秀，这是ArrayList最擅长的。修改数据之前需要先遍历查询，所以还是ArrayList性能高。

注意：vector、ArrayList、LinkedList都是有序的，因为vector和ArrayList都是具有索引的，LInkedList有链表，也是有顺序的。他们都允许包含相同的对象。

 

 

HashSet实质上也是一个数组，它是不可重复的，也是添加无序的。它是以对象本身的hashcode（因为hashcode比较长）根据算法生成hash，以hash做索引，其实他是以hash做顺序的，所以可以说对象的hashCode值决定了哈希表中的存储位置。存在HashSet的对象元素都得覆盖equals()和hashcode()方法，那为什么我们没有覆盖过呢，因为在用eclipes工具的时候，它已经帮你做完了。

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

对象都继承于Object类，Object类中有equals（）和hashCode（）方法。

equals（）方法在Object中本质是==，即判断两个对象是否指向同一个内存空间。

User user1=new User("sss", "111");

User user2=new User("sss", "111");

User user3 = user2;

 

System.out.println(user1==user2);//false

System.out.println(user1.equals(user2));//false

System.out.println(user1.hashCode()==user2.hashCode());//false

 

System.out.println(user2==user3);//true

System.out.println(user2.equals(user3));//true

System.out.println(user2.hashCode()==user3.hashCode());//true

那么来看这个

String A=new String("A");

String B=new String("A");

System.out.println(A==B);//false

System.out.println(A.equals(B));//true

System.out.println(A.hashCode()==B.hashCode());//true

HashSet set=new HashSet();

set.add(A);

set.add(B);

System.out.println(set);//输出结果只有一个“A”

从代码看到，A，B都是new了一个对象，所以两个对象的指引是不同的，为什么equals是true呢？因为String类覆盖了Object中的equals方法，先判断是否==，等于返回true，false则继续判断里面数据是否相等，因为相等，所以返回true。

1、首先equals()和hashcode()这两个方法都是从object类中继承过来的。

 

　　equals()是对两个对象的地址值进行的比较（即比较引用是否相同）。

 

　　hashCode()是一个本地方法，它的实现是根据本地机器相关的。

 

2、Java语言对equals()的要求如下，这些要求是必须遵循的：

 

　　A 对称性：如果x.equals(y)返回是“true”，那么y.equals(x)也应该返回是“true”。

 

　　B 反射性：x.equals(x)必须返回是“true”。

 

　　C 类推性：如果x.equals(y)返回是“true”，而且y.equals(z)返回是“true”，那么z.equals(x)也应该返回是“true”。

 

　　D 一致性：如果x.equals(y)返回是“true”，只要x和y内容一直不变，不管你重复x.equals(y)多少次，返回都是“true”。

 

　　任何情况下，x.equals(null)，永远返回是“false”；x.equals(和x不同类型的对象)永远返回是“false”。

 

3、 equals()相等的两个对象，hashcode()一定相等；

 

　　反过来：hashcode()不等，一定能推出equals()也不等；

 

　　hashcode()相等，equals()可能相等，也可能不等。 

举个简单的例子，假如String类型没有覆盖Object的方法，那么new（“A”）两次，hashCode值是相同的，但是equals是不同的，因为不是同一个指引。如果equals是同一个指引，那么他们的hashCode一定相同

在添加操作是，先判断hashcode()是否相等，false直接添加。如果等于true，在判断equals是否相等，true则被视为同一个对象，不保存在hash表里。

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

Set家族比较

相同点：1）都不允许有元素重复

2）都不是线程安全的类

解决办法：Set<String> set1 = Collections.synchronizedSet(new HashSet<String>());

不同点：

HashSet：上面有说了那么多，不提了。

LinkedHashSet：从字面上看，就知道它的特点链表和Hash算法，Hash算法判断对象元素是否重复，链表结构记录它的添加顺序。

很明显，它因为增加了Linked的方法，性能上是没有HashSet高的。

TreeSet：不保证元素的先后的添加顺序，但是会对集合中的元素进行做排序操作。

底层是红黑树（树结构，比较擅长范围查询）。至于什么是红黑树，我会在以后的学习中详细说明。

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

HashSet做等值查询效率高，TreeSet做范围查询效率高（数据库的索引都是树结构的哦~~）

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

Map

Map是没有实现Collections接口的。首先我们先从字面了解一下什么是Map，大家有接触到mybatis中，有涉及到.Mapping吧，表示的是映射。其实Map表示的也是一种映射关系，就是key-value的映射。

从数学的概念解释映射：

A，B有两个非空的集合，如果存在一个法则f，使得对A中的每个元素a，按照法则f，在a中有唯一确定的元素b与之对应，则成f为从A到B的映射，记作：f：A->B。

那么对于Map来将，A即是key,B即是value。

根据Map的规则来看，第一key不能重复。那么key组合的集合像不像是Set？键的值可以重复，像不像是一个List？

验证一下：

public Set<K> keySet()//Map接口方法

代码验证一下是这样的：

Map<String, String> map=new HashMap<String, String>();

map.put("a", "A");

map.put("b", "B");

map.put("c", "C");

map.put("d", "D");

map.put("e", "E");

Set<String>keyset=map.keySet();

System.out.println(keyset);

 

------

public Collection<V> values()

查看API发现这个方法返回的类是Collection

Collection collection= map.values();

System.out.println(collection);

纵向的我们看完了Map的原理，那么横向看，它就是一个多个键值对（Entry）组成的。

 

Set<Map.Entry<String,String>> entry = map.entrySet();

for(Map.Entry<String, String> e:entry){

System.out.println(e.getKey() +"->"+e.getValue());

}

Map家族比较：

HashMap：采用hash算法，此时Map中的key不会保证添加的顺序，key也不允许重复。

LinkedHashMap：采用链表和Hash算法，此时Map中会保证添加的先后顺序，key允许重复

TreeMap：采用红黑树算法，此时map中的key会按照自然排序或定制排序进行排序，key不允许重复。key判断标准是：compareto/comparede的返回值为0

HashTable：线程安全的，是HashMap的前身，能不用尽量不用。

Properties：HashTable的子类，要求key和value都是String类型。

（这个看着很熟悉，是因为配置文件是这个格式的吧（.properties）的，以后会进行更新。）

小问题：看了这么多，现在给你一个String str="asdfgqwerasdfgas",能够算出他们每个的数量吗？做出来后，可以使他们添加的顺序有序吗？可以让他们以a，b。。这样的方式排序吗