各种容器解析

   

1  容器分为两种：Collection和Map

2 各自旗下的子类关系：

 Collection:

         ---- List:是一个接口,实现类有ArrayList/LinkedList/Vector.

         特点：将以特定次序放入元素，取出来的可能和放进去的顺序不同。可以有重复元素。

 

         ---- Set:是一个接口，实现类有：HashSet/TreeSet.

         特点：不能有重复元素,用它的迭代器来遍历元素。

 

        用法：

-----ArrayList最长用，查找效率高。可以理解为以数组形式存储。LinkedList,可以理解为时以链表形式存储，插入删除效率高，查找效率低。虽然它也有get(int index)方法来得到元素，但内部是按照链表连接顺序来查找滴，因此get()的效率不高。Vector总是比ArrayList慢，很少使用。

 

-----HashSet:实际上是一个 HashMap 实例,从源码看出内部实例化的是一个hashMap.它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。 可以得到它的迭代器遍历元素。TreeSet:能够维护其内部元素的排序状态。通常只有当需要产生一个经过排序的序列才用TreeSet,它的查找删除效率都比HashSet低。更常用的是HashSet.

 

------TreeSet:是一个TreeMap的实例，保证排序后的顺序按升序排序，或者而按照set提供的比较器排序。

       

HashSet与TreeSet区别：前者无顺序，后者有顺序且不能重复。  HashSet是基于Hash算法实现的,其性能通常优于TreeSet,我们通常都应该使用HashSet,在我们需要排序的功能时,我门才使用TreeSet。

 

 

Map<K,V>:

     -----是一个接口，实现类有HashMap/TreeMap/HashTable.

    特点：存储的是一个键值对。“键”是独一无二滴，所对应的“值”可以重复。

   用法：

---------HashMap:拥有增删查等基本操作,内部机制为利用对象的HashCode快速找到key.

 

   注：HashMap利用了hash表的数据结构，通过一个自定的hash函数把关键字key转化为一个独一无二的int值，即hash值，用该数值确定该key在array数组（长度确定，默认为16，不能扩容，不同于ArrayList）中的位置，若该位置已经有值，则在位置后面连接一个链表，用来放有相同hash值的值，即一个array的值对应多个value.

 

   附录：hash表结构还可以有别的方法来解决冲突，比如二次线性在散列等。详细略。

 

---------TreeMap:该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

 

---------HashTable:HashMap是用来代替HashTable的类，一般现在不用后者。后者不支持null值。hash值的使用不同，HashTable直接使用hashCode得到hash值,代码为：

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

 HashMap有个hash公式计算hash值，代码为

int hash = hash(k);
int i = indexFor(hash, table.length);
static int hash(Object x) {
　　 int h = x.hashCode();

　　 h += ~(h << 9);
　　 h ^= (h >>> 14);
　　 h += (h << 4);
　　 h ^= (h >>> 10);
　　 return h;
}
static int indexFor(int h, int length) {
　　 return h & (length-1);
}

 

HashMap用于快速查找。